2022/01/11 by Giannis Alonistiotis, Antonis Antonopoulos, Alonistiotis, Giannis +9
Computer Science · Mathematics · #Algorithms and Data Compression #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Limits and Structures in Graph Theory #Machine Learning and Algorithms
paper · pdf · doi:10.48550/arxiv.2201.04165
openalex publication_date 2022/01/11 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We present a new FPTAS for the Subset Sum Ratio problem, which, given a set of integers, asks for two disjoint subsets such that the ratio of their sums is as close to 1 as possible. Our scheme makes use of exact and approximate algorithms for the closely related Partition problem, hence any progress over those -- such as the recent improvement due to Bringmann and Nakos [SODA 2021] -- carries over to our FPTAS. Depending on the relationship between the size of the input set n and the error margin ε, we improve upon the best currently known algorithm of Melissinos and Pagourtzis [COCOON 2018] of complexity O(n4 / ε). In particular, the exponent of n in our proposed scheme may decrease down to 2, depending on the Partition algorithm used. Furthermore, while the aforementioned state of the art complexity, expressed in the form O((n + 1 / ε)c), has constant c = 5, our results establish that c < 5.