Combinatorial Optimization: Polyhedra and Efficiency, Volume 1

Front Cover
Springer, 2003 - Business & Economics - 1881 pages
0 Reviews
This book offers an in-depth overview of polyhedral methods and efficient algorithms in combinatorial optimization.These methods form a broad, coherent and powerful kernel in combinatorial optimization, with strong links to discrete mathematics, mathematical programming and computer science. In eight parts, various areas are treated, each starting with an elementary introduction to the area, with short, elegant proofs of the principal results, and each evolving to the more advanced methods and results, with full proofs of some of the deepest theorems in the area. Over 4000 references to further research are given, and historical surveys on the basic subjects are presented.

What people are saying - Write a review

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

Contents

Introduction
1
General preliminaries
9
Dilworth truncation 820
13
Preliminaries on graphs
16
42
25
45
26
51
29
55
30
Matroid matching 745
273
Weighted bipartite matching and the assignment
285
The traveling salesman problem 981
296
Submodular functions and polymatroids 766
299
Linear programming methods and the bipartite matching
301
Bipartite edge cover and stable set
315
Bipartite edgecolouring
321
Bipartite bmatchings and transportation
337

59
31
Submodularity more generally 826
32
67
33
78
37
Preliminaries on algorithms and complexity
38
Preliminaries on polyhedra and linear and integer
59
Submodular function minimization 786
86
unit lengths
87
nonnegative lengths
96
arbitrary lengths
107
Tpaths 1279
110
Disjoint paths
131
Matroid union 725
143
Planar graphs 1296
146
Maximum flow
148
41
165
Circulations and transshipments
170
Minimumcost flows and circulations
177
Minimum directed cut covers and packing directed cuts 946
180
Path and flow polyhedra and total unimodularity
198
Partially ordered sets and path coverings
217
Connectivity and GomoryHu trees
237
Cardinality bipartite matching and vertex cover
259
Submodular functions on directed graphs 1018
362
Transversals
378
Common transversals
393
Cliques Stable Sets and Colouring 1081
408
Cardinality nonbipartite matching
413
Graph orientation 1035
432
The matching polytope
438
Weighted nonbipartite matching algorithmically
453
Nonbipartite edge cover
461
Tjoins undirected shortest paths and the Chinese
485
Matroids and multiflows 1419
494
Covering and antiblocking in hypergraphs 1428
532
bmatchings
546
Capacitated bmatchings
562
Simple bmatchings and bfactors
569
bedge covers
575
Upper and lower bounds
584
Bidirected graphs
594
Homotopy and graphs on surfaces 1352
597
The dimension of the perfect matching polytope
609
The perfect matching lattice
619
Copyright

Other editions - View all

About the author (2003)

Alexander Schrijver is one of the most respected researchers in this area. He has won the Dantzig award, the Fulkerson prize (twice) and the Lanchester Prize for his earlier classic text on "Theory of Linear and Integer Programming".

Bibliographic information