<p>One paper that gives an answer to this question is <a href="http://arxiv.org/pdf/1308.2617v2.pdf">Chalermsook, Laekhanukit, &amp; Nanongkai (2013)</a>.</p>

<p>There are also related works in the context of Fixed Parameter Tractability such as
<a href="http://arxiv.org/pdf/1310.2711v1.pdf">Hajiaghayi, Khandekar, &amp; Kortsarz (2013)</a> and <a href="http://arxiv.org/pdf/1308.3520v1.pdf">Chitnis, Hajiaghayi, Kortsarz (2013)</a>.
These hardness results are proven under various assumptions such as ETH or existence of very strong PCPs.</p>

CC BY-SA 3.0
2013-11-04T00:14:34.913Z
http://arxiv.org/pdf/1308.2617v2.pdf says "For any $r$ larger than some constant, any $r$-approximation algorithm for the maximum independent set problem must run in at least $2^{{n^{1-\epsilon}}/{r^{1+\epsilon}}}$ time. This nearly matches the upper bound of $2^{n/r}$". So approximation ratio $r=2^{({s(n)n})^{\delta_1}}$ can be achieved in $2^{2^{r(n)n - ({s(n)n})^{\delta_1}}} = 2^{2^{1 - \frac{({s(n)n})^{\delta_1}}{r(n)n}r(n)n}}=2^{2^{\delta_2 r(n)n}}$ time for some $\delta_2 >1 - \frac{({s(n)})^{\delta_1}{n}^{\delta_1-1}}{r(n)}$?
Turbo
CC BY-SA 3.0
2013-11-03T19:49:46.917Z
2014-03-15T00:07:18.063Z
2014-03-15T00:07:18.063Z
Igor Shinkar
<p>You have many $FPA$ (fixed parameter approximation) algorithms for which a sublinear parameter translates into subexponential time in the length of the input.</p>

<p>For example, <a href="http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=918B7428BAD06428C58DFF7CEF62BEBE?doi=10.1.1.146.408&amp;rep=rep1&amp;type=pdf" rel="nofollow">approximating the number of simple paths</a> of length $k$, for some $k=n^c$ (where $c&lt;1$), gives you a running time of:</p>

<p>$O((2e)^{n^c}\cdot 2^{polylog(n)})$.</p>

CC BY-SA 3.0
2014-03-15T08:27:40.587Z
2014-03-15T09:35:59.747Z
2014-03-15T09:35:59.747Z
R B
<p>There are studies about approximation algorithms for NP complete problems in Polynomial time and exact algorithms in exponential time. Are there studies about approximation algorithms for NP complete problems in subexponential time of form $2^{n^{\delta_2}}$ where $\delta_2\in(0,1)$?</p>

<p>I am particularly interested in what is known about hard to polynomial time approximable problems such as Independence number and Clique number in subexponential time? Note that ETH only prohibits exact computation in such a time frame. Say Independence number is $\alpha(G)=2^{r(n)n}$ on a graph with vertex count $|V|=2^{s(n)n}$ for some $0&lt;r(n)&lt;s(n)$. Is an $2^{(r(n)n)^{\delta_1}}$-factor approximation scheme possible for Independence number in time $2^{|V|^{\delta_2}}=2^{2^{\delta_2s(n) n}}$ where $0&lt;\delta_1&lt;1$ and $0&lt;\delta_2&lt;1$ are some fixed positive reals?</p>

<p>That is for every $\delta_1\in(0,1)$ is there a $\delta_2\in (0,1)$ such that $\alpha(G)$ can be approximated within $2^{\log_2^{\delta_1}(\alpha(G))}=2^{(r(n)n)^{\delta_1}}$ factor in time $2^{|V|^{\delta_2}}=2^{2^{\delta_2s(n) n}}$? </p>

CC BY-SA 3.0
2013-11-04T02:49:56.517Z
did you actually mean to ask for running time sublinear in the independent number?
Sasho Nikolov
CC BY-SA 3.0
2013-11-04T05:18:28.630Z
No, running time is sub-exponential. Fully exponential would be $2^{|V|}$. Here running time is of form $2^{|V|^{\delta_1}}$ and here $\alpha(G)=2^{r(n)n}=|V|^{\frac{r(n)}{s(n)}}<|V|=2^{s(n)n}$.
Turbo
CC BY-SA 3.0
2013-11-04T05:26:06.963Z
It should be $\delta_2$ in previous comment and we have $\alpha(G)<|V|<2^{|V|^{\delta_2}}<2^{|V|}$.
Turbo
CC BY-SA 3.0
2013-11-04T05:41:04.353Z
I think I had typos before.
Turbo
CC BY-SA 3.0
2013-11-04T05:41:53.453Z
Is it Clear now?
Turbo
CC BY-SA 3.0
2013-11-04T05:49:14.163Z
yes, it is clear
Sasho Nikolov
CC BY-SA 3.0
2013-11-04T05:51:46.927Z
Is my comment below that approximation ratio $r=2^{({s(n)n})^{\delta_1}}$ can be achieved in $2^{2^{r(n)n -({s(n)n})^{\delta_1}}} = 2^{2^{(1 - \frac{({s(n)n})^{\delta_1}}{r(n)n})r(n)n}}=2^{2^{\delta_2 r(n)n}}$ time for some $\delta_2 >1 - \frac{({s(n)})^{\delta_1}{n}^{\delta_1-1}}{r(n)}$ correct? Is $\delta_2<1$ for every $\delta_1<1$?
Turbo
CC BY-SA 3.0
2013-11-04T06:03:52.503Z
comment below to Igor Shinkar's answer.
Turbo
<approximation-algorithms><approximation-hardness>
Approximation in subexponental time
Turbo
# Approximation in subexponental time

