[Mittagsseminar TI] Mittagsseminar am Donnerstag, 27. 11. 2025: Asaf Levin (Haifa), Algorithms for Sparse Separable Convex Integer Programs

[Günter Rote <rote@inf.fu-berlin.de>]

Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin
spricht am

      Donnerstag, 22. Mai 2025, 12:00 Uhr, SR 055, Takustraße 9
      Asaf Levin (Technion, Haifa)
      zum Thema: (Near)-Optimal Algorithms for Sparse Separable Convex Integer Programs

Abstract:

We study the general integer programming (IP) problem of optimizing a separable
convex function over the integer points of a polytope. The number of variables n is
a variable part of the input, and we consider the regime where the
constraint matrix A has small coefficients and small primal or dual treedepth.
Equivalently, we consider block-structured matrices, in particular n-fold,
tree-fold, 2-stage and multi-stage matrices.

We ask about the possibility of near-linear time algorithms in the general case of
(non-linear) separable convex functions.
The techniques of previous works for the linear case are inherently limited to it;
in fact, no strongly-polynomial algorithm may exist due to a simple unconditional
information-theoretic lower bound.

Our algorithms combine ideas from scaling, proximity, and sensitivity of
integer programs, together with a new dynamic data structure.

Based on a joint work with Christoph Hunkenschröder, Martin Koutecký, and Tung Anh Vu