$(1-ε)$-Approximation of Knapsack in Nearly Quadratic Time
Fuente:
arXiv
Guardado en:
| Autor principal: | |
|---|---|
| Formato: | Preprint |
| Publicado: |
2023
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866908482627698688 |
|---|---|
| author | Mao, Xiao |
| author_facet | Mao, Xiao |
| contents | Knapsack is one of the most fundamental problems in theoretical computer science. In the $(1 - ε)$-approximation setting, although there is a fine-grained lower bound of $(n + 1 / ε) ^ {2 - o(1)}$ based on the $(\min, +)$-convolution hypothesis ([K{ü}nnemann, Paturi and Stefan Schneider, ICALP 2017] and [Cygan, Mucha, Wegrzycki and Wlodarczyk, 2017]), the best algorithm is randomized and runs in $\tilde O\left(n + (\frac{1}ε)^{11/5}/2^{Ω(\sqrt{\log(1/ε)})}\right)$ time [Deng, Jin and Mao, SODA 2023], and it remains an important open problem whether an algorithm with a running time that matches the lower bound (up to a sub-polynomial factor) exists. We answer the question positively by showing a deterministic $(1 - ε)$-approximation scheme for knapsack that runs in $\tilde O(n + (1 / ε) ^ {2})$ time. We first extend a known lemma in a recursive way to reduce the problem to $n ε$-additive approximation for $n$ items with profits in $[1, 2)$. Then we give a simple efficient geometry-based algorithm for the reduced problem. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2308_07004 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | $(1-ε)$-Approximation of Knapsack in Nearly Quadratic Time Mao, Xiao Data Structures and Algorithms Knapsack is one of the most fundamental problems in theoretical computer science. In the $(1 - ε)$-approximation setting, although there is a fine-grained lower bound of $(n + 1 / ε) ^ {2 - o(1)}$ based on the $(\min, +)$-convolution hypothesis ([K{ü}nnemann, Paturi and Stefan Schneider, ICALP 2017] and [Cygan, Mucha, Wegrzycki and Wlodarczyk, 2017]), the best algorithm is randomized and runs in $\tilde O\left(n + (\frac{1}ε)^{11/5}/2^{Ω(\sqrt{\log(1/ε)})}\right)$ time [Deng, Jin and Mao, SODA 2023], and it remains an important open problem whether an algorithm with a running time that matches the lower bound (up to a sub-polynomial factor) exists. We answer the question positively by showing a deterministic $(1 - ε)$-approximation scheme for knapsack that runs in $\tilde O(n + (1 / ε) ^ {2})$ time. We first extend a known lemma in a recursive way to reduce the problem to $n ε$-additive approximation for $n$ items with profits in $[1, 2)$. Then we give a simple efficient geometry-based algorithm for the reduced problem. |
| title | $(1-ε)$-Approximation of Knapsack in Nearly Quadratic Time |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2308.07004 |