A First Course in Combinatorial OptimizationA First Course in Combinatorial Optimization is a 2004 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. |
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 b₁ basic solution Bellman-Ford Algorithm bipartite graph Branch-&-Bound cardinality characteristic vector Chvátal-Gomory cutting planes column combinatorial optimization combinatorial-optimization problems consider convex Cutting-Plane Method cycle defined dicycle digraph Dijkstra's Algorithm Dual Simplex Method Duality Theorem edge of G efficient algorithm elements endpoint equations example extreme points feasible solution finding a minimum-weight graph G graphic matroid Greedy Algorithm independent set integer linear program knapsack program König's Theorem Lemma Let G linear inequalities linear-programming relaxation lower bound matching of G matrix matroid Matroid-Intersection maximal maximum-cardinality matching minimal minimum-weight Hamiltonian tour minimum-weight v-w dipath nonnegative number of edges odd-set cover optimal solution perfect matching PI(M planar polytope problem of finding Proof satisfies Simplex Method solving spanning tree subgradient submodular function subproblem subprogram subset Suppose totally unimodular undirected graph upper bound V₁(G variables Vertex packing vertices w-tree weight function