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 |
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.