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 seminar - Laura SanitàExport this event to calendar

Friday, July 13, 2012 — 3:30 PM to 4:30 PM EDT

0/1 Polytopes with Quadratic Chvátal Rank

Speaker: Laura Sanità
Affiliation: University of Waterloo
Room: Mathematics & Computer Building (MC) 5158

Abstract:

For a polytope P, the Chvátal closure P'⊆P is obtained by simultaneously strengthening all feasible inequalities cx≤β (with integral c) to cx≤⌊β⌋. The number of iterations of this procedure that are needed until the integral hull of P is reached is called the Chvátal rank. If P⊆[0,1]n, then it is known that O(n2 log n) iterations always suffices (Eisenbrand and Schulz (1999)) and at least (1+1/e-0(1))n iterations are sometimes needed (Pokutta and Stauffer (2011)), leaving a huge gap between lower and upper bounds. We prove that there is a polytope contained in the 0/1 cube that has Chvátal rank Ω(n2), closing the gap up to a logarithmic factor. In fact, even a superlinear lower bound was mentioned as an open problem by numerous authors.

Joint work with Thomas Rothvoß.

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

Waterloo, ON N2L 3G1
Canada

S M T W T F S
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
1
2
  1. 2021 (85)
    1. October (1)
    2. September (8)
    3. August (7)
    4. July (10)
    5. June (12)
    6. May (7)
    7. April (9)
    8. March (13)
    9. February (8)
    10. 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)