Combinatorial Optimization : Theory and Algorithms

by Korte, Bernhard

• ISBN13: 9783540672265
• ISBN10: 3540672265
• eBook ISBN(s): 9783662217085
• Edition: 1st
• Format: Hardcover
• Copyright: 2000-08-01
• Publisher: SPRINGER VERLAG INC
• More Book Details

Summary

Textbook with special emphasis on theoretical results and algorithms with provably good performance. Contains complete proofs, some which may never have appeared in a book before. Many recent topics are covered and references are provided.

Table of Contents

Introduction	1	(12)
Enumeration	2	(3)
Running Time of Algorithms	5	(3)
Linear Optimization Problems	8	(1)
Sorting	9	(4)
Exercises	11	(1)
References	12	(1)
Graphs	13	(36)
Basic Definitions	13	(4)
Trees, Circuits, and Cuts	17	(7)
Connectivity	24	(6)
Eulerian and Bipartite Graphs	30	(3)
Planarity	33	(7)
Planar Duality	40	(9)
Exercises	42	(4)
References	46	(3)
Linear Programming	49	(16)
Polyhedra	50	(3)
The Simplex Algorithm	53	(4)
Duality	57	(3)
Convex Hulls and Polytopes	60	(5)
Exercises	62	(1)
References	63	(2)
Linear Programming Algorithms	65	(26)
Size of Vertices and Faces	65	(3)
Continued Fractions	68	(2)
Gaussian Elimination	70	(4)
The Ellipsoid Method	74	(6)
Khachiyan's Theorem	80	(2)
Separation and Optimization	82	(9)
Exercises	88	(1)
References	89	(2)
Integer Programming	91	(26)
The Integer Hull of a Polyhedron	92	(4)
Unimodular Transformations	96	(1)
Total Dual Integrality	97	(4)
Totally Unimodular Matrices	101	(5)
Cutting Planes	106	(4)
Lagrangean Relaxation	110	(7)
Exercises	112	(3)
References	115	(2)
Spanning Trees and Arborescences	117	(22)
Minimum Spanning Trees	118	(3)
Minimum Weight Arborescences	121	(4)
Polyhedral Descriptions	125	(3)
Packing Spanning Trees and Arborescences	128	(11)
Exercises	132	(3)
References	135	(4)
Shortest Paths	139	(14)
Shortest Paths From One Source	140	(4)
Shortest Paths Between All Pairs of Vertices	144	(3)
Minimum Mean Cycles	147	(6)
Exercises	149	(2)
References	151	(2)
Network Flows	153	(32)
Max-Flow-Min-Cut Theorem	154	(4)
Menger's Theorem	158	(2)
The Edmonds-Karp Algorithm	160	(2)
Blocking Flows	162	(1)
The Goldberg-Tarjan Algorithm	163	(5)
Gomory-Hu Trees	168	(6)
The Minimum Cut in an Undirected Graph	174	(11)
Exercises	176	(5)
References	181	(4)
Minimum Cost Flows	185	(20)
Problem Formulation	185	(2)
An Optimality Criterion	187	(2)
Minimum Mean Cycle-Cancelling Algorithm	189	(4)
Successive Shortest Path Algorithm	193	(4)
Orlin's Algorithm	197	(8)
Exercises	201	(2)
References	203	(2)
Maximum Matchings	205	(30)
Bipartite Matching	206	(2)
The Tutte Matrix	208	(2)
Tutte's Theorem	210	(3)
Ear-Decompositions of Factor-Critical Graphs	213	(6)
Edmonds' Matching Algorithm	219	(16)
Exercises	228	(3)
References	231	(4)
Weighted Matching	235	(26)
The Assignment Problem	236	(1)
Outline of the Weighted Matching Algorithm	237	(3)
Implementation of the Weighted Matching Algorithm	240	(13)
Postoptimality	253	(1)
The Matching Polytope	254	(7)
Exercises	257	(2)
References	259	(2)
b-Matchings and T-Joins	261	(18)
b-Matchings	261	(4)
Minimum Weight T-Joins	265	(4)
T-Joins and T-Cuts	269	(3)
The Padberg-Rao Theorem	272	(7)
Exercises	275	(3)
References	278	(1)
Matroids	279	(32)
Independence Systems and Matroids	279	(4)
Other Matroid Axioms	283	(4)
Duality	287	(4)
The Greedy Algorithm	291	(5)
Matroid Intersection	296	(4)
Matroid Partitioning	300	(2)
Weighted Matroid Intersection	302	(9)
Exercises	305	(3)
References	308	(3)
Generalizations of Matroids	311	(16)
Greedoids	311	(4)
Polymatroids	315	(4)
Minimizing Submodular Functions	319	(8)
Exercises	323	(2)
References	325	(2)
NP-Completeness	327	(34)
Turing Machines	327	(2)
Church's Thesis	329	(5)
P and NP	334	(4)
Cook's Theorem	338	(4)
Some Basic NP-Complete Problems	342	(7)
The Class coNP	349	(2)
NP-Hard Problems	351	(10)
Exercises	354	(4)
References	358	(3)
Approximation Algorithms	361	(36)
Set Covering	362	(5)
Colouring	367	(6)
Approximation Schemes	373	(3)
Maximum Satisfiability	376	(4)
The PCP Theorem	380	(4)
L-Reductions	384	(13)
Exercises	390	(3)
References	393	(4)
The Knapsack Problem	397	(10)
Fractional Knapsack and Weighted Median Problem	397	(3)
A Pseudopolynomial Algorithm	400	(2)
A Fully Polynomial Approximation Scheme	402	(5)
Exercises	405	(1)
References	406	(1)
Bin-Packing	407	(16)
Greedy Heuristics	407	(5)
An Asymptotic Approximation Scheme	412	(4)
The Karmarkar-Karp Algorithm	416	(7)
Exercises	419	(2)
References	421	(2)
Multicommodity Flows and Edge-Disjoint Paths	423	(22)
Multicommodity Flows	424	(3)
Algorithms for Multicommodity Flows	427	(4)
Directed Edge-Disjoint Paths Problem	431	(4)
Undirected Edge-Disjoint Paths Problem	435	(10)
Exercises	440	(3)
References	443	(2)
Network Design Problems	445	(28)
Steiner Trees	446	(4)
Survivable Network Design	450	(3)
A Primal-Dual Approximation Algorithm	453	(9)
Jain's Algorithm	462	(11)
Exercises	467	(3)
References	470	(3)
The Traveling Salesman Problem	473	(34)
Approximation Algorithms for the TSP	473	(5)
Euclidean TSPs	478	(7)
Local Search	485	(6)
The Traveling Salesman Polytope	491	(6)
Lower Bounds	497	(2)
Branch-and-Bound	499	(8)
Exercises	501	(2)
References	503	(4)
Notation Index	507	(4)
Author Index	511	(8)
Subject Index	519