<p>For unweighted problems, The Nearest Codeword problem in coding theory is known to be very hard to approximate. It is <a href="http://theory.cs.uni-bonn.de/ftp/reports/cs-reports/2000/85221-CS.pdf" rel="noreferrer">NP-hard to approximate</a> to within
a factor $n^{ \Omega(1)/ \log \log n}$.</p>

<p>Another hard to approximate problem is the longest path problem in directed graphs. <a href="http://repository.upenn.edu/cgi/viewcontent.cgi?article=1202&amp;context=cis_papers" rel="noreferrer">Björklund, Husfeldt, and Khanna</a> 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$.</p>

<p>Also, Approximating <a href="http://link.springer.com/article/10.1007%2Fs00493-003-0019-y" rel="noreferrer">Closest Vector in a lattice</a> to within almost polynomial factors is NP-Hard.</p>

<p>Finally, <a href="http://www.sciencedirect.com/science/article/pii/0020019093900222" rel="noreferrer">minimum independent dominating set</a> of a graph is not approximable within $n^{1-\epsilon}$ for any $\epsilon \gt 0$.</p>

CC BY-SA 3.0
2013-06-12T07:47:18.200Z
2013-06-12T08:19:44.237Z
2013-06-12T08:19:44.237Z
Mohammad Al-Turkistany
<p>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.</p>

<hr>

<p>[1] <a href="http://toc.nada.kth.se/articles/v003a006/v003a006.pdf" rel="nofollow">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.</a></p>

CC BY-SA 3.0
2013-06-10T01:03:23.807Z
2013-06-10T18:36:32.053Z
2013-06-10T18:36:32.053Z
Juho
<p>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 <a href="http://www.eng.tau.ac.il/algs/tsp.pdf" rel="nofollow">exponential factors</a>.</p>

CC BY-SA 3.0
2013-06-10T03:34:13.727Z
My answer for the OP before the edit.
Mohammad Al-Turkistany
CC BY-SA 3.0
2013-06-10T02:54:48.203Z
2013-06-10T03:10:31.937Z
2013-06-10T03:10:31.937Z
Mohammad Al-Turkistany
<p>The title of this question does not match the content. As stated in the comments, there are some NP optimization problems for which <em>any</em> 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.</p>

<p>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 <a href="http://basepub.dauphine.fr/xmlui/bitstream/handle/123456789/4769/isaac04.pdf?sequence=2" rel="nofollow">this extended abstract</a>, you can see that the Maximum Independent Set problem is complete for polyAPX under PTAS reductions.</p>

<p>For more information on approximation-preserving reductions and approximability results, check out <a href="http://www.nada.kth.se/~viggo/wwwcompendium/" rel="nofollow">the compendium of NP optimization problems</a>.</p>

CC BY-SA 3.0
2013-06-10T17:44:41.323Z
2013-06-11T19:38:37.663Z
2013-06-11T19:38:37.663Z
argentpepper
<p>Under some assumptions, it is <a href="https://ieeexplore.ieee.org/document/548522" rel="nofollow noreferrer">hard to approximate MAX-CLIQUE</a> within a factor <span class="math-container">$n^{1-\epsilon}$</span> for any <span class="math-container">$\epsilon &gt;0$</span>. Are there any other problems that are known to be equally hard to approximate? I'm particularly interested in unweighted problems.</p>

CC BY-SA 3.0
2013-06-10T08:20:35.110Z
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.
Sasho Nikolov
CC BY-SA 3.0
2013-06-10T08:23:21.700Z
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?
Sasho Nikolov
CC BY-SA 3.0
2013-06-10T14:40:03.070Z
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.
Austin Buchanan
CC BY-SA 3.0
2013-06-10T14:47:28.057Z
If you think otherwise, please explain in an answer both your preferred notion of hardness and a list some 'hardest' problems.
Austin Buchanan
CC BY-SA 3.0
2013-06-10T15:52:47.177Z
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?
Sasho Nikolov
CC BY-SA 3.0
2013-06-10T16:06:13.277Z
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.
Austin Buchanan
<approximation-hardness><clique>
Hardest problems to approximate
Austin Buchanan
# Hardest problems to approximate

(Asked by: username_0 on 2013-06-10)

Under some assumptions, it is [hard to approximate MAX-CLIQUE](https://ieeexplore.ieee.org/document/548522) 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.

**Tags:** approximation-hardness, clique
> **Comments:**
> **username_1**: 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.  
> **username_1**: 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?  
> **username_0**: 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.  
> **username_0**: If you think otherwise, please explain in an answer both your preferred notion of hardness and a list some 'hardest' problems.  
> **username_1**: 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?  
> **username_0**: 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.  

---

## 4 answers

### Answer by username_2 on 2013-06-12. Score: 5 | Accepted answer

For unweighted problems, The Nearest Codeword problem in coding theory is known to be very hard to approximate. It is [NP-hard to approximate](http://theory.cs.uni-bonn.de/ftp/reports/cs-reports/2000/85221-CS.pdf) 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](http://repository.upenn.edu/cgi/viewcontent.cgi?article=1202&context=cis_papers) 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](http://link.springer.com/article/10.1007%2Fs00493-003-0019-y) to within almost polynomial factors is NP-Hard.

Finally, [minimum independent dominating set](http://www.sciencedirect.com/science/article/pii/0020019093900222) of a graph is not approximable within $n^{1-\epsilon}$ for any $\epsilon \gt 0$.


---

### Answer by username_3 on 2013-06-10. Score: 7

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.](http://toc.nada.kth.se/articles/v003a006/v003a006.pdf)


---

### Answer by username_2 on 2013-06-10. Score: 4

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](http://www.eng.tau.ac.il/algs/tsp.pdf).

> **Comments:**
> **username_2**: My answer for the OP before the edit.  

---

### Answer by username_4 on 2013-06-10. Score: 4

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](http://basepub.dauphine.fr/xmlui/bitstream/handle/123456789/4769/isaac04.pdf?sequence=2), 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](http://www.nada.kth.se/~viggo/wwwcompendium/).


---

