×

zbMATH — the first resource for mathematics

Combinatorial optimization. Packing and covering. (English) Zbl 0972.90059
CBMS-NSF Regional Conference Series in Applied Mathematics. 74. Philadelphia, PA: SIAM, Society for Industrial and Applied Mathematics. xi, 132 p. (2001).
This nice survey presents new and elegant proofs of classical results for the integer programming models known as set packing and covering. There are min-max, polyhedral, exclude minor, and decomposition results. We give the headings of the 10 chapters:
1. Clutters, 2. \(T\)-Cuts and \(T\)-Joins, 3. Perfect Graphs and Matrices, 4. Ideal Matrices, 5. Odd Cycles in Graphs, 6. \(0,\pm 1\) Matrices and Integral Polyhedra, 7. Signing 0,1 Matrices to Be Totally Unimodular or Balanced, 8. Decomposition by \(k\)-Sum, 9. Decomposition of Balanced Matrices, 10. Decomposition of Perfect Graphs.
For each of 18 conjectures, stated in the book, the author offers $ 5000 for the first paper solving or refuting it.

MSC:
90C27 Combinatorial optimization
90-02 Research exposition (monographs, survey articles) pertaining to operations research and mathematical programming
05B40 Combinatorial aspects of packing and covering
05-02 Research exposition (monographs, survey articles) pertaining to combinatorics
PDF BibTeX XML Cite
Full Text: DOI