|
Samuel Fiorini:
Integer programs with bounded subdeterminants
Abstract: A matrix M is said to be totally unimodular (TU) if the determinant of every square submatrix of M is in {-1,0,1}. Integer programs with TU constraint matrices M are a cornerstone of discrete optimization. These IPs can be solved in strongly polynomial time through their linear programming relaxations, and include as a special case the shortest path problem, maximum flow and minimum s-t cut. Now assume that all the subdeterminants of M are bounded by a constant in absolute value. Can we then solve the IP in strongly polynomial time? This question is still wide open, despite recent progress. I will take you on a tour of integer programming in the light of subdeterminants, featuring classical results such as Seymour's decomposition of TU matrices (1980) and the proximity bound of Cook, Gerards, Tardos & Schrijver (1986), as well as present-day advances. |