Parameterized Algorithms on Integer Sets with Small Doubling: Integer Programming, Subset Sum and k-SUM
Preprint
Abstract
We study the parameterized complexity of algorithmic problems whose input is an integer set $A$ in terms of the doubling constant $C := |A + A|/|A|$, a fundamental measure of additive structure. We present evidence that this new parameterization is algorithmically useful in the form of new results for two difficult, well-studied problems: Integer Programming and Subset Sum. First, we show that determining the feasibility of bounded Integer Programs is a tractable problem when parameterized in the doubling constant. Specifically, we prove that the feasibility of an integer program $I$ with $n$ polynomially-bounded variables and $m$ constraints can be determined in time $n^{O_C(1)} poly(|I|)$ when the column set of the constraint matrix has doubling constant $C$. Second, we show that the Subset Sum and Unbounded Subset Sum problems can be solved in time $n^{O_C(1)}$ and $n^{O_C(\log \log \log n)}$, respectively, where the $O_C$ notation hides functions that depend only on the doubling constant $C$. We also show the equivalence of achieving an FPT algorithm for Subset Sum with bounded doubling and achieving a milestone result for the parameterized complexity of Box ILP. Finally, we design near-linear time algorithms for $k$-SUM as well as tight lower bounds for 4-SUM and nearly tight lower bounds for $k$-SUM, under the $k$-SUM conjecture. Several of our results rely on a new proof that Freiman's Theorem, a central result in additive combinatorics, can be made efficiently constructive. This result may be of independent interest.
Keywords
All Related Versions
This publication has 15 references indexed in Scilit:
- Faster Algorithms for Bounded Knapsack and Bounded Subset Sum Via Fine-Grained Proximity Results2024
- Graph Theory and Additive Combinatorics2023
- Tight Complexity Lower Bounds for Integer Linear Programming with Few ConstraintsACM Transactions on Computation Theory, 2020
- Combinatorial n-fold integer programming and applicationsMathematical Programming, 2019
- Proximity Results and Faster Algorithms for Integer Programming Using the Steinitz LemmaACM Transactions on Algorithms, 2019
- Faster Pseudopolynomial Time Algorithms for Subset SumACM Transactions on Algorithms, 2019
- On the Compressibility of $\mathcal{NP}$ Instances and Cryptographic ApplicationsSIAM Journal on Computing, 2010
- Open problems around exact algorithmsDiscrete Applied Mathematics, 2008
- An application of simultaneous approximation in combinatorial optimization1985
- Computing Partitions with Applications to the Knapsack ProblemJournal of the ACM, 1974