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 - Sean KaferExport this event to calendar

Friday, February 28, 2020 — 1:00 PM EST

Title: An Introduction to the Circuits of Polyhedra, The Circuit Diameter, and Their Applications

Speaker: Sean Kafer
Affiliation: University of Waterloo
Room: MC 5417

Abstract:

The combinatorial diameter of a polyhedron P is the maximum value of a shortest path between two vertices of P, where the path moves along edges of P. Its study is motivated largely by its implications on the running time of the Simplex algorithm. In contrast, the circuit diameter of P is defined as the maximum value of a shortest path between two vertices of P, where the path moves along the circuits of P, where circuits are vectors that are parallel to a maximal set of facets of P. Equivalently, the set of circuits can be defined as the set of all edge directions that can be obtained by translating the facets of P. As such, the circuit diameter generalizes combinatorial diameter. Furthermore, circuits have the potential to be used to develop Simplex-like algorithms which solve LPs by moving along circuit directions.

This talk is intended as an introduction to the subject of circuits, the circuit diameter, and the application of circuits to augmentation algorithms. I will assume no foreknowledge of these topics. In addition to basics, I will discuss results about the circuit diameters of some well-known combinatorial polytopes. I will also discuss what is known about the potential for circuits to be used to solve LPs, including the best known performance of different "pivot rules" for circuit-based LP solving algorithms. Finally, I will discuss some hardness results regarding such algorithms, as well as hardness implications on the Simplex algorithm derived from results about circuits.

Some of this talk is based on work with coauthors Laura Sanità, Kostya Pashkovich, and Jesús De Loera.

Location 
MC - Mathematics & Computer Building
5417
200 University Avenue West

Waterloo, ON N2L 3G1
Canada

S M T W T F S
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
1
2
3
4
  1. 2020 (43)
    1. June (4)
    2. May (6)
    3. March (11)
    4. February (11)
    5. 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)