Simple Local Search Problems that are Hard to Solve

DOI10.1137/0220004zbMATH Open0716.68048OpenAlexW2062459871MaRDI QIDQ3204045FDOQ3204045

Alejandro A. Schäffer, Mihalis Yannakakis

Publication date: 1991

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0220004

Recommendations

A note on the complexity of local search problems
Local search: complexity and approximation
Local search and the local structure of NP-complete problems
scientific article; zbMATH DE number 5159135
Local search inequalities
scientific article; zbMATH DE number 1016966
Local search, reducibility and approximability of NP-optimization problems
scientific article; zbMATH DE number 1783857
Local search heuristics for combinatorial optimization problems

zbMATH Keywords

algorithms local search complexity theory graph partitioning satisfiability max-cut local optimum connectionist network

Mathematics Subject Classification ID

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

Cited In (69)

COMPUTING NASH EQUILIBRIA FOR TWO-PLAYER RESTRICTED NETWORK CONGESTION GAMES IS $\mathcal{PLS}$-COMPLETE
Approximate algorithms for generalized maximum utility problems
Pairwise-Interaction Games
On parallel versus sequential approximation
Finding optimal subgraphs by local search
Complexity and Approximability of Optimal Resource Allocation and Nash Equilibrium over Networks
Computing Stable Outcomes in Hedonic Games
Smoothed Analysis of the Squared Euclidean Maximum-Cut Problem
Timed network games
Patience of matrix games
Generalized graph $k$-coloring games
Computing with truly asynchronous threshold logic networks
Generalizations of Opt P to the polynomial hierarchy
On local search for the generalized graph coloring problem
Complexity of single-swap heuristics for metric facility location and related problems
Are analog neural networks better than binary neural networks?
Complexity of uniqueness and local search in quadratic 0-1 programming
Symmetries and the complexity of pure Nash equilibrium
Approximately counting locally-optimal structures
Generalized $k$-multiway cut problems
Convergence to approximate Nash equilibria in congestion games
Minimizing expectation plus variance
A variation of DS decomposition in set function optimization
How easy is local search?
Title not available (Why is that?)
A variable-depth search algorithm for the recursive bipartitioning of signal flow graphs
Equilibria, fixed points, and complexity classes
Unique end of potential line
Title not available (Why is that?)
The complexity of Boolean constraint satisfaction local search problems
Hardness of Continuous Local Search: Query Complexity and Cryptographic Lower Bounds
Settling the Complexity of Local Max-Cut (Almost) Completely
Simultaneous contests with equal sharing allocation of prizes: computational complexity and price of anarchy
On Finding and Verifying Locally Optimal Solutions
Satisfactory graph partition, variants, and generalizations
Pure Nash equilibria in a generalization of congestion games allowing resource failures
Continuous dynamical systems that realize discrete optimization on the hypercube
On complexity of unconstrained hyperbolic 0--1 programming problems
General-Purpose Computation with Neural Networks: A Survey of Complexity Theoretic Results
Convergence and approximation in potential games
Computational aspects of the colorful Carathéodory theorem
Matrix representation and gradient flows for NP-hard problems
The malleability of TSP 2Opt
Dynamics of Profit-Sharing Games
Integer Programming: Optimization and Evaluation Are Equivalent
On the quality of local search for the quadratic assignment problem
Representing Fitness Landscapes by Valued Constraints to Understand the Complexity of Local Search
Approximately Counting Locally-Optimal Structures
Complexity of local search for the $p$-median problem
Computing equilibria: a computational complexity perspective
Linearizing Genomes: Exact Methods and Local Search
Computing Stable Outcomes in Symmetric Additively Separable Hedonic Games
A simple deterministic algorithm for symmetric submodular maximization subject to a knapsack constraint
Title not available (Why is that?)
A note on the complexity of local search problems
Short sequences of improvement moves lead to approximate equilibria in constraint satisfaction games
Stability based on single-agent deviations in additively separable hedonic games
(Dis)assortative partitions on random regular graphs
Complexity of Single-Swap Heuristics for Metric Facility Location and Related Problems
Mixed integer bilevel optimization with a $k$-optimal follower: a hierarchy of bounds
A quadratic simplex algorithm for primal optimization over zero-one polytopes
Pure Nash equilibria in a generalization of congestion games allowing resource failures
Partitioning problems via random processes
Computing better approximate pure Nash equilibria in cut games via semidefinite programming
The smoothed complexity of policy iteration for Markov decision processes
Approximation of Constraint Satisfaction via local search
Hybrid Ant Colony Optimization Algorithms—Behaviour Investigation Based on Intuitionistic Fuzzy Logic
Topological distance games
On the minimum $s-t$ cut problem with budget constraints

This page was built for publication: Simple Local Search Problems that are Hard to Solve

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3204045)