Efficiently solving special instances of NP-hard problems: Integer programs with bounded subdeterminants

Abstract

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.

Bio:

Yelena Yuditsky is a F.R.S.-FNRS postdoctoral fellow at Université libre de Bruxelles. Prior to that, Yelena was a postdoctoral fellow at Ben-Gurion University of the Negev and Karlsruhe institute of technology. Yelena received her PhD from McGill university where she was advised by Bruce Reed and Sergey Norin. Her research interests are in design and analysis of algorithms, optimization, structural graph theory and discrete geometry.