Contact Info
Combinatorics & Optimization
University of Waterloo
Waterloo, Ontario
Canada N2L 3G1
Phone: 519-888-4567, ext 33038
PDF files require Adobe Acrobat Reader.
Friday, June 5, 2020 1:00 PM EDT
Title: A Strongly Polynomial Label-Correcting Algorithm for Linear Systems with Two Variables per Inequality
| Speaker: | Cedric Koh |
| Affiliation: | London School of Economics and Political Science |
| Zoom: | Contact Sharat Ibrahimpur |
Abstract:
In this talk, I will present a strongly polynomial label-correcting algorithm for solving the feasibility of linear systems with two variables per inequality. The algorithm is based on the Newton–Dinkelbach method for fractional combinatorial optimization, and extends previous work of Madani (2002). The key technical idea is a new analysis of the Newton-Dinkelbach method exploiting gauge symmetries of the algorithm. This also leads to an acceleration of the method for general fractional combinatorial optimization problems.
Based on joint work with Bento Natura and László Végh.