The Dutch Seminar on Optimization is an initiative to bring together researchers from the Netherlands and beyond, with topics that are centered around Optimization in a broad sense. We would like to invite all researchers, especially also PhD students, who are working on related topics to join the events.
Speaker: Samuel Fiorini (Université libre de Bruxelles)
Tile: Integer programs with bounded subdeterminants and two nonzeros per row
Abstract:
We give a strongly polynomial-time algorithm for integer linear programs defined by integer coefficient matrices whose subdeterminants are bounded by a constant and that contain at most two nonzero entries in each row. The core of our approach is the first polynomial-time algorithm for the weighted stable set problem on graphs that do not contain more than k vertex-disjoint odd cycles, where k is any constant. Previously, polynomial-time algorithms were only known for k=0 (bipartite graphs) and for k=1. We observe that integer linear programs defined by coefficient matrices with bounded subdeterminants and two nonzeros per column can be also solved in strongly polynomial-time, using a reduction to b-matching. This is joint work with Gwenaël Joret (ULB), Stefan Weltge (TUM) and Yelena Yuditsky (ULB)
The lecture will be given online. Please visit the website for more information and the zoom link.