(Asked by: username_0 on 2013-11-03)

There are studies about approximation algorithms for NP complete problems in Polynomial time and exact algorithms in exponential time. Are there studies about approximation algorithms for NP complete problems in subexponential time of form $2^{n^{\delta\_2}}$ where $\delta\_2\in(0,1)$?

I am particularly interested in what is known about hard to polynomial time approximable problems such as Independence number and Clique number in subexponential time? Note that ETH only prohibits exact computation in such a time frame. Say Independence number is $\alpha(G)=2^{r(n)n}$ on a graph with vertex count $|V|=2^{s(n)n}$ for some $0

That is for every $\delta\_1\in(0,1)$ is there a $\delta\_2\in (0,1)$ such that $\alpha(G)$ can be approximated within $2^{\log\_2^{\delta\_1}(\alpha(G))}=2^{(r(n)n)^{\delta\_1}}$ factor in time $2^{|V|^{\delta\_2}}=2^{2^{\delta\_2s(n) n}}$?

**Tags:** approximation-algorithms, approximation-hardness

> **Comments:**
> **username_1**: did you actually mean to ask for running time sublinear in the independent number?  
> **username_0**: No, running time is sub-exponential. Fully exponential would be $2^{|V|}$. Here running time is of form $2^{|V|^{\delta_1}}$ and here $\alpha(G)=2^{r(n)n}=|V|^{\frac{r(n)}{s(n)}}<|V|=2^{s(n)n}$.  
> **username_0**: It should be $\delta_2$ in previous comment and we have $\alpha(G)<|V|<2^{|V|^{\delta_2}}<2^{|V|}$.  
> **username_0**: I think I had typos before.  
> **username_0**: Is it Clear now?  
> **username_1**: yes, it is clear  
> **username_0**: Is my comment below that approximation ratio $r=2^{({s(n)n})^{\delta_1}}$ can be achieved in $2^{2^{r(n)n -({s(n)n})^{\delta_1}}} = 2^{2^{(1 - \frac{({s(n)n})^{\delta_1}}{r(n)n})r(n)n}}=2^{2^{\delta_2 r(n)n}}$ time for some $\delta_2 >1 - \frac{({s(n)})^{\delta_1}{n}^{\delta_1-1}}{r(n)}$ correct? Is $\delta_2<1$ for every $\delta_1<1$?  
> **username_0**: comment below to username_2's answer.  

---

## 2 answers

### Answer by username_2 on 2013-11-03. Score: 10

One paper that gives an answer to this question is [Chalermsook, Laekhanukit, & Nanongkai (2013)](http://arxiv.org/pdf/1308.2617v2.pdf).

There are also related works in the context of Fixed Parameter Tractability such as
[Hajiaghayi, Khandekar, & Kortsarz (2013)](http://arxiv.org/pdf/1310.2711v1.pdf) and [Chitnis, Hajiaghayi, Kortsarz (2013)](http://arxiv.org/pdf/1308.3520v1.pdf).
These hardness results are proven under various assumptions such as ETH or existence of very strong PCPs.

> **Comments:**
> **username_0**: http://arxiv.org/pdf/1308.2617v2.pdf says "For any $r$ larger than some constant, any $r$-approximation algorithm for the maximum independent set problem must run in at least $2^{{n^{1-\epsilon}}/{r^{1+\epsilon}}}$ time. This nearly matches the upper bound of $2^{n/r}$". So approximation ratio $r=2^{({s(n)n})^{\delta_1}}$ can be achieved in $2^{2^{r(n)n - ({s(n)n})^{\delta_1}}} = 2^{2^{1 - \frac{({s(n)n})^{\delta_1}}{r(n)n}r(n)n}}=2^{2^{\delta_2 r(n)n}}$ time for some $\delta_2 >1 - \frac{({s(n)})^{\delta_1}{n}^{\delta_1-1}}{r(n)}$?  

---

### Answer by username_3 on 2014-03-15. Score: 3

You have many $FPA$ (fixed parameter approximation) algorithms for which a sublinear parameter translates into subexponential time in the length of the input.

For example, [approximating the number of simple paths](http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=918B7428BAD06428C58DFF7CEF62BEBE?doi=10.1.1.146.408&rep=rep1&type=pdf) of length $k$, for some $k=n^c$ (where $c<1$), gives you a running time of:

$O((2e)^{n^c}\cdot 2^{polylog(n)})$.


---

