BEGIN:VCALENDAR
CALSCALE:GREGORIAN
PRODID:iCalendar-Ruby
VERSION:2.0
BEGIN:VEVENT
DESCRIPTION: In this talk\, I will show how techniques from Combinatorial O
 ptimization and Combinatorics can be leveraged to achieve progress on a wel
 l-known question in Integer Programming\, namely how to solve integer linea
 r programs (ILPs) with bounded subdeterminants. More precisely\, I will pre
 sent an efficient (even strongly polynomial) algorithm to solve ILPs define
 d by a constraint matrix whose subdeterminants are all within {-2\,-1\,0\,1
 \,2}. This problem class naturally extends the well-known class of ILPs wit
 h a totally unimodular (TU) constraint matrix\, i.e.\, where subdeterminant
 s are within {-1\,0\,1}\, and captures some open problems. We employ a vari
 ety of techniques common in Combinatorial Optimization\, including polyhedr
 al techniques\, matroids\, and submodular functions. In particular\, using 
 a polyhedral result of Veselov and Chirkov\, we reduce the problem to a com
 binatorial one with a so-called parity constraint. We then show how a semin
 al\, purely combinatorial result of Seymour on decomposing TU matrices\, wh
 ich is tightly related to regular matroids and was originally developed in 
 this context\, can be used algorithmically to break the problem into smalle
 r ones. Finally\, these smaller problems are amenable to combinatorial opti
 mization techniques like parity-constrained submodular minimization. Additi
 onally\, I will highlight some of the many open problems in this field and 
 discuss recent related results. 
DTSTAMP:20180614T132200
DTSTART:20180618T141500
CLASS:PUBLIC
LOCATION:Technische Universität Berlin Institut für Mathematik Straße des 1
 7. Juni 136 10623 Berlin room MA 041 (ground floor)
SEQUENCE:0
SUMMARY:Rico Zenklusen (ETH Zürich): At the Interface of Combinatorial Opti
 mization and Integer Programming
UID:89680376@www.facetsofcomplexity.de
URL:http://www.facetsofcomplexity.de/monday/20180618-L-Zenklusen.html
END:VEVENT
END:VCALENDAR