
Combinatorial Optimization
Packing and Covering
Gerard Cornuejols(Author)
Society for Industrial & Applied Mathematics,U.S. (Publisher)
Published on 31. March 2001
Book
Paperback/Softback
143 pages
978-0-89871-481-4 (ISBN)
Description
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. Cornuejols 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. Cornuejols) before 2020. Claims must be sent to Dr. Cornuejols at Carnegie Mellon University during his lifetime.
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. Cornuejols 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. Cornuejols) before 2020. Claims must be sent to Dr. Cornuejols at Carnegie Mellon University during his lifetime.
More details
Series
Language
English
Place of publication
New York
United States
Target group
Professional and scholarly
Product notice
Paperback (trade)
Dimensions
Height: 251 mm
Width: 172 mm
Thickness: 9 mm
Weight
269 gr
ISBN-13
978-0-89871-481-4 (9780898714814)
Copyright in bibliographic data and cover images is held by Nielsen Book Services Limited or by the publishers or by their respective licensors: all rights reserved.
Schweitzer Classification
Content
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
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