3 papers
cs.DS2025
(Near)-Optimal Algorithms for Sparse Separable Convex Integer Programs
Christoph Hunkenschröder, Martin Koutecký, Asaf Levin +1
We study the general integer programming (IP) problem of optimizing a separable convex function over the integer points of a polytope: $\min \{f(\mathbf{x}) \mid A\mathbf{x} = \mat…
math.OC2025
Better and Simpler Reducibility Bounds over the Integers
Asaf Levin
We study the settings where we are given a function of n variables defined in a given box of integers. We show that in many cases we can replace the given objective function by a n…
cs.CC2024
Tight Lower Bounds for Block-Structured Integer Programs
Christoph Hunkenschröder, Kim-Manuel Klein, Martin Koutecký +2
We study fundamental block-structured integer programs called tree-fold and multi-stage IPs. Tree-fold IPs admit a constraint matrix with independent blocks linked together by few…