Combinatorial Optimization: Networks and Matroids

by Eugene Lawler

Overview

Perceptively written text examines optimization problems that can be formulated in terms of networks and algebraic structures called matroids. Chapters cover shortest paths, network flows, bipartite matching, nonbipartite matching, matroids and the greedy algorithm, matroid intersections, and the matroid parity problems. A suitable text or reference for courses in combinatorial computing and concrete computational complexity in departments of computer science and mathematics.

Product Details

ISBN-13:	9780486143668
Publisher:	Dover Publications
Publication date:	09/18/2012
Series:	Dover Books on Mathematics
Sold by:	Barnes & Noble
Format:	eBook
Pages:	400
File size:	16 MB
Note:	This product may take a few minutes to download.

Table of Contents

	Preface	iii
Chapter 1	Introduction	1
1.	What is Combinatorial Optimization?	1
2.	Some Representative Optimization Problems	2
3.	When is a Problem Solved?	4
4.	The Criterion of Polynomial Boundedness	5
5.	Some Apparently Nonpolynomial-Bounded Problems	8
6.	Methods of Solution	10
	Comments and References	12
Chapter 2	Mathematical Preliminaries	15
1.	Mathematical Prerequisites	15
2.	Sets and Relations	16
3.	Graphs and Digraphs	20
4.	Subgraphs, Cliques, Multigraphs	24
5.	Connectivity in Graphs	26
6.	Connectivity in Digraphs	28
7.	Cocycles and Directed Cocycles	31
8.	Planarity and Duality	32
9.	Eulerian and Hamiltonian Graphs	36
10.	Linear Programming Problems	39
11.	The Simplex Method	43
12.	Geometric Interpretation	48
13.	Duality Theory	53
	Comments and References	58
Chapter 3	Shortest Paths	59
1.	Introduction	59
2.	Some Problem Formulations	61
3.	Bellman's Equations	65
4.	Acyclic Networks	68
5.	Networks with Positive Arcs: Dijkstra's Method	70
6.	Solution by Successive Approximations: Bellman-Ford Method Method	74
7.	Improvements in Efficiency: Yen's Modifications	76
8.	Linear Programming Interpretation and Relaxation Procedures	77
9.	Shortest Paths between all Pairs of Nodes: Matrix Multiplication	82
10.	Floyd-Warshall Method	86
11.	Detection of Negative Cycles	90
12.	Networks with Transit Times	92
13.	The Minimal Cost-to-time Ratio Cycle Problem	94
14.	M Shortest Paths: Dreyfus Method	98
15.	M Shortest Paths without Repeated Nodes	100
	Comments and References	104
Chapter 4	Network Flows	109
1.	Introduction	109
2.	Maximal Flows	110
3.	Maximal Flow Algorithm	114
4.	Efficiency of the Maximal Flow Algorithm	116
5.	Combinatorial Implications of Max-Flow Min-Cut Theorem	120
6.	Linear Programming Interpretation of Max-Flow Min-Cut Theorem	123
7.	Minimum Cost Flows	129
8.	Networks with Losses and Gains	134
9.	Lower Bounds and Circulations	138
10.	The Out-of-Kilter Method	142
11.	Theoretical Improvement in Efficiency of Out-of-Kilter Method	157
12.	Integrality of Flows and the Unimodular Property	160
13.	Application to Project Scheduling	165
14.	Transhipment and Transportation Problems	169
15.	Multiterminal and Multicommodity Flows	173
	Comments and References	177
Chapter 5	Bipartite Matching	182
1.	Introduction	182
2.	Problem Reductions and Equivalences	184
3.	Counterparts of Network Flow Theorems	188
4.	Mendelsohn-Dulmage Theorem	191
5.	Cardinality Matching Algorithm	193
6.	A Special Case: Convex Graphs	196
7.	Max-Min Matching	197
8.	The Hungarian Method for Weighted Matching	201
9.	A Special Case: Gilmore-Gomory Matching	207
10.	A Novel Optimization Criterion: Gale-Shapley Matching	211
	Comments and References	214
Chapter 6	Nonbipartite Matching	217
1.	Introduction	217
2.	Problem Formulations	218
3.	Bidirected Flows	223
4.	Augmenting Paths	226
5.	Trees and Blossoms	229
6.	Cardinality Matching Algorithm	233
7.	Duality Theory	239
8.	Linear Programming Formulation of Weighted Matching Problem	242
9.	An O (n[superscript 4]) Weighted Matching Algorithm	247
10.	An O (n[superscript 3]) Weighted Matching Algorithm	252
11.	The Chinese Postman's Problem	259
	Comments and References	261
Chapter 7	Matroids and the Greedy Algorithm	264
1.	Introduction	264
2.	Three Apparently Unrelated Optimization Problems	265
3.	Matroid Definitions	268
4.	Matching, Transversal, and Partition Matroids	271
5.	Matroid Axiomatics	273
6.	The Matroid Greedy Algorithm	275
7.	Applications of the Greedy Algorithm	278
8.	Matroid Duality	280
9.	Variations of the Greedy Algorithm	283
10.	Prim Spanning Tree Algorithm	285
11.	An Application: Flow Network Synthesis	286
12.	The Steiner Problem and Other Dilemmas	290
	Comments and References	296
Chapter 8	Matroid Intersections	300
1.	Introduction	300
2.	Problem Formulations	301
3.	Augmenting Sequences and Border Graphs	306
4.	Cardinality Intersection Algorithm	313
5.	Duality Theory	315
6.	Generalized Mendelsohn-Dulmage Theorem, Matroid Sums and Matroid Partitions	317
7.	Matroid Partitioning Algorithm	320
8.	The Shannon Switching Game	324
9.	Weighted Augmenting Sequences	326
10.	Primal Weighted Intersection Algorithm	332
11.	Matroid Polyhedra	334
12.	Explanation of Primal-Dual Method	339
13.	Primal-Dual Weighted Intersection Algorithm	345
14.	A Special Case: Directed Spanning Trees	348
	Comments and References	352
Chapter 9	The Matroid Parity Problem	356
1.	Introduction	356
2.	Problem Formulations	358
3.	Augmenting Sequences	363
4.	Generalizations	364
	Comments and References	367
	Author Index	368
	Subject Index	371

Editorial Reviews

Reprints a work originally published by Holt, Rinehart and Winston (New York, 1976). Focusing on combinatorial optimization problems involving matroids, this text is suitable for courses in combinatorial computing and concrete computational complexity in departments of computer science and mathematics. After introducing the basic mathematical principles involved, the book examines shortest paths, network flows, and bipartite matching. It then goes on to discuss non-bipartite matching, the greedy algorithm, matroid intersections, and the matroid parity problem. Annotation c. Book News, Inc., Portland, OR (booknews.com)

Booknews