# Book:Bernhard H. Korte/Combinatorial Optimization: Theory and Algorithms/Sixth Edition

## Bernhard H. Korte and Jens Vygen: Combinatorial Optimization: Theory and Algorithms (6th Edition)

Published $\text {2018}$, Springer-Verlag

ISBN 978-3-540-71843-7

### Contents

1 $\quad$Introduction
1.1 $\quad$ Enumeration
1.2 $\quad$ Running Time of Algorithms
1.3 $\quad$ Linear Optimization Problems
1.4 $\quad$ Sorting
Exercises
References

2 $\quad$Graphs
2.1 $\quad$ Basic Definitions
2.2 $\quad$ Trees, Circuits, and Cuts
2.3 $\quad$ Connectivity
2.4 $\quad$ Eulerian and Bipartite Graphs
2.5 $\quad$ Planarity
2.6 $\quad$ Planar Duality
Exercises
References

3 $\quad$Linear Programming
3.1 $\quad$ Polyhedra
3.2 $\quad$ The Simplex Algorithm
3.3 $\quad$ Implementation of the Simplex Algorithm
3.4 $\quad$ Duality
3.5 $\quad$ Convex Hulls and Polytopes
Exercises
References

4 $\quad$Linear Programming Algorithms
4.1 $\quad$ Size of Vertices and Faces
4.2 $\quad$ Continued Fractions
4.3 $\quad$ Gaussian Elimination
4.4 $\quad$ The Ellipsoid Method
4.5 $\quad$ Khachiyan's Theorem
4.6 $\quad$ Separation and Optimization
Exercises
References

5 $\quad$Integer Programming
5.1 $\quad$ The Integer Hull of a Polyhedron
5.2 $\quad$ Unimodular Transformations
5.3 $\quad$ Total Dual Integrality
5.4 $\quad$ Totally Unimodular Matrices
5.5 $\quad$ Cutting Planes
5.6 $\quad$ Lagrangian Relaxation
Exercises
References

6 $\quad$Spanning Trees and Arborescences
6.1 $\quad$ Minimum Spanning Tree
6.2 $\quad$ Minimum Weight Arborescences
6.3 $\quad$ Polyhedral Descriptions
6.4 $\quad$ Packing Spanning Trees and Arborescences
Exercises
References

7 $\quad$Shortest Paths
7.1 $\quad$ Shortest Paths From One Source
7.2 $\quad$ Shortest Paths Between All Pairs of Vertices
7.3 $\quad$ Minimum Mean Cycles
7.4 $\quad$ Shallow-Light Trees
Exercises
References

8 $\quad$Network Flows
8.1 $\quad$ Max-Flow-Min-Cut Theorem
8.2 $\quad$ Menger's Theorem
8.3 $\quad$ The Edmonds-Karp Algorithm
8.4 $\quad$ Dinic's, Karanoz's, and Fujishige's Algorithm
8.5 $\quad$ The Goldberg-Tarjan Algorithm
8.6 $\quad$ Gomory-Hu Trees
8.7 $\quad$ The Minimum Capacity of a Cut in an Undirected Graph
Exercises
References

9 $\quad$Minimum Cost Flows
9.1 $\quad$ Problem Formulation
9.2 $\quad$ An Optimality Criterion
9.3 $\quad$ Minimum Mean Cycle-Cancelling Algorithm
9.4 $\quad$ Successive Shortest Path Algorithm
9.5 $\quad$ Orlin's Algorithm
9.6 $\quad$ The Network Simplex Algorithm
9.7 $\quad$ Flows Over time
Exercises
References

10$\quad$Maximum Matchings
10.1 $\quad$ Bipartite Matchings
10.2 $\quad$ The Tutte Matrix
10.3 $\quad$ Tutte's Theorem
10.4 $\quad$ Ear-Decomposition of Factor-Critical Graphs
10.5 $\quad$ Edmonds' Matching Algorithm
Exercises
References

11$\quad$Weighted Matching
11.1 $\quad$ The Assignment Problem
11.2 $\quad$ Outline of the Weighted Matching Algorithm
11.3 $\quad$ Implementation of the Weighted Matching Algorithm
11.4 $\quad$ Postoptimality
11.5 $\quad$ The Matching Polytope
Exercises
References

