07.03.2023 16:00 Stefan Kober:
Totally Delta-modular IPs on a TU constraint matrix with one additional rowMI 02.04.011 (Boltzmannstr. 3, 85748 Garching)

It is a well-known conjecture that integer programs on an integer constraint matrix whose subdeterminants are bounded in absolute value by a constant could be solvable in polynomial time. Despite some recent progress in special cases, the question is still wide open. We consider the special case consisting of a TU constraint matrix with one additional row, which in general encompasses different hard and interesting problems. We present partial progress to the resolution of the question of polynomial solvability of such problems in particular for transposed network matrices. The applied techniques range from Seymour's decomposition of TU matrices over certain types of proximity results for integer programs to graph and minor theory.

This is joint work with Manuel Aprile, Samuel Fiorini, Stefan Weltge and Yelena Yuditsky.