14:00
15:00

/Exposé /Talk/

Many problems can be described using an integer program, e.g. scheduling, capital budgeting, or vehicle routing. In full generality, solving an integer program is known to be NP-hard. However, integer programs where the coefficient matrix is totally unimodular (each determinant of any square submatrix is one of the values in $\{-1,0,1\}$) can be solved in polynomial time. One of the central questions in combinatorial optimization is whether there is a polynomial-time algorithm for solving integer programs where the coefficient matrix is totally $\Delta$-modular (each determinant of any square submatrix is one of the values in $\{-\Delta,\ldots,\Delta\}$). The case of $\Delta=2$ was positively resolved by Artmann, Weismantel, and Zenklusen only as recently as 2017 and the question for larger values of $\Delta$ still remains open and appears to be very difficult.

In this talk, I will present results for several different cases of the above conjecture. These results require tools from structural graph theory and include a new algorithm for finding a maximum independent set in a graph with bounded odd cycle packing number, as well as a new proximity result of integer optimal solutions and their corresponding linear relaxation solutions.

[Lena Yuditsky ] (Université libre de Bruxelles )
[ https://web.math.princeton.edu/~pds/ | https://sites.google.com/view/yuditsky/home ]

Remarks / Remarques

Find all the information of the working group on this [ https://graphesetoptimisation.labri.fr/pmwiki.php/Groupe/GT?userlang=en | web page ] .
Retrouvez toutes les informations du GT sur cette [ https://graphesetoptimisation.labri.fr/pmwiki.php/Groupe/GT | page web ] .

LaBRI/178 et https://webconf.u-bordeaux.fr/b/mar-ef4-zed