Contact us on (02) 8445 2300
For all customer service and order enquiries

Woodslane Online Catalogues

9780898714814 Academic Inspection Copy

Combinatorial Optimization

Packing and Covering
Description
Table of
Contents
Google
Preview
New proofs of classical results are presented and difficult results are made accessible in this monograph. The integer programming models known as set packing and set covering have a wide range of applications. Sometimes, owing to the special structure of the constraint matrix, the natural linear programming relaxation yields an optimal solution that is integer, thus solving the problem. Sometimes, both the linear programming relaxation and its dual have integer optimal solutions. Under which conditions do such integrality conditions hold? This question is of both theoretical and practical interest. Min-max theorems, polyhedral combinatorics and graph theory all come together in this area of discrete mathematics. This monograph presents several of these results as it introduces mathematicians to this active area of research.
Preface Chapter 1: Clutters Chapter 2: T-Cuts and T-Joins Chapter 3: Perfect Graphs and Matrices Chapter 4: Ideal Matrices Chapter 5: Odd Cycles in Graphs Chapter 6: 0,+1 Matrices and Integral Polyhedra Chapter 7: Signing 0,1 Matrices to Be Totally Unimodular or Balanced Chapter 8: Decomposition by k-Sum Chapter 9: Decomposition of Balanced Matrices Chapter 10: Decomposition of Perfect Graphs Bibliography Index
Google Preview content