| Autor: |
Chen, Lin, Lian, Jiayi, Mao, Yuchen, Zhang, Guochuan |
| Rok vydání: |
2023 |
| Předmět: |
|
| Druh dokumentu: |
Working Paper |
| Popis: |
We investigate polynomial-time approximation schemes for the classic 0-1 knapsack problem. The previous algorithm by Deng, Jin, and Mao (SODA'23) has approximation factor $1 + \eps$ with running time $\widetilde{O}(n + \frac{1}{\eps^{2.2}})$. There is a lower Bound of $(n + \frac{1}{\eps})^{2-o(1)}$ conditioned on the hypothesis that $(\min, +)$ has no truly subquadratic algorithm. We close the gap by proposing an approximation scheme that runs in $\widetilde{O}(n + \frac{1}{\eps^2})$ time. |
| Databáze: |
arXiv |
| Externí odkaz: |
|
