Simple FPTAS for the subset-sums ratio problem

• We show a simple FPTAS for the subset-sums ratio problem.
• The new algorithm greatly simplifies the existing algorithm.
• The key insight is to solve a slightly harder problem called restricted subset-sums ratio.
• We introduce the restricted subset-sums ratio problem where we have an additional constraint that the output sets must contain some certain numbers.
• We show FPTAS for the restricted subset-sums ratio problem.

In the subset-sums ratio problem, we want to find two sets of numbers such that the ratio between the larger and smaller sets (in terms of the summed values) is as small as possible. We show a new Fully Polynomial-Time Approximation Scheme (FPTAS) for this problem which simplifies the algorithm proposed by [C. Bazgan, M. Santha, Z. Tuza, Efficient approximation algorithms for the SUBSET-SUMS EQUALITY problem, J. Comput. System Sci. 64 (2) (2002) 160–170, announced in ICALP 1998]. The key insight of the new algorithm is to solve the problem with an additional constraint that the output sets must contain some certain numbers. While the new problem is harder (in the sense that the original problem can be reduced to this problem), it still admits an FPTAS, which is surprisingly simpler than the FPTAS of the original problem.