Simple Local Search Problems that are Hard to Solve
From MaRDI portal
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
(87)- Hardness of continuous local search: query complexity and cryptographic lower bounds
- Finding 3-swap-optimal independent sets and dominating sets is hard
- Approximate algorithms for generalized maximum utility problems
- Finding optimal subgraphs by local search
- On parallel versus sequential approximation
- Computing Stable Outcomes in Hedonic Games
- Timed network games
- Patience of matrix games
- Existence, computation and efficiency of Nash stable outcomes in hedonic skill 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
- Generalized graph \(k\)-coloring games
- On the complexity of local search for weighted standard set problems
- Separations in proof complexity and TFNP
- Finding 3-swap-optimal independent sets and dominating sets is hard
- Settling the complexity of local max-cut (almost) completely
- Complexity of single-swap heuristics for metric facility location and related problems
- Representing fitness landscapes by valued constraints to understand the complexity of local search
- 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
- Stability based on single-agent deviations in additively separable hedonic games
- Approximately counting locally-optimal structures
- Local search: simple, successful, but sometimes sluggish
- (Dis)assortative partitions on random regular graphs
- Generalized \(k\)-multiway cut problems
- Computing Nash equilibria for two-player restricted network congestion games is \(\mathcal{PLS}\)-complete
- Convergence to approximate Nash equilibria in congestion games
- Minimizing expectation plus variance
- Complexity and approximability of optimal resource allocation and Nash equilibrium over networks
- One-sided markets with externalities
- A variation of DS decomposition in set function optimization
- How easy is local search?
- Smoothed analysis with adaptive adversaries
- scientific article; zbMATH DE number 18531 (Why is no real title available?)
- Timed network games
- Ant algorithm with local search procedure for multiple knapsack problem
- A variable-depth search algorithm for the recursive bipartitioning of signal flow graphs
- Equilibria, fixed points, and complexity classes
- 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
- Unique end of potential line
- The complexity of Boolean constraint satisfaction local search problems
- Minimum stable cut and treewidth
- scientific article; zbMATH DE number 1488096 (Why is no real title available?)
- 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
- 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
- On the \(\mathcal {PLS}\)-complexity of maximum constraint assignment
- Linearizing genomes: exact methods and local search
- Pure Nash equilibria in a generalization of congestion games allowing resource failures
- Local Max-Cut on sparse graphs
- Continuous dynamical systems that realize discrete optimization on the hypercube
- A quadratic simplex algorithm for primal optimization over zero-one polytopes
- The k-Opt algorithm for the traveling salesman problem has exponential running time for k 5
- On the smoothed complexity of combinatorial local search
- On complexity of unconstrained hyperbolic 0--1 programming problems
- Pure Nash equilibria in a generalization of congestion games allowing resource failures
- Convergence and approximation in potential games
- Computational aspects of the colorful Carathéodory theorem
- General-Purpose Computation with Neural Networks: A Survey of Complexity Theoretic Results
- Partitioning problems via random processes
- Matrix representation and gradient flows for NP-hard problems
- Smoothed analysis of the squared Euclidean maximum-cut problem
- Pairwise-interaction games
- The malleability of TSP 2Opt
- Dynamics of Profit-Sharing Games
- Computing better approximate pure Nash equilibria in cut games via semidefinite programming
- The smoothed complexity of policy iteration for Markov decision processes
- Integer Programming: Optimization and Evaluation Are Equivalent
- Approximation of Constraint Satisfaction via local search
- Intersection classes in TFNP and proof complexity
- Hybrid Ant Colony Optimization Algorithms—Behaviour Investigation Based on Intuitionistic Fuzzy Logic
- On the quality of local search for the quadratic assignment problem
- Complexity of local search for the \(p\)-median problem
- Computing equilibria: a computational complexity perspective
- Approximately Counting Locally-Optimal Structures
- Computing Stable Outcomes in Symmetric Additively Separable Hedonic Games
- Global approximation of local optimality: nonsubmodular optimization
- A simple deterministic algorithm for symmetric submodular maximization subject to a knapsack constraint
- Topological distance games
- On the minimum \(s-t\) cut problem with budget constraints
- A note on the complexity of local search problems
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)
