Zobrazeno 1 - 10
of 52
pro vyhledávání: '"Jeavons, Peter G."'
Local search is widely used to solve combinatorial optimisation problems and to model biological evolution, but the performance of local search algorithms on different kinds of fitness landscapes is poorly understood. Here we consider how fitness lan
Externí odkaz:
http://arxiv.org/abs/1907.01218
Publikováno v:
Information and Computation 264 12-31 (2019)
The binary Constraint Satisfaction Problem (CSP) is to decide whether there exists an assignment to a set of variables which satisfies specified constraints between pairs of variables. A binary CSP instance can be presented as a labelled graph encodi
Externí odkaz:
http://arxiv.org/abs/1608.05358
Autor:
Cohen, David A., Cooper, Martin C., Jeavons, Peter G., Krokhin, Andrei, Powell, Robert, Zivny, Stanislav
Publikováno v:
SIAM Journal on Discrete Mathematics 31(4) (2017) 2279-2300
We study methods for transforming valued constraint satisfaction problems (VCSPs) to binary VCSPs. First, we show that the standard dual encoding preserves many aspects of the algebraic properties that capture the computational complexity of VCSPs. S
Externí odkaz:
http://arxiv.org/abs/1608.01628
We study the complexity of constraint satisfaction problems involving global constraints, i.e., special-purpose constraints provided by a solver and represented implicitly by a parametrised algorithm. Such constraints are widely used; indeed, they ar
Externí odkaz:
http://arxiv.org/abs/1307.2867
Publikováno v:
In Information and Computation February 2019 264:12-31
Publikováno v:
SIAM Journal on Computing 42(5) 1915-1939 (2013)
Discrete optimisation problems arise in many different areas and are studied under many different names. In many such problems the quantity to be optimised can be expressed as a sum of functions of a restricted form. Here we present a unifying theory
Externí odkaz:
http://arxiv.org/abs/1207.6692
Publikováno v:
Discrete Applied Mathematics 157(15) (2009) 3347-3358
It has previously been an open problem whether all Boolean submodular functions can be decomposed into a sum of binary submodular functions over a possibly larger set of variables. This problem has been considered within several different contexts in
Externí odkaz:
http://arxiv.org/abs/0811.1885
Publikováno v:
In Artificial Intelligence 2010 174(9):570-584
Publikováno v:
In Theoretical Computer Science 2008 409(1):137-153
Publikováno v:
In Theoretical Computer Science 2008 401(1):36-51