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
(95)- 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
- Minimum stable cut and treewidth
- 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)
