Approximating Partition in Near-Linear Time
<|reference_start|>Approximating Partition in Near-Linear Time: We propose an $\widetilde{O}(n + 1/\eps)$-time FPTAS (Fully Polynomial-Time Approximation Scheme) for the classical Partition problem. This is the best possible (up to a polylogarithmic 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 $\widetilde{O}(n + 1/\eps^{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.<|reference_end|>
@article{chen2024approximating,
    title={Approximating Partition in Near-Linear Time},
    author={Lin Chen, Jiayi Lian, Yuchen Mao, Guochuan Zhang},
    journal={arXiv preprint arXiv:2402.11426},
    year={2024},
    archivePrefix={arXiv},
    eprint={2402.11426},
    primaryClass={cs.DS}
}