5 papers
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…
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 $Ω(Î_{\tex…
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…
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…