15
$\begingroup$

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<r(n)<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<\delta_1<1$ and $0<\delta_2<1$ are some fixed positive reals?

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}}$?

Improve this question
$\endgroup$
8
  • $\begingroup$ did you actually mean to ask for running time sublinear in the independent number? $\endgroup$
    – Sasho Nikolov
    Nov 4, 2013 at 2:49
  • $\begingroup$ 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}$. $\endgroup$
    – Turbo
    Nov 4, 2013 at 5:18
  • $\begingroup$ It should be $\delta_2$ in previous comment and we have $\alpha(G)<|V|<2^{|V|^{\delta_2}}<2^{|V|}$. $\endgroup$
    – Turbo
    Nov 4, 2013 at 5:26
  • $\begingroup$ I think I had typos before. $\endgroup$
    – Turbo
    Nov 4, 2013 at 5:41
  • $\begingroup$ Is it Clear now? $\endgroup$
    – Turbo
    Nov 4, 2013 at 5:41

2 Answers 2

Reset to default
10
$\begingroup$

One paper that gives an answer to this question is Chalermsook, Laekhanukit, & Nanongkai (2013).

There are also related works in the context of Fixed Parameter Tractability such as Hajiaghayi, Khandekar, & Kortsarz (2013) and Chitnis, Hajiaghayi, Kortsarz (2013). These hardness results are proven under various assumptions such as ETH or existence of very strong PCPs.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ 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)}$? $\endgroup$
    – Turbo
    Nov 4, 2013 at 0:14
3
$\begingroup$

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 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)})$.

Improve this answer
$\endgroup$

Your Answer

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

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