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