Book:Bernhard H. Korte/Combinatorial Optimization: Theory and Algorithms/Sixth Edition
Jump to navigation
Jump to search
Bernhard H. Korte and Jens Vygen: Combinatorial Optimization: Theory and Algorithms (6th Edition)
Published $\text {2018}$, Springer-Verlag
- ISBN 978-3-540-71843-7
Subject Matter
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$\quad$Matroids
- 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$\quad$Generalizations 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
Further Editions
- 2000: Bernhard H. Korte and Jens Vygen: Combinatorial Optimization: Theory and Algorithms
- 2002: Bernhard H. Korte and Jens Vygen: Combinatorial Optimization: Theory and Algorithms (2nd ed.)
- 2006: Bernhard H. Korte and Jens Vygen: Combinatorial Optimization: Theory and Algorithms (3rd ed.)
- 2008: Bernhard H. Korte and Jens Vygen: Combinatorial Optimization: Theory and Algorithms (4th ed.)
- 2012: Bernhard H. Korte and Jens Vygen: Combinatorial Optimization: Theory and Algorithms (5th ed.)