Marius Costandin
Published 2021-10-17, updated 2023-10-05Version 3
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.
Comments: It relies on maximizing the distance over an intersection of balls to a given point. The used algorithm for this however, is not able to solve the class of problem the SSP generates
Minimum L1-distance projection onto the boundary of a convex set: Simple characterization
On the Hardness of Almost All Subset Sum Problems by Ordinary Branch-and-Bound
Lifts of convex sets and cone factorizations
![QR code for arXiv:2110.09901 [math.OC]](http://oss.arxitics.com/images/favicon.svg)