Conference 2024
Top image

 
Home
Program LNMB conference
Registration LNMB Conference
Invited Speakers LNMB Conference
Program PhD presentations
Abstracts PhD presentations
Announcement NGB/LNMB Seminar
Abstracts/Bios NGB/LNMB Seminar
Registration NGB/LNMB Seminar
Conference Office
How to get there
 
Return to LNMB Site
 

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.