Zobrazeno 1 - 10
of 99
pro vyhledávání: '"Thapper, Johan"'
Autor:
Thapper, Johan, Zivny, Stanislav
Publikováno v:
ACM Transactions on Computation Theory 10(3) Article no. 12 (2018)
It has been shown that for a general-valued constraint language $\Gamma$ the following statements are equivalent: (1) any instance of $\operatorname{VCSP}(\Gamma)$ can be solved to optimality using a constant level of the Sherali-Adams LP hierarchy;
Externí odkaz:
http://arxiv.org/abs/1612.01147
Autor:
Thapper, Johan, Zivny, Stanislav
Publikováno v:
SIAM Journal on Computing 46(4) (2017) 1241-1279
We give a precise algebraic characterisation of the power of Sherali-Adams relaxations for solvability of valued constraint satisfaction problems to optimality. The condition is that of bounded width which has already been shown to capture the power
Externí odkaz:
http://arxiv.org/abs/1606.02577
Autor:
Jonsson, Peter, Thapper, Johan
A semilinear relation is a finite union of finite intersections of open and closed half-spaces over, for instance, the reals, the rationals, or the integers. Semilinear relations have been studied in connection with algebraic geometry, automata theor
Externí odkaz:
http://arxiv.org/abs/1506.00479
Autor:
Thapper, Johan, Zivny, Stanislav
Publikováno v:
Proc. of ICALP'15 1058-1069 (2015)
We consider Sherali-Adams linear programming relaxations for solving valued constraint satisfaction problems to optimality. The utility of linear programming relaxations in this context have previously been demonstrated using the lowest possible leve
Externí odkaz:
http://arxiv.org/abs/1502.05301
Autor:
Thapper, Johan, Zivny, Stanislav
Publikováno v:
SIAM Journal on Discrete Mathematics 29(4) (2015) 2361-2384
The connection between constraint languages and clone theory has been a fruitful line of research on the complexity of constraint satisfaction problems. In a recent result, Cohen et al. [SICOMP'13] have characterised a Galois connection between value
Externí odkaz:
http://arxiv.org/abs/1502.03482
Publikováno v:
SIAM Journal on Computing 44(1) (2015) 1-36
Let $D$, called the domain, be a fixed finite set and let $\Gamma$, called the valued constraint language, be a fixed set of functions of the form $f:D^m\to\mathbb{Q}\cup\{\infty\}$, where different functions might have different arity $m$. We study
Externí odkaz:
http://arxiv.org/abs/1311.4219
Autor:
Thapper, Johan, Zivny, Stanislav
Publikováno v:
Journal of the ACM 63(4) Article No. 37 (2016)
We study the computational complexity of exact minimisation of rational-valued discrete functions. Let $\Gamma$ be a set of rational-valued functions on a fixed finite domain; such a set is called a finite-valued constraint language. The valued const
Externí odkaz:
http://arxiv.org/abs/1210.2987
Autor:
Thapper, Johan, Zivny, Stanislav
Publikováno v:
Proc. of FOCS'12 669-678 (2012)
A class of valued constraint satisfaction problems (VCSPs) is characterised by a valued constraint language, a fixed set of cost functions on a finite domain. An instance of the problem is specified by a sum of cost functions from the language with t
Externí odkaz:
http://arxiv.org/abs/1204.1079
A famous result by Jeavons, Cohen, and Gyssens shows that every constraint satisfaction problem (CSP) where the constraints are preserved by a semi-lattice operation can be solved in polynomial time. This is one of the basic facts for the so-called u
Externí odkaz:
http://arxiv.org/abs/1111.6616
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