A First Course in Combinatorial Optimization

ISBN-13: 9780521010122 / Angielski / Miękka / 2004 / 228 str.

Jon Lee; D. G. Crighton; M. J. Ablowitz

Opis

Jon Lee focuses on key mathematical ideas leading to useful models and algorithms, rather than on data structures and implementation details, in this introductory graduate-level text for students of operations research, mathematics, and computer science. The viewpoint is polyhedral, and Lee 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.

Recenzje

'The author, with his light but rigorous mathematical writing style, takes delight in revealing the stars of combinatorial optimization. This is an excellent teaching book; I recommend it highly.' International Statistical Institute

Spis treści

Introduction; Polytopes and linear programming; 1. Matroids and the greedy algorithm; 2. Minimum-weight dipaths; 3. Matroid intersection; 4. Matching; 5. Flows and cuts; 6. Cutting planes; 7. Branch-&-bound; 8. Optimizing submodular functions; Appendix.