Simple Local Search Problems that are Hard to Solve

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

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

Cited in

(94)

Symmetries and the complexity of pure Nash equilibrium
How easy is local search?
Are analog neural networks better than binary neural networks?
Generalizations of Opt P to the polynomial hierarchy
Complexity of uniqueness and local search in quadratic 0-1 programming
Computing with truly asynchronous threshold logic networks
On the quality of local search for the quadratic assignment problem
Finding optimal subgraphs by local search
Complexity of single-swap heuristics for metric facility location and related problems
The complexity of Boolean constraint satisfaction local search problems
On complexity of unconstrained hyperbolic 0--1 programming problems
On local search for the generalized graph coloring problem
Matrix representation and gradient flows for NP-hard problems
A variable-depth search algorithm for the recursive bipartitioning of signal flow graphs
On the \(\mathcal {PLS}\)-complexity of maximum constraint assignment
Computational aspects of the colorful Carathéodory theorem
Timed network games
A variation of DS decomposition in set function optimization
Unique end of potential line
A simple deterministic algorithm for symmetric submodular maximization subject to a knapsack constraint
Patience of matrix games
Continuous dynamical systems that realize discrete optimization on the hypercube
Generalized \(k\)-multiway cut problems
Pure Nash equilibria in a generalization of congestion games allowing resource failures
Approximately counting locally-optimal structures
Pairwise-interaction games
Settling the complexity of local max-cut (almost) completely
Computing Stable Outcomes in Hedonic Games
Integer Programming: Optimization and Evaluation Are Equivalent
Linearizing genomes: exact methods and local search
Approximately Counting Locally-Optimal Structures
Smoothed analysis of the squared Euclidean maximum-cut problem
On Finding and Verifying Locally Optimal Solutions
On the complexity of local search for weighted standard set problems
Local search: simple, successful, but sometimes sluggish
scientific article; zbMATH DE number 18531 (Why is no real title available?)
On the hardness of global and local approximation
Convergence and approximation in potential games
Approximate algorithms for generalized maximum utility problems
scientific article; zbMATH DE number 1488096 (Why is no real title available?)
Equilibria, fixed points, and complexity classes
General-Purpose Computation with Neural Networks: A Survey of Complexity Theoretic Results
Dynamics of Profit-Sharing Games
Approximation of Constraint Satisfaction via local search
Computing Stable Outcomes in Symmetric Additively Separable Hedonic Games
Timed network games
Hardness of continuous local search: query complexity and cryptographic lower bounds
Representing fitness landscapes by valued constraints to understand the complexity of local search
Complexity of Single-Swap Heuristics for Metric Facility Location and Related Problems
Computing Nash equilibria for two-player restricted network congestion games is \(\mathcal{PLS}\)-complete
Complexity and approximability of optimal resource allocation and Nash equilibrium over networks
(Dis)assortative partitions on random regular graphs
Generalized graph k-coloring games
On parallel versus sequential approximation
Mixed integer bilevel optimization with a k-optimal follower: a hierarchy of bounds
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
The malleability of TSP 2Opt
Pure Nash equilibria in a generalization of congestion games allowing resource failures
Simultaneous contests with equal sharing allocation of prizes: computational complexity and price of anarchy
A quadratic simplex algorithm for primal optimization over zero-one polytopes
Convergence to approximate Nash equilibria in congestion games
Computing better approximate pure Nash equilibria in cut games via semidefinite programming
The smoothed complexity of policy iteration for Markov decision processes
Finding 3-swap-optimal independent sets and dominating sets is hard
Stability based on single-agent deviations in additively separable hedonic games
Partitioning problems via random processes
A note on the complexity of local search problems
Node-max-cut and the complexity of equilibrium in linear weighted congestion games
Existence and complexity of approximate equilibria in weighted congestion games
Dynamic debt swapping in financial networks
The k-Opt algorithm for the traveling salesman problem has exponential running time for k 5
On the smoothed complexity of combinatorial local search
Intersection classes in TFNP and proof complexity
Global approximation of local optimality: nonsubmodular optimization
Existence, computation and efficiency of Nash stable outcomes in hedonic skill games
Separations in proof complexity and TFNP
Finding 3-swap-optimal independent sets and dominating sets is hard
One-sided markets with externalities
Ant algorithm with local search procedure for multiple knapsack problem
Smoothed analysis with adaptive adversaries
Minimum stable cut and treewidth
Local Max-Cut on sparse graphs
Complexity of local search for Euclidean clustering problems
From worst case to the average: structural guarantees in k-CSP approximation via orthogonal arrays
The complexity of symmetric bimatrix games with common payoffs
On the performance of mildly greedy players in k-coloring games
PLS-completeness of string permutations
Settling the complexity of Nash equilibrium in congestion games
Computing equilibria: a computational complexity perspective
Minimizing expectation plus variance
Complexity of local search for the \(p\)-median problem
Satisfactory graph partition, variants, and generalizations

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)