Contact Info
Combinatorics & Optimization
University of Waterloo
Waterloo, Ontario
Canada N2L 3G1
Phone: 519-888-4567, ext 33038
PDF files require Adobe Acrobat Reader.
Title: Integer programs with bounded subdeterminants and two nonzeros per row
Speaker: | Stefan Weltge |
Affiliation: | Technical University of Munich |
Location: | MC 5501 or contact Eva Lee for Zoom link |
Abstract: Determining the complexity of integer linear programs with integer coefficient matrices whose subdeterminants are bounded by a constant is currently a very actively discussed question in the field. In this talk, I will present a strongly polynomial-time algorithm for such integer programs with the further requirement that every constraint contains at most two variables. 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.
This is joint work with Samuel Fiorini, Gwenaël Joret, and Yelena Yuditsky, which recently appeared at FOCS this year.
Combinatorics & Optimization
University of Waterloo
Waterloo, Ontario
Canada N2L 3G1
Phone: 519-888-4567, ext 33038
PDF files require Adobe Acrobat Reader.
The University of Waterloo acknowledges that much of our work takes place on the traditional territory of the Neutral, Anishinaabeg and Haudenosaunee peoples. Our main campus is situated on the Haldimand Tract, the land granted to the Six Nations that includes six miles on each side of the Grand River. Our active work toward reconciliation takes place across our campuses through research, learning, teaching, and community building, and is co-ordinated within the Office of Indigenous Relations.