Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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.

share|improve this question
add comment

1 Answer 1

up vote 16 down vote accepted

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.

share|improve this answer
    
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}$. –  Michael Lampis Feb 20 '13 at 12:34
    
Thanks, @MichaelLampis. I updated the answer. –  Serge Gaspers Feb 20 '13 at 12:47
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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