Seminar: Samuel Fiorini (Bruxelles), International speaker
- https://wsc.project.cwi.nl/dutch-optimization-seminar/events/seminar-samuel-fiorini-bruxelles-international-speaker
- Seminar: Samuel Fiorini (Bruxelles), International speaker
- 2021-08-26T16:00:00+02:00
- 2021-08-26T17:00:00+02:00
- When Aug 26, 2021 from 04:00 PM to 05:00 PM (Europe/Amsterdam / UTC200)
- Add event to calendar iCal
Speaker: Samuel Fiorini (Université libre de Bruxelles)
Title:
Integer programs with bounded subdeterminants and two nonzeros per row
Zoom link:
https://cwi-nl.zoom.us/j/84909645595?pwd=b1M4QnNKVzNMdmNSVFNaZUJmR1kvUT09
(Meeting ID: 849 0964 5595, Passcode: 772448)
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).
Video:
Slides: