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

From ProofWiki
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

Retrieved from "https://proofwiki.org/w/index.php?title=Book:Bernhard_H._Korte/Combinatorial_Optimization:_Theory_and_Algorithms/Sixth_Edition&oldid=501996"