Questions tagged [approximation-hardness]
Hardness of approximation, aka inapproximability.
171
questions
67
votes
7answers
8k views
Are runtime bounds in P decidable? (answer: no)
The question asked is whether the following question is decidable:
Problem Given an integer $k$ and Turing machine $M$ promised to be in P, is the runtime of $M$ ${O}(n^k)$ with respect ...
27
votes
4answers
1k views
Compendium of the Best Approximation and Hardness Results for NP optimization problems
Do you know any up-to-date wiki dedicated to NP optimization problems with their best approximation and hardness result?
Based on the feedback, it seems that it is safe to assume there is not such a ...
17
votes
3answers
487 views
Why differential approximation ratios are not well-studied comparing to standard ones despite of their claimed benefits?
There is a standard approximation theory where the approximation ratio is $\sup\frac{A}{OPT}$ (for problems with $MIN$ objectives), $A$ - the value returned by some algorithm $A$ and $OPT$ - an ...
8
votes
1answer
673 views
Is MAX CUT approximation resistant?
CSP optimization problem is approximation resistant if it is $NP$-hard to beat the approximation factor of a random assignment. For instance, MAX 3-LIN is approximation resistant since a random ...
11
votes
2answers
286 views
Which 2P1R Games are Potentially Sharp?
Two-prover one-round (2P1R) games are an essential tool for hardness of approximation. Specifically, the parallel repetition of two-prover one-round games gives a way to increase the size of a gap in ...
8
votes
4answers
404 views
In-approximability results in severely restricted graph classes
Longest path problem is not polynomial-time approximable to any constant factor in cubic Hamiltonian graphs (Longest path $\notin APX$ unless $P=NP$). I don't know if it remains in-approximable in ...
8
votes
0answers
1k views
Is Exact Cover by Equally-Sized Sets reducible to Multi-Dimensional Matching in a certain nice way?
This question is motivated by my other question “Gap hardness of Multi-Dimensional Cover,” which is in turn motivated by the question “Set Cover for Permutation Matrices” by Brayden Ware.
Informal ...
10
votes
0answers
346 views
Gap hardness of Multi-Dimensional Cover
Given a finite set $X$ and a collection $F$ of subsets of $X$, we define a cover of $X$ in $F$ as a subset of $F$ whose union is equal to $X$. A cover $C$ of $X$ in $F$ is said to be exact if the ...
8
votes
2answers
716 views
Quantum PCP and hardness of simulating of Hamiltonians
I have a few questions about Quantum PCP conjecture:
What is the statement of the quantum PCP conjecture?
What implications would Quantum PCP theorem have for simulating of Hamiltonians?
Is it ...
20
votes
4answers
857 views
Examples of hardness phase transitions
Suppose we have a problem parameterized by a real-valued parameter p which is "easy" to solve when $p=p_0$ and "hard" when $p=p_1$ for some values $p_0$, $p_1$.
One example is counting spin ...
24
votes
3answers
2k views
Hardness of approximation - additive error
There is a rich literature and at least one very good book setting out the known hardness of approximation results for NP-hard problems in the context of multiplicative error (e.g. 2-approximation for ...
32
votes
4answers
847 views
Hardness of approximation assuming NP != coNP
Two of the common assumptions for proving hardness of approximation results are $P \neq NP$ and Unique Games Conjecture. Are there any hardness of approximation results assuming $NP \neq coNP$ ? I am ...
7
votes
1answer
661 views
Permanents - Approximation and connection to integer factorization
Given a non-negative integer matrix of size $n \times n$. If the permanent can be calculated in $n^{2}$ arithmetic operations but each operation is on word size $n^{k}$ bits for some constant $k$, ...
16
votes
3answers
556 views
UGC hardness of the predicate $NAE(x_1, …, x_\ell)$ for $x_i \in GF(k)$?
Background:
In Subhash Khot's original UGC paper (PDF), he proves the UG-hardness of deciding whether a given CSP instance with constraints all of the form Not-all-equal(a, b, c) over a ternary ...
8
votes
2answers
711 views
Approximation Algorithms for MAXSAT
Trying to find the optimal solution to WEIGHTED-MAX-3SAT, the weighted version of the 3-SAT optimization problem, is NP-hard. In fact, even approximating the non-weighted version of MAX-SAT ...
32
votes
1answer
2k views
Is Gap-3SAT NP-complete even for 3CNF formulas where no pair of variables appears in significantly more clauses than the average?
In this question, a 3CNF formula means a CNF formula where each clause involves exactly three distinct variables. For a constant 0<s<1, Gap-3SATs is the following promise problem:
Gap-3SATs
...
11
votes
2answers
692 views
Hardness of Vertex Separators
For a given graph $G$, the Separator Problem asks whether a vertex or edge set of small cardinality (or weight) exists whose removal partitions $G$ into two disjoint graphs of approximately equal ...
26
votes
3answers
951 views
When is relaxed counting hard?
Suppose we relax the problem of counting proper colorings by counting weighted colorings as follows: every proper coloring gets weight 1 and every improper coloring gets weight $c^v$ where $c$ is some ...
10
votes
2answers
451 views
Consequences of lower bounds for $\epsilon$-nets on approximation
Many here are probably aware of Alon's recent super-linear lower bounds for $\epsilon$-nets in a natural geometric setting [PDF]. I would like to know what, if anything, such a lower bound implies ...
22
votes
2answers
1k views
Polynomial time approximation algorithms for machine scheduling: how many open problems are left?
In 1999, Petra Schuurman and Gerhard J. Woeginger published the paper "Polynomial time approximation algorithms for machine scheduling: Ten open problems". Since then, to the best of my knowledge, ...
38
votes
9answers
3k views
Optimal greedy algorithms for NP-hard problems
Greed, for lack of a better word, is good. One of the first algorithmic paradigms taught in introductory algorithms course is the greedy approach. Greedy approach results in simple and intuitive ...
