|
| | | | |
| | | |
| Stat |
Members: 3645
Articles: 2'504'585
Articles rated: 2609
24 April 2024 |
|
| | | | |
|
Article overview
| |
|
|
Time-Approximation Trade-offs for Inapproximable Problems | | Édouard Bonnet
; Michael Lampis
; Vangelis Th. Paschos
; | | Date: |
20 Feb 2015 | | Abstract: | In this paper we focus on problems which do not admit a constant-factor
approximation in polynomial time and explore how quickly their approximability
improves as the allowed running time is gradually increased from polynomial to
(sub-)exponential.
We tackle a number of problems: For Min Independent Dominating Set, Max
Induced Path, Forest and Tree, for any $r(n)$, a simple, known scheme gives an
approximation ratio of $r$ in time roughly $r^{n/r}$. We show that, for most
values of $r$, if this running time could be significantly improved the ETH
would fail. For Max Minimal Vertex Cover we give a non-trivial
$sqrt{r}$-approximation in time $2^{n/r}$. We match this with a similarly
tight result. We also give a $log r$-approximation for Min ATSP in time
$2^{n/r}$ and an $r$-approximation for Max Grundy Coloring in time $r^{n/r}$.
Furthermore, we show that Min Set Cover exhibits a curious behavior in this
super-polynomial setting: for any $delta > 0$ it admits an
$m^delta$-approximation, where $m$ is the number of sets, in just
quasi-polynomial time. We observe that if such ratios could be achieved in
polynomial time, the ETH or the Projection Games Conjecture would fail. | | Source: | arXiv, 1502.5828 | | Services: | Forum | Review | PDF | Favorites | |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
browser Mozilla/5.0 AppleWebKit/537.36 (KHTML, like Gecko; compatible; ClaudeBot/1.0; +claudebot@anthropic.com)
|
| |
|
|
|
|
News, job offers and information for researchers and scientists:
| |
REGISTER