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

Speaker(s)

Jana Cslovjecsek

Affiliation

EPFL

Date

April 29, 2021, 12:15 p.m.

Information about the event

online

Seminar

Seminar Algorithms

---

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.

---