## A First Course in Combinatorial OptimizationA First Course in Combinatorial Optimization is a text for a one-semester introductory graduate-level course for students of operations research, mathematics, and computer science. It is a self-contained treatment of the subject, requiring only some mathematical maturity. Topics include: linear and integer programming, polytopes, matroids and matroid optimization, shortest paths, and network flows. Central to the exposition is the polyhedral viewpoint, which is the key principle underlying the successful integer-programming approach to combinatorial-optimization problems. 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. |

### What people are saying - Write a review

We haven't found any reviews in the usual places.

### Contents

II | 1 |

III | 9 |

IV | 14 |

V | 21 |

VI | 27 |

VII | 29 |

VIII | 35 |

IX | 40 |

XXXVI | 126 |

XXXVII | 137 |

XXXVIII | 138 |

XL | 140 |

XLI | 147 |

XLII | 150 |

XLIII | 151 |

XLV | 152 |

X | 49 |

XII | 51 |

XIII | 53 |

XIV | 56 |

XV | 60 |

XVI | 63 |

XVII | 66 |

XVIII | 73 |

XIX | 75 |

XX | 76 |

XXI | 78 |

XXIII | 81 |

XXIV | 82 |

XXV | 84 |

XXVII | 89 |

XXVIII | 101 |

XXIX | 103 |

XXX | 106 |

XXXI | 107 |

XXXIII | 109 |

XXXIV | 113 |

XXXV | 121 |

### Other editions - View all

### Common terms and phrases

augmenting path basic solution Bellman-Ford Algorithm bipartite graph Branch-&-Bound cardinality characteristic vector Cjxj column combinatorial optimization combinatorial-optimization problems consider convex convex hull Cutting-Plane Method cycle define dicycle digraph Dijkstra's Algorithm Dual Simplex Method Duality Theorem edges of G efficient algorithm elements endpoint equations example extreme points Farkas Lemma feasible solution finding a minimum-weight Gomory cutting planes graph G graphic matroid Greedy Algorithm independent set integer linear program knapsack program Lemma Let G linear inequalities linear-programming relaxation linearly independent lower bound matching of G matrix Matroid-Intersection maximal maximum-cardinality matching minimal minimum-weight v-w dipath nonnegative number of edges odd-set cover optimal solution perfect matching planar polytope problem of finding Proof satisfies Simplex Method solving spanning tree subgradient submodular function subproblem subprogram subset Suppose T-join totally unimodular undirected graph upper bound v e V(G variables Vertex packing w-tree weight function