Society for Industrial and Applied Mathematics, 2001, -145 pp.
The integer programming models known as set packing and set covering have a wide range of applications, such as patte recognition, plant location, and airline crew scheduling. Sometimes, because of the special structure of the constraint matrix, the natural linear programming relaxation yields an optimal solution that is integral, thus solving the problem. Sometimes, both the linear programming relaxation and its dual have integral optimal solutions. Under which conditions do such integrality properties hold? This question is of both theoretical and practical interest. Min-max theorems, polyhedral combinatorics, and graph theory all come together in this rich area of discrete mathematics. In addition to min-max and polyhedral results, some of the deepest results in this area come in two flavors: "excluded minor" results and "decomposition" results. In this book, we present several of these beautiful results. Three chapters cover min-max and polyhedral results. The next four chapters cover excluded minor results. In the last three chapters, we present decomposition results. We hope that this book will encourage research on the many intriguing open questions that still remain. In particular, we state 18 conjectures. For each of these conjectures, we offer $5000 for the first paper solving or refuting it. The paper must be accepted by a quality refereed joual (such as Joual of Combinatorial Theory B, Combinatorica, SIAM Joual on Discrete Mathematics, or others to be determined by Gerard Couejols) before
2020. Claims must be sent to Gerard Couejols at Caegie Mellon University during his lifetime.
Clutters.
T-Cuts and 7-Joins.
Perfect Graphs and Matrices.
Ideal Matrices.
Odd Cycles in Graphs.
0,±1 Matrices and Integral Polyhedra.
Signing 0,1 Matrices to Be Totally Unimodular or Balanced.
Decomposition by A-Sum.
Decomposition of Balanced Matrices.
Decomposition of Perfect Graphs.
The integer programming models known as set packing and set covering have a wide range of applications, such as patte recognition, plant location, and airline crew scheduling. Sometimes, because of the special structure of the constraint matrix, the natural linear programming relaxation yields an optimal solution that is integral, thus solving the problem. Sometimes, both the linear programming relaxation and its dual have integral optimal solutions. Under which conditions do such integrality properties hold? This question is of both theoretical and practical interest. Min-max theorems, polyhedral combinatorics, and graph theory all come together in this rich area of discrete mathematics. In addition to min-max and polyhedral results, some of the deepest results in this area come in two flavors: "excluded minor" results and "decomposition" results. In this book, we present several of these beautiful results. Three chapters cover min-max and polyhedral results. The next four chapters cover excluded minor results. In the last three chapters, we present decomposition results. We hope that this book will encourage research on the many intriguing open questions that still remain. In particular, we state 18 conjectures. For each of these conjectures, we offer $5000 for the first paper solving or refuting it. The paper must be accepted by a quality refereed joual (such as Joual of Combinatorial Theory B, Combinatorica, SIAM Joual on Discrete Mathematics, or others to be determined by Gerard Couejols) before
2020. Claims must be sent to Gerard Couejols at Caegie Mellon University during his lifetime.
Clutters.
T-Cuts and 7-Joins.
Perfect Graphs and Matrices.
Ideal Matrices.
Odd Cycles in Graphs.
0,±1 Matrices and Integral Polyhedra.
Signing 0,1 Matrices to Be Totally Unimodular or Balanced.
Decomposition by A-Sum.
Decomposition of Balanced Matrices.
Decomposition of Perfect Graphs.