51 citations · 203 across the 13 of their papers we have counts for
13 papers
Binary constraints on one additional variable can create exponential ascents for local search
David A. Cohen, Peter G. Jeavons, Artem Kaznatcheev +2
Local search in combinatorial optimisation can be viewed as an uphill climb on a corresponding fitness landscape, where the assignments visited by a strict local search follow an a…
Steepest ascent can be exponential in bounded treewidth problems
David A. Cohen, Martin C. Cooper, Artem Kaznatcheev +1
We investigate the complexity of local search based on steepest ascent. We show that even when all variables have domains of size two and the underlying constraint graph of variabl…
Representing fitness landscapes by valued constraints to understand the complexity of local search
Artem Kaznatcheev, David A. Cohen, Peter G. Jeavons
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 fit…
On Singleton Arc Consistency for CSPs Defined by Monotone Patterns
Clement Carbonnel, David A. Cohen, Martin C. Cooper +1
Singleton arc consistency is an important type of local consistency which has been recently shown to solve all constraint satisfaction problems (CSPs) over constraint languages of…
Binary Constraint Satisfaction Problems Defined by Excluded Topological Minors
David A. Cohen, Martin C. Cooper, Peter G. Jeavons +1
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 variab…
Binarisation for Valued Constraint Satisfaction Problems
David A. Cohen, Martin C. Cooper, Peter G. Jeavons +3
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 alge…