# A FPTAS for the Subset Sum Problem with Real Numbers

arXiv: https://arxiv.org/abs/2110.09901 · HTML: https://mlsanity.com/paper/2110.09901/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 17 Oct 2021.

## Built on by (most cited first, 1 of 1)

- [Inferring Attack Relations for Gradual Semantics](https://mlsanity.com/paper/2211.16118/) (2022)

## Abstract (arXiv)

In this paper we study the subset sum problem with real numbers. Starting from the given problem, we formulate a quadratic maximization problem over a polytope which is eventually written as a distance maximization to a fixed point. For solving this, we provide a polynomial algorithm which maximizes the distance to a fixed point over a certain convex set. This convex set is obtained by intersecting the unit hypercube with two relevant half spaces. We show that in case the subset sum problem has a solution, our algorithm gives the correct maximum distance up to an arbitrary chosen precision. In such a case, we show that the obtained maximizer is a solution to the subset sum problem. Therefore, we compute the maximizer and upon analyzing it we can assert the feasibility of the subset sum problem.