Block-Structured Integer and Linear Programming in Strongly Polynomial and Near Linear Time

Prelegent(ci)

Jana Cslovjecsek

Afiliacja

EPFL

Termin

29 kwietnia 2021 12:15

Informacje na temat wydarzenia

online

Seminarium

Seminarium "Algorytmika"

---

We consider n-fold integer programming problems and their
generalizations. These are integer linear programming problems for which
the linear constraints exhibit a (recursive) block-structure: The
problem decomposes into independent sub-problems after deleting a small
number of constraints. Our algorithm relies on parametric search to find
a good fractional solution and a proximity bound between this fractional
solution and an optimal integral solution. Together, this allows us to
find an optimal integer solution in near linear time.

---