7 papers
Vertex cover number of valued constraints is a structural parameter for efficient local search
Artem Kaznatcheev
Many local search methods for problems in artificial intelligence can be viewed as an uphill climb on a corresponding discrete fitness landscapes. Finding even local peaks in these…
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…
All ascents exponential from valued constraint graphs of pathwidth three
Artem Kaznatcheev, Willemijn Volgering
Many combinatorial optimization problems can be formulated as finding an assignment that maximizes some pseudo-Boolean function (that we call the fitness function). Strict local se…
Greed is slow on sparse graphs of oriented valued constraints
Artem Kaznatcheev, Sofia Vazquez Alferez
Greedy local search is especially popular for solving valued constraint satisfaction problems (VCSPs). Since any method will be slow for some VCSPs, we ask: what is the simplest VC…
When is local search both effective and efficient?
Artem Kaznatcheev, Sofia Vazquez Alferez
Combinatorial optimization problems implicitly define fitness landscapes that combine the numeric structure of the 'fitness' function to be maximized with the combinatorial structu…
Exponential Steepest Ascent from Valued Constraint Graphs of Pathwidth Four
Artem Kaznatcheev, Melle van Marle
We examine the complexity of maximising fitness via local search on valued constraint satisfaction problems (VCSPs). We consider two kinds of local ascents: (1) steepest ascents, w…