Combinatorial Optimization: Theory and Algorithms

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

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.

 

What people are saying - Write a review

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

Contents

bMatchings and TJoins
285
122 Minimum Weight TJoins
289
123 TJoins and TCuts
293
124 The PadbergRao Theorem
296
Exercises
299
References
302
Matroids
304
132 Other Matroid Axioms
309

22 Trees Circuits and Cuts
17
23 Connectivity
24
24 Eulerian and Bipartite Graphs
30
25 Planarity
33
26 Planar Duality
40
Exercises
43
References
46
Linear Programming
48
31 Polyhedra
50
32 The Simplex Algorithm
54
33 Implementation of the Simplex Algorithm
57
34 Duality
60
35 Convex Hulls and Polytopes
64
Exercises
66
References
68
Linear Programming Algorithms
71
42 Continued Fractions
74
43 Gaussian Elimination
77
44 The Ellipsoid Method
80
45 Khachiyans Theorem
86
46 Separation and Optimization
88
Exercises
95
References
96
Integer Programming
98
51 The Integer Hull of a Polyhedron
101
52 Unimodular Transformations
105
53 Total Dual Integrality
107
54 Totally Unimodular Matrices
110
55 Cutting Planes
115
56 Lagrangean Relaxation
119
Exercises
121
References
125
Spanning Trees and Arborescences
127
62 Minimum Weight Arborescences
133
63 Polyhedral Descriptions
137
64 Packing Spanning Trees and Arborescences
140
Exercises
144
References
147
Shortest Paths
151
71 Shortest Paths From One Source
152
72 Shortest Paths Between All Pairs of Vertices
156
73 Minimum Mean Cycles
159
Exercises
161
References
163
Network Flows
165
81 MaxFlowMinCut Theorem
166
82 Mengers Theorem
170
83 The EdmondsKarp Algorithm
172
84 Blocking Flows and Fujishiges Algorithm
174
85 The GoldbergTarjan Algorithm
176
86 GomoryHu Trees
180
87 The Minimum Capacity of a Cut in an Undirected Graph
186
Exercises
189
References
194
Minimum Cost Flows
198
92 An Optimality Criterion
201
93 Minimum Mean CycleCancelling Algorithm
203
94 Successive Shortest Path Algorithm
207
95 Orlins Algorithm
211
96 The Network Simplex Algorithm
214
97 Flows Over Time
218
Exercises
220
References
224
Maximum Matchings
227
101 Bipartite Matching
228
102 The Tutte Matrix
230
103 Tuttes Theorem
232
104 EarDecompositions of FactorCritical Graphs
235
105 Edmonds Matching Algorithm
241
Exercises
250
References
254
Weighted Matching
257
111 The Assignment Problem
258
112 Outline of the Weighted Matching Algorithm
259
113 Implementation of the Weighted Matching Algorithm
262
114 Postoptimality
276
115 The Matching Polytope
277
Exercises
280
References
282
133 Duality
313
134 The Greedy Algorithm
317
135 Matroid Intersection
322
136 Matroid Partitioning
327
137 Weighted Matroid Intersection
329
Exercises
332
References
334
Generalizations of Matroids
337
142 Polymatroids
341
143 Minimizing Submodular Functions
345
144 Schrijvers Algorithm
347
145 Symmetric Submodular Functions
351
Exercises
353
References
355
NPCompleteness
359
152 Churchs Thesis
362
153 P and NP
367
154 Cooks Theorem
371
155 Some Basic NPComplete Problems
375
156 The Class coNP
382
157 NPHard Problems
384
Exercises
387
References
391
Approximation Algorithms
393
161 Set Covering
394
162 The MaxCut Problem
399
163 Colouring
405
164 Approximation Schemes
413
165 Maximum Satisfiability
415
166 The PCP Theorem
420
167 LReductions
424
Exercises
430
References
434
The Knapsack Problem
438
172 A Pseudopolynomial Algorithm
442
173 A Fully Polynomial Approximation Scheme
444
Exercises
447
BinPacking
449
182 An Asymptotic Approximation Scheme
455
183 The KarmarkarKarp Algorithm
459
Exercises
462
References
464
Multicommodity Flows and EdgeDisjoint Paths
467
191 Multicommodity Flows
468
192 Algorithms for Multicommodity Flows
471
193 Directed EdgeDisjoint Paths Problem
476
194 Undirected EdgeDisjoint Paths Problem
479
Exercises
485
References
487
Network Design Problems
490
201 Steiner Trees
492
202 The RobinsZelikovsky Algorithm
497
203 Survivable Network Design
502
204 A PrimalDual Approximation Algorithm
505
205 Jains Algorithm
514
Exercises
520
References
522
The Traveling Salesman Problem
527
212 Euclidean TSP
532
213 Local Search
539
214 The Traveling Salesman Polytope
545
215 Lower Bounds
551
216 BranchandBound
553
Exercises
556
References
559
Facility Location
563
222 Rounding Linear Programming Solutions
565
223 PrimalDual Algorithms
567
224 Scaling and Greedy Augmentation
573
225 Bounding the Number of Facilities
576
226 Local Search
579
227 Capacitated Facility Location Problems
585
228 Universal Facility Location
588
Exercises
594
References
596
Notation Index
599
Author Index
602
Subject Index
613
Copyright

Other editions - View all

Common terms and phrases

References to this book

All Book Search results »

Bibliographic information