12$\quad$$\beta-Matchings and T-Joins 12.1 \quad \beta-Matchings 12.2 \quad Minimum Weight T-Joins 12.3 \quad T-Joins and T-Cuts 12.4 \quad The Padberg-Rao Theorem Exercises References 13\quadMatroids 13.1 \quad Independence Systems and Matroids 13.2 \quad Other Matroid Axioms 13.3 \quad Duality 13.4 \quad The Greedy Algorithm 13.5 \quad Matroid Intersection 13.6 \quad Matroid Partitioning 13.7 \quad Weighted Matroid Intersection Exercises References 14\quadGeneralizations of Matroids 14.1 \quad Greedoids 14.2 \quad Polymatroids 14.3 \quad Minimizing Submodular Functions 14.4 \quad Schrijver's Algorithm 14.5 \quad Symmetric Submodular Functions 14.6 \quad Submodular Function Maximization Exercises References 15\quad$$NP$-Completeness
15.1 $\quad$ Turing Machines
15.2 $\quad$ Church's Thesis
15.3 $\quad$ $P$ and $NP$
15.4 $\quad$ Cook's Theorem
15.5 $\quad$ Some Basic $NP$-Complete Problems
15.6 $\quad$ The Class $coNP$
15.7 $\quad$ $NP$-Hard Problems
Exercises
References

16$\quad$Approximation Algorithms
16.1 $\quad$ Set Covering
16.2 $\quad$ The Max-Cut Problem
16.3 $\quad$ Colouring
16.4 $\quad$ Approximation Schemes
16.5 $\quad$ Maximum Satisfiability
16.6 $\quad$ The $PCP$ Theorem
16.7 $\quad$ L-Reductions
Exercises
References

17$\quad$The Knapsack Problem
17.1 $\quad$ Fractional Knasak and Weighted Median Problem
17.2 $\quad$ A Pseudopolynomial Algorithm
17.3 $\quad$ A Fully Polynomial Approximation Scheme
17.4 $\quad$ Multi-Dimensional Knapsack
17.5 $\quad$ The Nemhauser-Ullmann Algorithm
Exercises
References

18$\quad$Bin-Packing
18.1 $\quad$ Greedy Heuristics
18.2 $\quad$ An Asymptotic Approximation Scheme
18.3 $\quad$ The Karmarkar-Karp Algorithm
Exercises
References

19$\quad$Multicommodity Flows and Edge-Disjoint Paths
19.1 $\quad$ Multicommodity Flows
19.2 $\quad$ Algorithms for Multicommodity Flows
19.3 $\quad$ Sparsest Cut and Max-Flow Min-Cut Ratio
19.4 $\quad$ The Leighton-Rao Theorem
19.5 $\quad$ Directed Edge-Disjoint Paths Problem
19.6 $\quad$ Undirected Edge-Disjoint Paths Problem
Exercises
References

20$\quad$Network Design Problems
20.1 $\quad$ Steiner Trees
20.2 $\quad$ The Robins-Zelikovsky Algorithm
20.3 $\quad$ Rounding the Directed Component LP
20.4 $\quad$ Survivable Network Design
20.5 $\quad$ A Primal-Dual Approximation Algorithm
20.6 $\quad$ Jain's Algorithm
20.7 $\quad$ The VPN Problem
Exercises
References

21$\quad$The Traveling Salesman Problem
21.1 $\quad$ Approximation Algorithms for the TSP
21.2 $\quad$ Euclidean TSP
21.3 $\quad$ Local Search
21.4 $\quad$ The Traveling Salesman Polytope
21.5 $\quad$ Lower Bounds
21.6 $\quad$ Branch-and-Bound
Exercises
References

22$\quad$Facility Location
22.1 $\quad$ The Uncapacitated Facility Location Problem
22.2 $\quad$ Rounding Linear Programming Solutions
22.3 $\quad$ Primal-Dual Algorithms
22.4 $\quad$ Scaling and Greedy Augmentation
22.5 $\quad$ Bounding the Number of Facilities
22.6 $\quad$ Local Search
22.7 $\quad$ Capacitated Facility Location Problems
22.8 $\quad$ Universal Facility Location
Exercises
References

Notation Index
Author Index
Subject Index