Combinatorial optimization theory and algorithms

Description

Cover Editorial Board Title: Combinatorial Optimization Theory and Algorithms Copyright Springer-Verlag Berlin Heidelberg 2012 ISSN 0937-5511 ISBN 978-3-642-24487-2 e-ISBN 978-3-642-24488-9 DOI 10.1007/978-3-642-24488-9 Preface to the Fifth Edition Preface to the Fourth Edition Preface to the Third Edition Preface to the Second Edition Preface to the First Edition Table of Contents 1 Introduction 1.1 Enumeration 1.2 Running Time of Algorithms 1.3 Linear Optimization Problems 1.4 Sorting Exercises References 2 Graphs 2.1 Basic Definitions 2.2 Trees, Circuits, and Cuts 2.3 Connectivity 2.4 Eulerian and Bipartite Graphs 2.5 Planarity 2.6 Planar Duality Exercises References 3 Linear Programming 3.1 Polyhedra 3.2 The Simplex Algorithm 3.3 Implementation of the Simplex Algorithm 3.4 Duality 3.5 Convex Hulls and Polytopes Exercises References 4 Linear Programming Algorithms 4.1 Size of Vertices and Faces 4.2 Continued Fractions 4.3 Gaussian Elimination 4.4 The Ellipsoid Method 4.5 Khachiyan's Theorem 4.6 Separation and Optimization Exercises References 5 Integer Programming 5.1 The Integer Hull of a Polyhedron 5.2 Unimodular Transformations 5.3 Total Dual Integrality 5.4 Totally Unimodular Matrices 5.5 Cutting Planes 5.6 Lagrangean Relaxation Exercises References 6 Spanning Trees and Arborescences 6.1 Minimum Spanning Trees 6.2 Minimum Weight Arborescences 6.3 Polyhedral Descriptions 6.4 Packing Spanning Trees and Arborescences Exercises References 7 Shortest Paths 7.1 Shortest Paths From One Source 7.2 Shortest Paths Between All Pairs of Vertices 7.3 Minimum Mean Cycles Exercises References 8 Network Flows 8.1 Max-Flow-Min-Cut Theorem 8.2 Menger's Theorem 8.3 The Edmonds-Karp Algorithm 8.4 Dinic's, Karzanov's, and Fujishige's Algorithm 8.5 The Goldberg-Tarjan Algorithm 8.6 Gomory-Hu Trees 8.7 The Minimum Capacity of a Cut in an Undirected Graph Exercises References 9 Minimum Cost Flows 9.1 Problem Formulation 9.2 An Optimality Criterion 9.3 Minimum Mean Cycle-Cancelling Algorithm 9.4 Successive Shortest Path Algorithm 9.5 Orlin's Algorithm 9.6 The Network Simplex Algorithm 9.7 Flows Over Time Exercises References 10 Maximum Matchings 10.1 Bipartite Matching 10.2 The Tutte Matrix 10.3 Tutte’s Theorem 10.4 Ear-Decompositions of Factor-Critical Graphs 10.5 Edmonds’ Matching Algorithm Exercises References 11 Weighted Matching 11.1 The Assignment Problem 11.2 Outline of the Weighted Matching Algorithm 11.3 Implementation of the Weighted Matching Algorithm 11.4 Postoptimality 11.5 The Matching Polytope Exercises References 12 b-Matchings and T-Joins 12.1 b-Matchings 12.2 Minimum Weight T-Joins 12.3 T-Joins and T-Cuts 12.4 The Padberg-Rao Theorem Exercises References 13 Matroids 13.1 Independence Systems and Matroids 13.2 Other Matroid Axioms 13.3 Duality 13.4 The Greedy Algorithm 13.5 Matroid Intersection 13.6 Matroid Partitioning 13.7 Weighted Matroid Intersection Exercises References 14 Generalizations of Matroids 14.1 Greedoids 14.2 Polymatroids 14.3 Minimizing Submodular Functions 14.4 Schrijver's Algorithm 14.5 Symmetric Submodular Functions Exercises References 15 NP-Completeness 15.1 Turing Machines 15.2 Church's Thesis 15.3 P and NP 15.4 Cook's Theorem 15.5 Some Basic NP-Complete Problems 15.6 The Class coNP 15.7 NP-Hard Problems Exercises References 16 Approximation Algorithms 16.1 Set Covering 16.2 The Max-Cut Problem 16.3 Colouring 16.4 Approximation Schemes 16.5 Maximum Satisfiability 16.6 The PCP Theorem 16.7 L-Reductions Exercises References 17 The Knapsack Problem 17.1 Fractional Knapsack and Weighted Median Problem 17.2 A Pseudopolynomial Algorithm 17.3 A Fully Polynomial Approximation Scheme 17.4 Multi-Dimensional Knapsack Exercises References 18 Bin-Packing 18.1 Greedy Heuristics 18.2 An Asymptotic Approximation Scheme 18.3 The Karmarkar-Karp Algorithm Exercises References 19 Multicommodity Flows and Edge-Disjoint Paths 19.1 Multicommodity Flows 19.2 Algorithms for Multicommodity Flows 19.3 Sparsest Cut and Max-Flow Min-Cut Ratio 19.4 The Leighton-Rao Theorem 19.5 Directed Edge-Disjoint Paths Problem 19.6 Undirected Edge-Disjoint Paths Problem Exercises References 20 Network Design Problems 20.1 Steiner Trees 20.2 The Robins-Zelikovsky Algorithm 20.3 Survivable Network Design 20.4 A Primal-Dual Approximation Algorithm 20.5 Jain's Algorithm Exercises References 21 The Traveling Salesman Problem 21.1 Approximation Algorithms for the TSP 21.2 Euclidean TSP 21.3 Local Search 21.4 The Traveling Salesman Polytope 21.5 Lower Bounds 21.6 Branch-and-Bound Exercises References 22 Facility Location 22.1 The Uncapacitated Facility Location Problem 22.2 Rounding Linear Programming Solutions 22.3 Primal-Dual Algorithms 22.4 Scaling and Greedy Augmentation 22.5 Bounding the Number of Facilities 22.6 Local Search 22.7 Capacitated Facility Location Problems 22.8 Universal Facility Location Exercises References Notation Index Author Index Subject Index