Combinatorial Optimization: Theory and Algorithms

Front Cover
Springer Science & Business Media, Nov 4, 2007 - Mathematics - 627 pages

Now fully updated in a third edition, this is a comprehensive textbook on combinatorial optimization. It puts special emphasis on theoretical results and algorithms with provably good performance, in contrast to heuristics. The book contains complete but concise proofs, also for many deep results, some of which have not appeared in print before. Recent topics are covered as well, and numerous references are provided. This third edition contains a new chapter on facility location problems, an area which has been extremely active in the past few years. Furthermore there are several new sections and further material on various topics. New exercises and updates in the bibliography were added.

 

Contents

Introduction
1
Graphs
13
Linear Programming 49
48
Linear Programming Algorithms
71
Integer Programming 99
98
Spanning Trees and Arborescences
127
Shortest Paths
151
Network Flows
165
10
227
15
359
Network Design Problems 491
490
The Traveling Salesman Problem
527
Facility Location
563
Notation Index
599
Subject Index
613
Copyright

Minimum Cost Flows 199
198

Other editions - View all

Common terms and phrases

Bibliographic information