Approximating Partition in Near-Linear Time

Lin Chen, Jiayi Lian, Yuchen Mao +1

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 polylogari…