## A First Course in Combinatorial Optimization"A First Course in Combinatorial Optimization" is a self-contained text for a one-semester introductory graduate-level course for students of operations research, mathematics, and computer science. The author focuses on the key mathematical ideas that lead to useful models and algorithms rather than on data structures and implementation details. The viewpoint is polyhedral, and the author also uses matroids as a unifying idea.Topics include linear and integer programming, polytopes, matroids and matroid optimization, shortest paths, and network flows. 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 column combinatorial optimization combinatorial-optimization problems common ground set consider convex convex hull Cutting-Plane Method cycle define dicycle digraph Dijkstra's Algorithm Dual Simplex Method edges of G efficient algorithm elements endpoint equations example extreme points Farkas Lemma feasible solution finding a minimum-weight 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 dipath 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