New FPT algorithms solve standard-form ILP optimization in O(κ_k)^{2k} Δ² time and feasibility in O(κ_k)^k Δ time, where κ_k is the Komlós discrepancy constant, giving polylog(k) factors with known bounds and 2^{O(k)} under the conjecture.
Deterministic and las vegas algorithms for sparse nonnegative convolution
2 Pith papers cite this work. Polarity classification is still indexing.
2
Pith papers citing it
fields
cs.DS 2verdicts
UNVERDICTED 2representative citing papers
The authors give an Õ(n + √(wt))-time algorithm for Subset Sum.
citing papers explorer
-
Algorithms for Standard-form ILP Problems via Koml\'os' Discrepancy Setting
New FPT algorithms solve standard-form ILP optimization in O(κ_k)^{2k} Δ² time and feasibility in O(κ_k)^k Δ time, where κ_k is the Komlós discrepancy constant, giving polylog(k) factors with known bounds and 2^{O(k)} under the conjecture.
-
An Improved Pseudopolynomial Time Algorithm for Subset Sum
The authors give an Õ(n + √(wt))-time algorithm for Subset Sum.