Geometric algorithms and combinatorial optimization

VORBLATT......Page 1
TITELBLATT......Page 3
IMPRESSUM......Page 4
VORWORT......Page 5
VERZEICHNIS_INHALT......Page 9
Basic Notation......Page 13
Hulls, Independence, Dimension......Page 15
Eigenvalues, Positive Definite Matrices......Page 16
Vector Norms, Balls......Page 17
Matrix Norms......Page 19
Some Inequalities......Page 20
Polyhedra, Inequality Systems......Page 21
Linear (Diophantine) Equations and Inequalities......Page 23
Linear Programming and Duality......Page 26
0.2 Graph Theory......Page 28
Graphs......Page 29
Digraphs......Page 30
Walks, Paths, Circuits, Trees......Page 31
Problems......Page 33
Algorithms and Turing Machines......Page 34
Time and Space Complexity......Page 35
Decision Problems: The Classes P and NP......Page 36
The Running Time of Oracle Algorithms......Page 38
Transformation and Reduction......Page 39
NP-Completeness and Related Notions......Page 40
Encoding Length of Numbers......Page 41
Polynomial and Strongly Polynomial Computations......Page 44
Polynomial Time Approximation of Real Numbers......Page 45
Gaussian Elimination......Page 48
Gram-Schmidt Orthogonalization......Page 52
The Simplex Method......Page 53
Computation of the Hermite Normal Form......Page 55
Chapter 2: Algorithmic Aspects of Convex Sets: Formulation of the Problems......Page 58
2.1 Basic Algorithmic Problems for Convex Sets......Page 59
2.2 Nondeterministic Decision Problems for Convex Sets......Page 68
Chapter 3. The Ellipsoid Method......Page 76
Properties of Ellipsoids......Page 78
Description of the Basuc Ellipsoid Method......Page 85
Proofs of Some Lemmas......Page 88
Implementation Problems and Polynomiality......Page 92
Some Examples......Page 95
3.2 The Central-Cut Ellipsoid Method......Page 98
3.3 The Shallow-Cut Ellipsoid Method......Page 106
4.1 Summary of Results......Page 114
4.2 Optimization from Separation......Page 117
4.3 Optimization from Membership......Page 119
4.4 Equivalence of the Basic Problems......Page 126
4.5 Some Negative Results......Page 130
4.6 Further Algorithmic Problems for Convex Bodies......Page 134
The Sum......Page 140
The Intersection......Page 141
Polars. Blockers, Antiblockers......Page 143
Chapter 5. Diophantie Approximation and Basic Reduction......Page 145
5.1 Continued Fractions......Page 146
5.2 Simultaneous Diophantine Approximation: Formulation of the Problems......Page 150
5.3 Basic Reduction in Lattices......Page 151
5.4 More on Lattice Algorithms......Page 162
6.1 Optimization over Polyhedra: A Preview......Page 169
6.2 Complexity of Rational Polyhedra......Page 174
6.3 Weak and Strong Problems......Page 182
6.4 Equivalence of Strong Optimization and Separation......Page 186
6.5 Further Problems for Polyhedra......Page 193
6.6 Strongly Polynomial Algorithms......Page 200
6.7 Integer Programming in Bounded Dimension......Page 204
7.1 Flows and Cuts......Page 209
7.2 Arborescences......Page 213
7.3 Matching......Page 215
7.4 Edge Coloring......Page 220
7.5 Matroids......Page 222
7.6 Subset Sums......Page 230
7.7 Concluding Remarks......Page 233
8.1 Blocking Hypergraphs and Polyhedra......Page 237
8.2 Problems on Bipartite Graphs......Page 241
8.3 Flows, Paths, Chains, and Cuts......Page 245
Arborescences and Rooted Cuts......Page 254
Trees and Cuts in Undirected Graphs......Page 259
Dicuts and Dijoins......Page 263
8.5 Matchings, Odd Cuts, and  Generalizations......Page 266
Matching......Page 267
b-Matching......Page 269
T-Joins and T-Cuts......Page 271
Cinese Postmen and Traveling Salesmen......Page 274
8.6 Milticommodity Flows......Page 278
9.1 Odd Cicuit Constraints and t-Perfect Graphs......Page 284
9.2 Clique Constraints and Perfect Graphs......Page 288
Antiblockers of Hypergraphs......Page 296
9.3 Orthonormal Representations......Page 297
9.4 Coloring Perfect Graphs......Page 308
9.5 More Algorithmic Results on Stable Sets......Page 311
10.1 Submodular Functions and Polymatroids......Page 316
10.2 Algorithms for Polymatroids and Submodular Functions......Page 320
Packing Bases of a Matroid......Page 323
10.3 Submodular Functions an Lattce, Intersecting, and Crossing Families......Page 325
10.4 Odd Submodular Function Minimization and Extensions......Page 337
VERZEICHNIS_LITERATUR......Page 343
VERZEICHNIS_ABKUERZUNGEN......Page 359
Author Index......Page 363
Subject Index......Page 367
WERBUNG......Page 375
Five Basic Problems......Page 379