How easy is local search?

1988/08/01 by David S. Johnson, Christos H. Papadimitriou, Mihalis Yannakakis · 44 citations
Computer Science · Engineering · #Advanced Graph Theory Research #Optimization and Packing Problems #Constraint Satisfaction and Optimization

paper · doi:10.1016/0022-0000(88)90046-3

Cited by

• Unique end of potential line
• Computing pure Nash and strong equilibria in bottleneck congestion games
• The Complexity of Computing a Nash Equilibrium
• On Finding and Verifying Locally Optimal Solutions
• The Kernighan-Lin Search Algorithm
• The Relative Complexity of NP Search Problems
• Foundations of the Pareto Iterated Local Search Metaheuristic
• Correlated Equilibria for Approximate Variational Inference in MRFs
• Computing Stable Outcomes in Symmetric Additively Separable Hedonic Games
• Escaping From Saddle Points --- Online Stochastic Gradient for Tensor Decomposition
• Memetic Algorithms: Parametrization and Balancing Local and Global Search
• Binary constraints on one additional variable can create exponential ascents for local search
• Black-box Optimization of LLM Outputs by Asking for Directions
• PLS-complete problems with lexicographic cost functions: Max-k-SAT and Abelian Permutation Orbit Minimization
• On the Impact of Fair Best Response Dynamics
• Learning Equilibria in Games by Stochastic Distributed Algorithms
• Naturalism, tractability and the adaptive toolbox
• Evolution as fitness landscape navigation: Concepts, Measures, and Emerging Questions
• The frontier of intractability for EFX with two agents
• An Accelerated Introduction to Memetic Algorithms
• Simple Local Search Problems that are Hard to Solve
• The Complexity of Finding Local Optima in Contrastive Learning
• Chaotic Simulated Annealing by A Neural Network Model with Transient Chaos
• Level-Based Analysis of Genetic Algorithms for Combinatorial\n Optimization
• Communication complexity of Nash equilibrium in potential games
• Discrete Price Updates Yield Fast Convergence in Ongoing Markets with Finite Warehouses
• On the Complexity of Modulo-q Arguments and the Chevalley-Warning Theorem
• Efficient computation of approximate pure Nash equilibria in congestion\n games
• Machine learning at the service of meta-heuristics for solving combinatorial optimization problems: A state-of-the-art
• Which graph motif parameters count?
• A near-complete resolution of the exponential-time complexity of k-opt for the traveling salesman problem
• On local search and LP and SDP relaxations for k-Set Packing
• Smoothed complexity of local Max-Cut and binary Max-CSP
• Finding One Local Optimum Is Easy -- but What About Two?
• Approximate Pure Nash Equilibria in Weighted Congestion Games:\n Existence, Efficient Computation, and Structure
• Improving TSP tours using dynamic programming over tree decomposition
• Can Selfish Groups be Self-Enforcing?
• Multi-Verse Optimizer: a nature-inspired algorithm for global optimization
• Greed is slow on sparse graphs of oriented valued constraints
• Complexity of Single-Swap Heuristics for Metric Facility Location and Related Problem
• On the Computational Power of Online Gradient Descent
• Complexity of evolutionary equilibria in static fitness landscapes
• Computational Complexity as an Ultimate Constraint on Evolution. [europepmc]
• Experiments with optimal model trees. [europepmc]