About the Book:
Combinatorial Optimization: A First Course is designed for a one semester introductory graduate-level course for students of operations research, mathematics and computer science. In a self contained treatment requiring only some mathematical maturity, the topics covered include: linear and integer programming, polytopes, matroids and matroid optimization, shortest paths and network flows.Central to the exposition is the polyhedral viewpoint, a key principle underlying the successful integer-programming approach to combinatorial-optimization problems. These methods from a broad, coherent and powerful kernel in combinatorial optimization, with strong links to discrete mathematics, mathematical programming and computer science. Another key unifying topic is matroids.The author does not dwell on data structures and implementation details, preferring to focus on the key mathematical ideas that lead to useful models and algorithms. Problems and exercises are included throughout as well as references for further study.
Table of Contents:
Shortest paths and trees / Polytopes, polyhedra, Farkas' lemma and linear programming / Matchings and covers in bipartite graphs / Menger's theorem, flows and circulations / Nonbipartite matching / Problems, algorithms and running time / Cliques, cocliques and colourings / Integer linear programming and totally unimodular matrices / Multicommodity flows and disjoint paths / Matroids / References / Name index / Subject index
Graduate Students of Operation Research, Mathematics and Computer Science