<p>One example is <a href="http://en.wikipedia.org/wiki/Independent_set_%28graph_theory%29">Maximum Independent Set</a>. It is NP-hard to approximate the problem with ratio $n^{1-\epsilon}$ <a href="http://dx.doi.org/10.4086/toc.2007.v003a006">(Zuckerman, 2007)</a>. However, <a href="http://dx.doi.org/10.1016/j.dam.2011.07.009">Bourgeois et al. (2011)</a> 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.</p>

<p>Another example is the <a href="http://en.wikipedia.org/wiki/Graph_bandwidth">Bandwidth</a> problem. <a href="http://dx.doi.org/10.1007/3-540-44666-4_26">Dunagan &amp; Vempala (2001)</a> 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})$ <a href="http://dx.doi.org/10.1007/s00454-009-9135-9">(Lee, 2009)</a>; however, no $\omega(\sqrt{\log n / \log \log n})$ lower bound is known for the best approximation ratio achievable in polynomial time.</p>

CC BY-SA 3.0
2013-02-20T12:34:32.527Z
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
CC BY-SA 3.0
2013-02-20T10:41:06.857Z
2013-02-20T12:45:40.737Z
2013-02-20T12:45:40.737Z
Serge Gaspers
<p>This is motivated by my previous question, <a href="https://cstheory.stackexchange.com/questions/9350/super-polynomial-time-approximation-algorithms-for-max-3sat">Super-polynomial time approximation algorithms for MAX-3SAT</a>.
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).</p>

<p>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)}$)? </p>

<p>I would appreciate a survey of such results.</p>

<cc.complexity-theory><approximation-algorithms>
Super-polynomial time approximation algorithms for optimization problems
Mohammad Al-Turkistany
# Super-polynomial time approximation algorithms for optimization problems

(Asked by: username_0 on 2013-02-20)

This is motivated by my previous question, [Super-polynomial time approximation algorithms for MAX-3SAT](https://cstheory.stackexchange.com/questions/9350/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.

**Tags:** cc.complexity-theory, approximation-algorithms


---

## 1 answers

### Answer by username_1 on 2013-02-20. Score: 17 | Accepted answer

One example is [Maximum Independent Set](http://en.wikipedia.org/wiki/Independent_set_%28graph_theory%29). It is NP-hard to approximate the problem with ratio $n^{1-\epsilon}$ [(Zuckerman, 2007)](http://dx.doi.org/10.4086/toc.2007.v003a006). However, [Bourgeois et al. (2011)](http://dx.doi.org/10.1016/j.dam.2011.07.009) 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](http://en.wikipedia.org/wiki/Graph_bandwidth) problem. [Dunagan & Vempala (2001)](http://dx.doi.org/10.1007/3-540-44666-4_26) 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)](http://dx.doi.org/10.1007/s00454-009-9135-9); however, no $\omega(\sqrt{\log n / \log \log n})$ lower bound is known for the best approximation ratio achievable in polynomial time.

> **Comments:**
> **username_2**: 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}$.  

---

