This is motivated by my previous question, Super-polynomial time approximation algorithms for MAX-3SAT. For many optimization problems, for each one we have inapproximability lower bound $\alpha$ assuming some widely believed complexity theoretic conjecture. In other words, there is no polynomial time algorithm for such optimization problems with approximation ratio better than some $\alpha$ (different ratio $\alpha$ for each problem).

Are there optimization problems for which we can achieve approximation ratio better than $\alpha $ if we allow super-polynomial time algorithms? Can we achieve better approximation ratios using quasi-polynomial time algorithms ( $n^{O(\log n)}$) or even using sub-exponential time algorithms($2^{o(n)}$)?

I would appreciate a survey of such results.


1 Answer 1


One example is Maximum Independent Set. It is NP-hard to approximate the problem with ratio $n^{1-\epsilon}$ (Zuckerman, 2007). However, Bourgeois et al. (2011) give a simple $n^{1/2}$-approximation algorithm with running time $O^*(2^{\sqrt{n} \log n})$. Here, $n$ denotes the number of vertices of the input graph and the $O^*$-notation hides polynomial factors.

Another example is the Bandwidth problem. Dunagan & Vempala (2001) design an algorithm with approximation ratio $O(\log^3 n)$ and running time $O(n^{\log n})$. To my knowledge, the best known polynomial time approximation has approximation ratio $O(\log^3 n (\log \log n)^{1/4})$ (Lee, 2009); however, no $\omega(\sqrt{\log n / \log \log n})$ lower bound is known for the best approximation ratio achievable in polynomial time.

  • $\begingroup$ Actually, for bandwidth it seems that there is a super-constant inapproximability bound, especially if one is willing to assume that NP cannot be solved in quasi-polynomial time. The bound, given in "Hardness results for approximating the bandwidth" by Dubey, Feige, Unger (JCSS 2011), is $c\sqrt{\log n/\log\log n}$. $\endgroup$ Commented Feb 20, 2013 at 12:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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