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.

Tutte Colloquium - Laura SanitaExport this event to calendar

Friday, June 28, 2019 — 3:30 PM EDT

Title: On the hardness of computing the diameter of a polytope

Speaker: Laura Sanita
Affiliation: University of Waterloo
Room: MC 5501

Abstract:

The diameter of a polytope P is given by the maximum length of a shortest path between a pair of vertices on P. Giving bounds on the diameter of a polytope is a fundamental research topic in theoretical computer science and discrete mathematics, motivated by the (still unknown) existence of a polynomial pivot rule for the Simplex Algorithm for solving Linear Programs.

The diameter of a polytope has been studied from many different perspectives, including a computational complexity point of view. In particular, Frieze and Teng in 1994 showed that computing the diameter of a polytope is weakly NP-hard.
In this talk, we will strengthen this hardness result, by exploiting the structure of a notorious and well-studied polytope in the optimization community: the fractional matching polytope. In particular, we will give an exact characterization of the diameter of this polytope, and then use it to derive strong NP-hardness (in fact, APX-hardness) for the problem of computing the diameter.
 

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

Waterloo, ON N2L 3G1
Canada

S M T W T F S
27
28
29
30
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. 2021 (71)
    1. August (2)
    2. July (10)
    3. June (12)
    4. May (7)
    5. April (9)
    6. March (13)
    7. February (8)
    8. January (10)
  2. 2020 (119)
    1. December (5)
    2. November (12)
    3. October (12)
    4. September (12)
    5. August (11)
    6. July (17)
    7. June (11)
    8. May (6)
    9. March (11)
    10. February (11)
    11. January (11)
  3. 2019 (167)
  4. 2018 (136)
  5. 2017 (103)
  6. 2016 (137)
  7. 2015 (136)
  8. 2014 (88)
  9. 2013 (48)
  10. 2012 (39)
  11. 2011 (36)
  12. 2010 (40)
  13. 2009 (40)
  14. 2008 (39)
  15. 2007 (15)