Zobrazeno 1 - 10
of 26
pro vyhledávání: '"Kuivinen, Fredrik"'
Autor:
Kuivinen, Fredrik
In the Constraint Satisfaction Problem (CSP) one is supposed to find an assignment to a set of variables so that a set of given constraints are satisfied. Many problems, both practical and theoretical, can be modelled as CSPs. As these problems are c
Externí odkaz:
http://urn.kb.se/resolve?urn=urn:nbn:se:liu:diva-51687
Autor:
Kuivinen, Fredrik
In the maximum solution equation problem a collection of equations are given over some algebraic structure. The objective is to find an assignment to the variables in the equations such that all equations are satisfied and the sum of the variables is
Externí odkaz:
http://urn.kb.se/resolve?urn=urn:nbn:se:liu:diva-3240
We report new results on the complexity of the valued constraint satisfaction problem (VCSP). Under the unique games conjecture, the approximability of finite-valued VCSP is fairly well-understood. However, there is yet no characterisation of VCSPs t
Externí odkaz:
http://arxiv.org/abs/1102.2880
Autor:
Kuivinen, Fredrik
Let $(L; \sqcap, \sqcup)$ be a finite lattice and let $n$ be a positive integer. A function $f : L^n \to \mathbb{R}$ is said to be submodular if $f(\tup{a} \sqcap \tup{b}) + f(\tup{a} \sqcup \tup{b}) \leq f(\tup{a}) + f(\tup{b})$ for all $\tup{a}, \t
Externí odkaz:
http://arxiv.org/abs/0904.3183
An instance of Max CSP is a finite collection of constraints on a set of variables, and the goal is to assign values to the variables that maximises the number of satisfied constraints. Max CSP captures many well-known problems (such as Max k-SAT and
Externí odkaz:
http://arxiv.org/abs/0712.1532
Autor:
Kuivinen, Fredrik
We study the approximability of Max Ones when the number of variable occurrences is bounded by a constant. For conservative constraint languages (i.e., when the unary relations are included) we give a complete classification when the number of occurr
Externí odkaz:
http://arxiv.org/abs/cs/0606057
We study a family of problems, called \prob{Maximum Solution}, where the objective is to maximise a linear goal function over the feasible integer assignments to a set of variables subject to a set of constraints. When the domain is Boolean (i.e. res
Externí odkaz:
http://arxiv.org/abs/cs/0602047
Publikováno v:
In Theoretical Computer Science 2009 410(38):3856-3874
Autor:
Jonsson, Peter1 petej@ida.liu.se, Kuivinen, Fredrik1 freku@ida.liu.se, Nordh, Gustav2 nordh@lix.polytechnique.fr
Publikováno v:
SIAM Journal on Computing. 2008, Vol. 38 Issue 1, p329-365. 37p. 5 Diagrams.