How easy is local search?

DOI10.1016/0022-0000(88)90046-3zbMath0655.68074OpenAlexW2103981148WikidataQ96141452 ScholiaQ96141452MaRDI QIDQ1109573

Mihalis Yannakakis, Christos H. Papadimitriou, David S. Johnson

Publication date: 1988

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0022-0000(88)90046-3

zbMATH Keywords

combinatorial optimization local search NP-hard graph partitioning locally optimal solutions

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Searching and sorting (68P10) Graph theory (including graph drawing) in computer science (68R10) Combinatorial optimization (90C27)

Related Items

On the complexity of the parity argument and other inefficient proofs of existence, The complexity of counting locally maximal satisfying assignments of Boolean CSPs, Complexity of single-swap heuristics for metric facility location and related problems, On the quantum query complexity of local search in two and three dimensions, Approximately counting locally-optimal structures, An abstraction-refinement methodology for reasoning about network games, Efficient coordination mechanisms for unrelated machine scheduling, New local search approximation techniques for maximum generalized satisfiability problems, Computing equilibria: a computational complexity perspective, Circuit principles and weak pigeonhole variants, What are the $\forall \Sigma_ 1^ b$-consequences of $T_ 2^ 1$ and $T_ 2^ 2$?, Solving the max-cut problem using eigenvalues, Quantified propositional calculus and a second-order theory for NC$^{\text \textbf{1}}$, Analyzing the complexity of finding good neighborhood functions for local search algorithms, How difficult is the frequency selection problem?, Matrix representation and gradient flows for NP-hard problems, Strategies with memories: Local search in an application oriented environment. Applied local search -- a prologue, A variable-depth search algorithm for the recursive bipartitioning of signal flow graphs, Metaheuristics: A bibliography, On the complexity of approximating a KKT point of quadratic programming, Parallel local search, Computing pure Nash and strong equilibria in bottleneck congestion games, On the quality of local search for the quadratic assignment problem, Finding optimal subgraphs by local search, On the complexity of finding falsifying assignments for Herbrand disjunctions, Recursive stochastic games with positive rewards, Dynamics in network interaction games, Unique end of potential line, A local search template., Black-box search by unbiased variation, Minimizing expectation plus variance, Convergence to approximate Nash equilibria in congestion games, On the computational complexity of cut-reduction, Propositional proofs and reductions between NP search problems, Local search: is brute-force avoidable?, The provably total NP search problems of weak second order bounded arithmetic, Colorful linear programming, Nash equilibrium, and pivots, Convergence and approximation in potential games, Local search for string problems: brute-force is essentially optimal, Performance of one-round walks in linear congestion games, On non-trivial Nash stable partitions in additive hedonic games with symmetric 0/1-utilities, Patience of matrix games, Reactive local search techniques for the maximum $k$-conjunctive constraint satisfaction problem $(MAX-k-CCSP)$, Recent development in computational complexity characterization of Nash equilibrium, Equilibria, fixed points, and complexity classes, Fortran subroutines for computing approximate solutions of weighted MAX-SAT problems using GRASP, Knowledge-guided local search for the vehicle routing problem, The capacitated max $k$-cut problem, On best response dynamics in weighted congestion games with polynomial delays, An analysis of neighborhood functions on generic solution spaces, Efficiently solving very large-scale routing problems, Local minima for indefinite quadratic knapsack problems, Exponentiality of the exchange algorithm for finding another room-partitioning, Local search, reducibility and approximability of NP-optimization problems, A note on the complexity of local search problems, Machine learning at the service of meta-heuristics for solving combinatorial optimization problems: a state-of-the-art, Did the train reach its destination: the complexity of finding a witness, Generalizations of Opt P to the polynomial hierarchy, Traveling salesman problem and local search, Computational aspects of the colorful Carathéodory theorem, Complexity of uniqueness and local search in quadratic 0-1 programming, Paroids: A canonical format for combinatorial optimization, On existence theorems, Open questions in complexity theory for numerical optimization, Local search and the local structure of NP-complete problems, Short sequences of improvement moves lead to approximate equilibria in constraint satisfaction games, Minimizing conflicts: A heuristic repair method for constraint satisfaction and scheduling problems, Memetic algorithms: The polynomial local search complexity theory perspective, Nested PLS, Local search algorithms for political districting, Pseudo-Boolean optimization, Data-independent neighborhood functions and strict local optima, The complexity of Boolean constraint satisfaction local search problems, On complexity of unconstrained hyperbolic 0--1 programming problems, Generalized $k$-multiway cut problems, On the complexity of finding a Caristi's fixed point, The complexity of the parity argument with potential, Symmetries and the complexity of pure Nash equilibrium, On the depth of combinatorial optimization problems, Paroid search: Generic local combinatorial optimization, Sequential and parallel local search for the time-constrained traveling salesman problem, Deterministic job-shop scheduling: Past, present and future, Cache me if you can: capacitated selfish replication games in networks, Pure Nash equilibria in player-specific and weighted congestion games, The job shop scheduling problem: Conventional and new solution techniques, The relative complexity of NP search problems, Alternating minima and maxima, Nash equilibria and bounded arithmetic, Enhanced algorithms for local search, The complexity of finding fair independent sets in cycles, How long does it take for all users in a social network to choose their communities?, Characterising the intersection of QMA and coQMA, Combinatorial auctions with endowment effect, A comparison of heuristic algorithms for flow shop scheduling problems with setup times and limited batch size, Order preserving reductions and polynomial improving paths, Ordinal notations and well-orderings in bounded arithmetic, Genetic local search in combinatorial optimization, On total functions, existence theorems and computational complexity, A Sperner lemma complete for PPA, Timed network games, On local search for the generalized graph coloring problem, The NP Search Problems of Frege and Extended Frege Proofs, On the Complexity of Equilibrium Computation in First-Price Auctions, TFNP: An Update, Complexity of Single-Swap Heuristics for Metric Facility Location and Related Problems, Computing Stable Outcomes in Hedonic Games, Approximately Counting Locally-Optimal Structures, The Journey from NP to TFNP Hardness, Approximate counting and NP search problems, Unnamed Item, Global strategies for augmenting the efficiency of TSP heuristics, Integer Programming: Optimization and Evaluation Are Equivalent, A mini–max spanning forest approach to the political districting problem, Computing Approximate Nash Equilibria in Network Congestion Games with Polynomially Decreasing Cost Functions, Weighted Boolean Formula Games, General-Purpose Computation with Neural Networks: A Survey of Complexity Theoretic Results, Computing approximate Nash equilibria in network congestion games with polynomially decreasing cost functions, Sublinear-Time Algorithms for Tournament Graphs, Typical forcings, NP search problems and an extension of a theorem of Riis, NP-completeness: A retrospective, Pure Nash equilibria in a generalization of congestion games allowing resource failures, On the complexity of incremental computation, The complexity of searching implicit graphs, PPAD-complete approximate pure Nash equilibria in Lipschitz games, On parallel versus sequential approximation, Computing Stable Outcomes in Symmetric Additively Separable Hedonic Games, The price of anarchy in series-parallel network congestion games, On the minimum $s-t$ cut problem with budget constraints, The malleability of TSP 2Opt, Non-oblivious local search for graph and hypergraph coloring problems, A CSP-Based Approach for Solving Parity Game, Total functions in QMA, Non-interactive universal arguments, Approximation algorithms on $k$-correlation clustering, Simultaneous contests with equal sharing allocation of prizes: computational complexity and price of anarchy, Can local optimality be used for efficient data reduction?, Naturalism, tractability and the adaptive toolbox, On the Relative Complexity of 15 Problems Related to 0/1-Integer Programming, Hardness of Continuous Local Search: Query Complexity and Cryptographic Lower Bounds, Many-one reductions and the category of multivalued functions, Santa Claus Meets Hypergraph Matchings, Representing Fitness Landscapes by Valued Constraints to Understand the Complexity of Local Search, Linearizing Genomes: Exact Methods and Local Search, Spanning Tree Congestion and Computation of Generalized Györi-Lovász Partition, ARRIVAL: Next Stop in CLS, The classes PPA-$k$: existence from arguments modulo $k$, Hierarchical Network Formation Games, Quantum and classical query complexities of local search are polynomially related, INCOMPLETENESS IN THE FINITE DOMAIN, The complexity of searching succinctly represented graphs, Settling the Complexity of Local Max-Cut (Almost) Completely, COMPUTING NASH EQUILIBRIA FOR TWO-PLAYER RESTRICTED NETWORK CONGESTION GAMES IS $\mathcal{PLS}$-COMPLETE, The classes PPA-$k$: existence from arguments modulo $k$, POLYNOMIAL LOCAL SEARCH IN THE POLYNOMIAL HIERARCHY AND WITNESSING IN FRAGMENTS OF BOUNDED ARITHMETIC, Unnamed Item, Unnamed Item, Pure Nash equilibria in a generalization of congestion games allowing resource failures, Unnamed Item, On the Complexity of Local Search in Unconstrained Quadratic Binary Optimization, The Parameterized Complexity of k-Flip Local Search for SAT and MAX SAT, A Characterisation of Definable NP Search Problems in Peano Arithmetic, Adventures in monotone complexity and TFNP, Unique End of Potential Line, Dynamics of Profit-Sharing Games, The effectiveness of finite improvement algorithms for finding global optima, Improving TSP Tours Using Dynamic Programming over Tree Decompositions., Fully Polynomial-Time Approximation Schemes for Fair Rent Division, The Complexity of Necklace Splitting, Consensus-Halving, and Discrete Ham Sandwich

Cites Work