On Unapproximable Versions of $NP$-Complete Problems
From MaRDI portal
Publication:5691296
DOI10.1137/S0097539794266407zbMath0864.68039MaRDI QIDQ5691296
Publication date: 9 June 1997
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Analysis of algorithms and problem complexity (68Q25) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Theory of computing (68Q99)
Related Items
Towards optimal lower bounds for clique and chromatic number. ⋮ \(\#\)BIS-hardness for 2-spin systems on bipartite bounded degree graphs in the tree non-uniqueness region ⋮ Approximately counting locally-optimal structures ⋮ Approximately Counting Locally-Optimal Structures ⋮ From the quantum approximate optimization algorithm to a quantum alternating operator ansatz ⋮ Shortest Path and Maximum Flow Problems in Networks with Additive Losses and Gains ⋮ Unnamed Item ⋮ From typical sequences to typical genotypes ⋮ The Complexity of Approximately Counting Tree Homomorphisms ⋮ Shortest path and maximum flow problems in networks with additive losses and gains ⋮ Commuting quantum circuits and complexity of Ising partition functions ⋮ The Complexity of Aggregates over Extractions by Regular Expressions ⋮ From Gap-Exponential Time Hypothesis to Fixed Parameter Tractable Inapproximability: Clique, Dominating Set, and More ⋮ The complexity of approximately counting stable roommate assignments ⋮ Inapproximability of the Tutte polynomial ⋮ Approximately counting paths and cycles in a graph ⋮ Counting substrate cycles in topologically restricted metabolic networks ⋮ Fast parallel heuristics for the job shop scheduling problem ⋮ More efficient queries in PCPs for NP and improved approximation hardness of maximum CSP ⋮ Two simulated annealing-based heuristics for the job shop scheduling problem ⋮ Counting Hamiltonian cycles on quartic 4-vertex-connected planar graphs ⋮ Clique is hard to approximate within \(n^{1-\epsilon}\) ⋮ Parallel approximation schemes for a class of planar and near planar combinatorial optimization problems.
