Approximating Partition in Deterministic Near-Linear Time

Abstract

We propose a deterministic $\tilde{O}(n+\frac{1}{\epsilon })$-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 $\tilde{O}(n+(\frac{1}{\epsilon }{)}^{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.

A preliminary version was published in STOC 2024. Compared to the previous version, the current version introduces a deterministic weak approximation scheme for Subset Sum