Integer Programming and Convolution, with Applications
summary
Provides an algorithm for integer programs Ax=b, x≥0 with m constraints and coefficients ≤Δ that replaces the dependence on the right-hand side B by log B, and achieves roughly 2^m times poly(Δ,n) time via an iterative DP that merges solutions by min-plus convolution. Proof uses the Steinitz lemma to bound partial sums and limit candidate RHS vectors. Feasibility improves to single-exponential in m with a SETH-based lower bound forbidding m−ε, and the methods speed unbounded knapsack/subset-sum and scheduling PTASes.
AI-written summary · about