0
[2402.11426] Approximating Partition in Near-Linear Time
source link: https://arxiv.org/abs/2402.11426
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
Computer Science > Data Structures and Algorithms
[Submitted on 18 Feb 2024]
Approximating Partition in Near-Linear Time
We propose an O˜(n+1/ε)-time FPTAS (Fully Polynomial-Time Approximation Scheme) for the classical Partition problem. This is the best possible (up to a logarithmic factor) assuming SETH (Strong Exponential Time Hypothesis) [Abboud, Bringmann, Hermelin, and Shabtay'22]. Prior to our work, the best known FPTAS for Partition runs in O˜(n+1/ε5/4) time [Deng, Jin and Mao'23, Wu and Chen'22]. Our result is obtained by solving a more general problem of weakly approximating Subset Sum.
| Comments: | To appear in STOC2024 |
| Subjects: | Data Structures and Algorithms (cs.DS) |
| Cite as: | arXiv:2402.11426 [cs.DS] |
| (or arXiv:2402.11426v1 [cs.DS] for this version) | |
| https://doi.org/10.48550/arXiv.2402.11426 |
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK