Representing Fitness Landscapes by Valued Constraints to Understand the Complexity of Local Search

DOI10.1613/jair.1.12156zbMath1496.68302arXiv1907.01218MaRDI QIDQ5139600

Artem Kaznatcheev, David A. Cohen, Peter G. Jeavons

Publication date: 9 December 2020

Published in: Journal of Artificial Intelligence Research (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1907.01218

zbMATH Keywords

search; constraint satisfaction; mathematical foundations

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68R10: Graph theory (including graph drawing) in computer science

68T20: Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)

Uses Software

• JBool

Cites Work

• Unnamed Item
• Unnamed Item
• How easy is local search?
• Local optimization on graphs
• Reciprocal sign epistasis is a necessary condition for multi-peaked fitness landscapes
• The complexity of Boolean constraint satisfaction local search problems
• The peaks and geometry of fitness landscapes
• Steepest ascent can be exponential in bounded treewidth problems
• The Complexity of Finite-Valued CSPs
• Simple Local Search Problems that are Hard to Solve
• Necessary Conditions for Tractability of Valued CSPs
• On the Power of Nodes of Degree Four in the Local Max-Cut Problem
• How Perturbation Strength Shapes the Global Structure of TSP Fitness Landscapes
• The complexity of conservative valued CSPs
• An Algebraic Theory of Complexity for Discrete Optimization
• Lower Bounds for Local Search by Quantum Arguments