Simple Local Search Problems that are Hard to Solve
From MaRDI portal
Publication:3204045
DOI10.1137/0220004zbMath0716.68048OpenAlexW2062459871MaRDI QIDQ3204045
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
algorithmslocal searchgraph partitioningsatisfiabilitycomplexity theorymax-cutlocal optimumconnectionist network
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Combinatorial optimization (90C27)
Related Items
Complexity of Single-Swap Heuristics for Metric Facility Location and Related Problems, Computing Stable Outcomes in Hedonic Games, Complexity of single-swap heuristics for metric facility location and related problems, Approximately counting locally-optimal structures, Approximately Counting Locally-Optimal Structures, Smoothed Analysis of the Squared Euclidean Maximum-Cut Problem, Approximation of Constraint Satisfaction via local search, Computing equilibria: a computational complexity perspective, Integer Programming: Optimization and Evaluation Are Equivalent, General-Purpose Computation with Neural Networks: A Survey of Complexity Theoretic Results, Matrix representation and gradient flows for NP-hard problems, A variable-depth search algorithm for the recursive bipartitioning of signal flow graphs, Are analog neural networks better than binary neural networks?, On the quality of local search for the quadratic assignment problem, Pure Nash equilibria in a generalization of congestion games allowing resource failures, A variation of DS decomposition in set function optimization, Finding optimal subgraphs by local search, 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, Computing Stable Outcomes in Symmetric Additively Separable Hedonic Games, Topological distance games, On the minimum \(s-t\) cut problem with budget constraints, The malleability of TSP 2Opt, Unique end of potential line, Simultaneous contests with equal sharing allocation of prizes: computational complexity and price of anarchy, Minimizing expectation plus variance, A quadratic simplex algorithm for primal optimization over zero-one polytopes, Convergence to approximate Nash equilibria in congestion games, A simple deterministic algorithm for symmetric submodular maximization subject to a knapsack constraint, Hardness of Continuous Local Search: Query Complexity and Cryptographic Lower Bounds, Convergence and approximation in potential games, Patience of matrix games, Equilibria, fixed points, and complexity classes, Representing Fitness Landscapes by Valued Constraints to Understand the Complexity of Local Search, Complexity of local search for the \(p\)-median problem, Linearizing Genomes: Exact Methods and Local Search, A note on the complexity of local search problems, Pairwise-Interaction Games, Settling the Complexity of Local Max-Cut (Almost) Completely, Generalizations of Opt P to the polynomial hierarchy, COMPUTING NASH EQUILIBRIA FOR TWO-PLAYER RESTRICTED NETWORK CONGESTION GAMES IS $\mathcal{PLS}$-COMPLETE, Computational aspects of the colorful Carathéodory theorem, Complexity of uniqueness and local search in quadratic 0-1 programming, Short sequences of improvement moves lead to approximate equilibria in constraint satisfaction games, Satisfactory graph partition, variants, and generalizations, The complexity of Boolean constraint satisfaction local search problems, On complexity of unconstrained hyperbolic 0--1 programming problems, Continuous dynamical systems that realize discrete optimization on the hypercube, Generalized \(k\)-multiway cut problems, Approximate algorithms for generalized maximum utility problems, Generalized graph \(k\)-coloring games, Pure Nash equilibria in a generalization of congestion games allowing resource failures, Symmetries and the complexity of pure Nash equilibrium, Unnamed Item, Computing with truly asynchronous threshold logic networks, Dynamics of Profit-Sharing Games, Complexity and Approximability of Optimal Resource Allocation and Nash Equilibrium over Networks, Timed network games, (Dis)assortative partitions on random regular graphs, On local search for the generalized graph coloring problem
