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 - Ricardo FukasawaExport this event to calendar

Friday, October 16, 2009 — 3:30 PM to 4:30 PM EDT

The master equality polyhedron

Speaker: Ricardo Fukasawa
Affiliation: University of Waterloo
Room: Mathematics & Computer Building (MC) 5158

Abstract:

In this talk, we introduce the master equality polyhedron (MEP), which generalizes the master polyhedra of Gomory (1969). Gomory introduced the master polyhedron and the master cyclic group polyhedron as tools to obtain cutting planes for general integer programming problems, and characterized their "non-trivial polar", i.e., the convex hull of inequalities which define their non-trivial facets. We obtain a similar characterization of the MEP when it is defined by a single constraint. When the MEP is defined by multiple constraints, a similar characterization is harder to obtain. Nevertheless, for the two and three constraint case, we obtain results that allow us to solve the separation problem over the MEP in polynomial-time. We will discuss these results and their implications. 

No previous knowledge is assumed. 

This is joint work with Sanjeeb Dash and Oktay Gunluk.

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

Waterloo, ON N2L 3G1
Canada

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 (72)
    1. August (5)
    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)