Zobrazeno 1 - 10
of 68
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:
Thapper, Johan
In this thesis we study a constraint optimisation problem called the maximum solution problem, henceforth referred to as Max Sol. It is defined as the problem of optimising a linear objective function over a constraint satisfaction problem (Csp) inst
Externí odkaz:
http://urn.kb.se/resolve?urn=urn:nbn:se:liu:diva-52103
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
Autor:
Thapper, Johan
Interactions between combinatorics and statistical mechanics have provided many fruitful insights in both fields. A compelling example is Kuperberg’s solution to the alternating sign matrix conjecture, and its following generalisations. In this the
Externí odkaz:
http://urn.kb.se/resolve?urn=urn:nbn:se:liu:diva-10141
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