A Note on Deterministic FPTAS for Partition
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866910794486120448 |
|---|---|
| author | Chen, Lin Lian, Jiayi Mao, Yuchen Zhang, Guochuan |
| author_facet | Chen, Lin Lian, Jiayi Mao, Yuchen Zhang, Guochuan |
| contents | We consider the Partition problem and propose a deterministic FPTAS (Fully Polynomial-Time Approximation Scheme) that runs in $\widetilde{O}(n + 1/\varepsilon)$-time. This is the best possible (up to a polylogarithmic factor) assuming the Strong Exponential Time Hypothesis~[Abboud, Bringmann, Hermelin, and Shabtay'22]. Prior to our work, only a randomized algorithm can achieve a running time of $\widetilde{O}(n + 1/\varepsilon)$~[Chen, Lian, Mao and Zhang '24], while the best deterministic algorithm runs in $\widetilde{O}(n+1/\varepsilon^{5/4})$ time~[Deng, Jin and Mao '23] and [Wu and Chen '22]. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2501_12848 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | A Note on Deterministic FPTAS for Partition Chen, Lin Lian, Jiayi Mao, Yuchen Zhang, Guochuan Data Structures and Algorithms We consider the Partition problem and propose a deterministic FPTAS (Fully Polynomial-Time Approximation Scheme) that runs in $\widetilde{O}(n + 1/\varepsilon)$-time. This is the best possible (up to a polylogarithmic factor) assuming the Strong Exponential Time Hypothesis~[Abboud, Bringmann, Hermelin, and Shabtay'22]. Prior to our work, only a randomized algorithm can achieve a running time of $\widetilde{O}(n + 1/\varepsilon)$~[Chen, Lian, Mao and Zhang '24], while the best deterministic algorithm runs in $\widetilde{O}(n+1/\varepsilon^{5/4})$ time~[Deng, Jin and Mao '23] and [Wu and Chen '22]. |
| title | A Note on Deterministic FPTAS for Partition |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2501.12848 |