7
$\begingroup$

Under some assumptions, it is hard to approximate MAX-CLIQUE within a factor $n^{1-\epsilon}$ for any $\epsilon >0$. Are there any other problems that are known to be equally hard to approximate? I'm particularly interested in unweighted problems.

$\endgroup$
  • 5
    $\begingroup$ It's a bit unclear to me how you're hoping to get an apples to apples comparison. Are you asking for graph problems and $n$ is always the number of vertices? Is $n$ input size (I am not sure now if Hastad's proof works for sparse graphs, but I assume it does). Is $n$ the ratio between the smallest and largest solution of fixed size instances? Seems "unfair" to compare MaxCut, where all optimal solutions lie in $[|E|/2, |E|]$, and MaxClique. Notions like approximation resistance and advantage over random make more sense to me. $\endgroup$ – Sasho Nikolov Jun 10 '13 at 8:20
  • 5
    $\begingroup$ Moreover, there are problems, like discrepancy of a hypergraph, where determining if OPT is positive or 0 is hard. So the approximation ratio is infinite. Do such examples answer your question? $\endgroup$ – Sasho Nikolov Jun 10 '13 at 8:23
  • $\begingroup$ It does not necessarily have to be a graph problem. I think it is entirely fair to compare MAX-CLIQUE with MAX-CUT. MAX-CUT has a constant factor approximation. $\endgroup$ – Austin Buchanan Jun 10 '13 at 14:40
  • 1
    $\begingroup$ maybe MaxCut was a bad example. take Max-E3-SAT: there is a factor $7/8$ approximation, but it's entirely trivial because all optimal solutions are in $[7m/8, m]$. that aside, does every problem for which deciding OPT > 0 is NP-Hard automatically qualify as 'hardest to approximate' (approximation ratio is at least $\infty$) according to your criteria? $\endgroup$ – Sasho Nikolov Jun 10 '13 at 15:52
  • 2
    $\begingroup$ Fair enough. Perhaps we can restrict it to problems where the optimal solution belongs to {1,...,n}. Otherwise, I am not sure how to make the question precise and meaningful at the same time. $\endgroup$ – Austin Buchanan Jun 10 '13 at 16:06
4
$\begingroup$

For unweighted problems, The Nearest Codeword problem in coding theory is known to be very hard to approximate. It is NP-hard to approximate to within a factor $n^{ \Omega(1)/ \log \log n}$.

Another hard to approximate problem is the longest path problem in directed graphs. Björklund, Husfeldt, and Khanna showed that longest path in directed graphs is hard to approximate to within better than a $n^{1-\epsilon}$ factor for any $\epsilon \gt 0$.

Also, Approximating Closest Vector in a lattice to within almost polynomial factors is NP-Hard.

Finally, minimum independent dominating set of a graph is not approximable within $n^{1-\epsilon}$ for any $\epsilon \gt 0$.

$\endgroup$
7
$\begingroup$

A similar hardness result is known for the inapproximability of chromatic number [1]. Independent set is hard to approximate as well, since it is $\mathsf{MAX\text{-}CLIQUE}$ on the complement graph. Some problems that are easier to approximate include vertex cover, (connected) dominating set, feedback vertex set, TSP and Steiner tree.


[1] Zuckerman, David. "Linear degree extractors and the inapproximability of max clique and chromatic number." Proceedings of the thirty-eighth annual ACM symposium on Theory of computing. ACM, 2006.

$\endgroup$
4
$\begingroup$

Min TSP is harder to approximate than maximum clique. For the general case of Min TSP, it is hard to approximate the minimum weight of TSP within better than exponential factors.

$\endgroup$
  • $\begingroup$ My answer for the OP before the edit. $\endgroup$ – Mohammad Al-Turkistany Jun 10 '13 at 3:34
4
$\begingroup$

The title of this question does not match the content. As stated in the comments, there are some NP optimization problems for which any polynomial time approximation algorithm implies P = NP. Maybe you are looking for optimization problems that are not approximable within any polynomial factor, or that exhibit a threshold behavior? You may be looking for polyAPX-hard or polyAPX-complete problems.

polyAPX is the class of NP optimization problems that have a polynomial time approximation algorithm such that the measure of the approximate solution is within a polynomial factor of the optimal measure. In Theorem 2 of this extended abstract, you can see that the Maximum Independent Set problem is complete for polyAPX under PTAS reductions.

For more information on approximation-preserving reductions and approximability results, check out the compendium of NP optimization problems.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.