Tutte seminar - Marco di SummaExport this event to calendar

Friday, May 25, 2012 — 3:30 PM to 4:30 PM EDT

A notion of inverse Chvátal rank

Speaker: Marco di Summa
Affiliation: University of Padova
Room: Mathematics & Computer Building (MC) 5158

Abstract:

The Chvátal rank of a polyhedron Q is the number of times one has to iterate the derivation of the so-called Chvátal closure in order to obtain the integer hull of Q, i.e., the polyhedron P defined as the convex hull of the integer points in Q. This number is known to be always finite for a fixed Q.

In this talk I will reverse this viewpoint by introducing the notion of inverse Chvátal rank: for an integral polyhedron P, the inverse Chvátal rank of P is the supremum of the Chvátal ranks of all polyhedra Q whose integer hull is P. In other words, this number describes how bad the worst linear relaxation of P is.

I will give a characterization of the integral polyhedra for which this value is finite, and discuss bounds on the inverse Chvátal rank for certain classes of integral polyhedra.

(This is joint work with Michele Conforti, Alberto Del Pia, Yuri Faenza and Rolande Grappe.)

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 (91)
    1. October (3)
    2. September (12)
    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)