Skip to content

Opening book details…

Can I read Parameterized Algorithms on Integer Sets with Small Doubling: Integer Programming, Subset Sum and k-SUM on EtoBox?

Parameterized Algorithms on Integer Sets with Small Doubling: Integer Programming, Subset Sum and k-SUM by Randolph, Tim; Węgrzycki, Karol is a scholarly article available to read on EtoBox.

What is Parameterized Algorithms on Integer Sets with Small Doubling: Integer Programming, Subset Sum and k-SUM about?

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 de

Author
Randolph, Tim; Węgrzycki, Karol
Published
2024
Language
EN

More by Randolph, Tim; Węgrzycki, Karol

Browse all works by Randolph, Tim; Węgrzycki, Karol