Approximating Partition in Near-Linear Time

Lin Chen; Jiayi Lian; Yuchen Mao; Guochuan Zhang

doi:10.1145/3618260.3649727

STOC2024顶会

Approximating Partition in Near-Linear Time

Lin Chen, Jiayi Lian, Yuchen Mao, Guochuan Zhang

arXiv DOI 出版方

2024年份

3被引次数

9顶会引用

摘要

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 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 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.