7 papers
Pigeonhole Equal Subset Sum: Subexponential Algorithm, Tight Lower Bounds, and Average-Case Analysis
Deepak Bhati, Pranjal Dutta, Antoine Joux +2
The Equal Subset Sum problem asks, given n positive integers bounded by M, to find two distinct non-empty subsets with the same sum. We study this problem in the regime $M = 2^{o(n…
On the Largest Cardinality Subset Sum
Deepak Bhati, Anubhav Dhar, Pranjal Dutta +2
We study Largest Cardinality Subset Sum (LCSS): given nonnegative integers and a target , compute a subset summing to with maximum cardinality. We also consider its all-…
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…
Fine-Grained Complexity of Earth Mover's Distance under Translation
Karl Bringmann, Frank Staals, Karol Węgrzycki +1
The Earth Mover's Distance is a popular similarity measure in several branches of computer science. It measures the minimum total edge length of a perfect matching between two poin…