Friday, June 5, 2020 1:00 pm
-
1:00 pm
EDT (GMT -04:00)
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.