Combinatorial Optimization Reading Group - Cedric Koh

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


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.