Return to Colloquia & Seminar listing
Total dual integrality and perfect graphs
Optimization| Speaker: | Edwin O'shea, Univ. of Washington |
| Location: | 2112 MSB |
| Start time: | Fri, Jan 27 2006, 2:10PM |
Description
Many problems in combinatorial optimization can be expressed as detecting
total dual integrality (TDI) in a 'non-generic' system of linear
inequalities. One such case is the weak perfect graph theorem (WPGT) of
Lovasz. We will present various ways for detecting TDI in a non-generic
system by studying secondary fans and Groebner bases of toric ideals. When
coupled with computational algebra packages, this understanding provides an
experimentally feasible tool for investigating TDI in a whole host of
scenarios. It also provides a new, Groebner basis proof of WPGT for chordal
graphs. More generally, we will present an explicit polyhedral strengthening of WPGT.
This is joint work with Andras Sebo.