University COVID-19 update

The University of Waterloo is constantly updating our most Frequently Asked Questions.

Questions about buildings and services? Visit the list of Modified Services.

Please note: The University of Waterloo is closed for all events until further notice.

Combinatorial Optimization Reading Group - Cedric KohExport this event to calendar

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.

S M T W T F S
26
27
28
29
30
31
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
1
2
3
4
5
  1. 2020 (76)
    1. August (9)
    2. July (17)
    3. June (11)
    4. May (6)
    5. March (11)
    6. February (11)
    7. January (11)
  2. 2019 (167)
    1. December (5)
    2. November (15)
    3. October (18)
    4. September (15)
    5. August (9)
    6. July (17)
    7. June (18)
    8. May (16)
    9. April (9)
    10. March (24)
    11. February (13)
    12. January (8)
  3. 2018 (138)
  4. 2017 (103)
  5. 2016 (137)
  6. 2015 (136)
  7. 2014 (88)
  8. 2013 (48)
  9. 2012 (39)
  10. 2011 (36)
  11. 2010 (40)
  12. 2009 (40)
  13. 2008 (39)
  14. 2007 (15)