Combinatorial Optimization: Theory and Algorithms

Front Cover
Springer Science & Business Media, Jan 10, 2012 - Mathematics - 660 pages
0 Reviews

This comprehensive textbook on combinatorial optimization places special emphasis on theoretical results and algorithms with provably good performance, in contrast to heuristics. It is based on numerous courses on combinatorial optimization and specialized topics, mostly at graduate level. This book reviews the fundamentals, covers the classical topics (paths, flows, matching, matroids, NP-completeness, approximation algorithms) in detail, and proceeds to advanced and recent topics, some of which have not appeared in a textbook before. Throughout, it contains complete but concise proofs, and also provides numerous exercises and references.

This fifth edition has again been updated, revised, and significantly extended, with more than 60 new exercises and new material on various topics, including Cayley's formula, blocking flows, faster b-matching separation, multidimensional knapsack, multicommodity max-flow min-cut ratio, and sparsest cut. Thus, this book represents the state of the art of combinatorial optimization.

 

What people are saying - Write a review

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

Contents

1 Introduction
1
2 Graphs
13
3 Linear Programming
50
4 Linear Programming Algorithms
73
5 Integer Programming
100
6 Spanning Trees and Arborescences
131
7 Shortest Paths
156
8 Network Flows
173
14 Generalizations of Matroids
354
15 NPCompleteness
377
16 Approximation Algorithms
413
17 The Knapsack Problem
458
18 BinPacking
471
19 Multicommodity Flows and EdgeDisjoint Paths
489
20 Network Design Problems
521
21 The Traveling Salesman Problem
557

9 Minimum Cost Flows
211
10 Maximum Matchings
241
11 Weighted Matching
272
12 bMatchings and TJoins
301
13 Matroids
321
22 Facility Location
593
Notation Index
629
Author Index
633
Subject Index
644
Copyright

Other editions - View all

Common terms and phrases

Bibliographic information