Loading... Please wait...

Combinatorial Optimization: Packing and Covering

Hover over image to zoom

Order Code:

 Product Description

by Gérard Cornuéjols


2001 / xii + 132 pages / Softcover / ISBN: 978-0-898714-81-4 / List Price $62.50 / SIAM/CBMS Member Price $43.75 / Order Code CB74

This monograph presents new and elegant proofs of classical results and makes difficult results accessible. 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 integral, thus solving the problem. Sometimes, both the linear programming relaxation and its dual have integral 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 rich area of discrete mathematics. This monograph presents several of these beautiful results as it introduces mathematicians to this active area of research.

To encourage research on the many intriguing open problems that remain, Dr. Cornuéjols is offering a $5000 prize to the first paper solving or refuting each of the 18 conjectures described in the book. To claim one of the prizes mentioned in the preface, papers must be accepted by a quality refereed journal (such as Journal of Combinatorial Theory B, Combinatorica, SIAM Journal on Discrete Mathematics, or others to be determined by Dr. Cornuéjols) before 2020. Claims must be sent to Dr. Cornuéjols at Carnegie Mellon University during his lifetime.

This book is appropriate for graduate students and faculty members in applied mathematics, operations research, and computer science.

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

ISBN: 9780898714814

 Find Similar Products by Category

Vendors Other Products

 Product Reviews

This product hasn't received any reviews yet. Be the first to review this product!

You Recently Viewed...



Follow us on

Copyright 2017 SIAM Bookstore. All Rights Reserved.
Sitemap | BigCommerce Premium Themes by PSDCenter

Society for Industrial and Applied Mathematics 3600 Market St., 6th Fl. Philadelphia, PA 19104-2688 USA +1-215-382-9800 FAX: +1-215-386-7999 www.siam.org email: siambooks@siam.org

Click the button below to add the Combinatorial Optimization: Packing and Covering to your wish list.