4 papers · 1 filter
Improving Lagarias-Odlyzko Algorithm For Average-Case Subset Sum: Modular Arithmetic Approach
Antoine Joux, Karol Węgrzycki
Lagarias and Odlyzko (J.~ACM~1985) proposed a polynomial time algorithm for solving ``\emph{almost all}'' instances of the Subset Sum problem with integers of size $Ω(Γ_{\text{…
Parameterized Algorithms on Integer Sets with Small Doubling: Integer Programming, Subset Sum and k-SUM
Tim Randolph, Karol Węgrzycki
We study the parameterized complexity of algorithmic problems whose input is an integer set in terms of the doubling constant , a fundamental measure of addit…
Polynomial Time Algorithms for Integer Programming and Unbounded Subset Sum in the Total Regime
Divesh Aggarwal, Antoine Joux, Miklos Santha +1
The Unbounded Subset Sum (USS) problem is an NP-hard computational problem where the goal is to decide whether there exist non-negative integers such that $x_1 a…
Sensitivity, Proximity and FPT Algorithms for Exact Matroid Problems
Friedrich Eisenbrand, Lars Rohwedder, Karol Węgrzycki
We consider the problem of finding a basis of a matroid with weight exactly equal to a given target. Here weights can be discrete values from or more generally $m…