The Set Packing and Set Covering Polyhedra
|Affiliation:||University of Waterloo|
|Room:||Mathematics and Computer Building (MC) 6486|
The set packing and set covering polyhedra are two of the most fundamental objects in combinatorial optimization. More than 50 years of studying the different properties of these objects has led to many beautiful theories and spectacular results, such as Fulkerson's theory of blocking and anti-blocking polyhedra, the different perfect graph theorems, characterization of ideal matrices, matroids with the max-flow min-cut property, characterization of weakly bipartite graphs, and many more.
In this talk, I will give an overview of these results, and explain the striking differences between the two objects that makes the set covering polyhedron much more complex than the other one. I will also talk about some recent progress towards understanding these polyhedra.
Some of the results are based on joint works with A. Feldmann,
R. Fukasawa, B. Guenin, J. Könemann and L. Sanità.
200 University Avenue West
Waterloo, ON N2L 3G1