@online{Aggarwal_2407.05435,
TITLE = {Polynomial Time Algorithms for Integer Programming and Unbounded Subset Sum in the Total Regime},
AUTHOR = {Aggarwal, Divesh and Joux, Antoine and Santha, Miklos and W{\k e}grzycki, Karol},
LANGUAGE = {eng},
URL = {https://arxiv.org/abs/2407.05435},
EPRINT = {2407.05435},
EPRINTTYPE = {arXiv},
YEAR = {2024},
MARGINALMARK = {$\bullet$},
ABSTRACT = {The Unbounded Subset Sum (USS) problem is an NP-hard computational problem<br>where the goal is to decide whether there exist non-negative integers $x_1,<br>\ldots, x_n$ such that $x_1 a_1 + \ldots + x_n a_n = b$, where $a_1 < \cdots <<br>a_n < b$ are distinct positive integers with $\text{gcd}(a_1, \ldots, a_n)$<br>dividing $b$. The problem can be solved in pseudopolynomial time, while<br>specialized cases, such as when $b$ exceeds the Frobenius number of $a_1,<br>\ldots, a_n$ simplify to a total problem where a solution always exists.<br> This paper explores the concept of totality in USS. The challenge in this<br>setting is to actually find a solution, even though we know its existence is<br>guaranteed. We focus on the instances of USS where solutions are guaranteed for<br>large $b$. We show that when $b$ is slightly greater than the Frobenius number,<br>we can find the solution to USS in polynomial time.<br> We then show how our results extend to Integer Programming with Equalities<br>(ILPE), highlighting conditions under which ILPE becomes total. We investigate<br>the diagonal Frobenius number, which is the appropriate generalization of the<br>Frobenius number to this context. In this setting, we give a polynomial-time<br>algorithm to find a solution of ILPE. The bound obtained from our algorithmic<br>procedure for finding a solution almost matches the recent existential bound of<br>Bach, Eisenbrand, Rothvoss, and Weismantel (2024).<br>},
}