Tight Bounds on Subexponential Time Approximation of Set Cover and Related Problems
We show that Set Cover on instances with $N$ elements cannot be approximated within $(1-γ)\ln N$-factor in time exp($N^{γ-δ})$, for any $0 < γ< 1$ and any $δ> 0$, assuming the Exponential Time Hypothesis. This essentially matches the best upper bound known by Cygan et al.\ (IPL, 2009) of $(1-γ)\ln N...
保存先:
| 主要な著者: | , , |
|---|---|
| フォーマット: | 論文 |
| 出版事項: |
2020
|
| 主題: | |
| オンライン･アクセス: | https://arxiv.org/abs/2008.05374 http://arxiv.org/abs/2008.05374 |
| タグ: |
タグなし, このレコードへの初めてのタグを付けませんか!
|