Combinatorial Optimization

Name: Combinatorial Optimization | Algorithms and Complexity
Brand: Dover Publications
Price: 26.49 EUR
Availability: OnlineOnly

Algorithms and Complexity

Christos H. Papadimitriou Kenneth Steiglitz(Autor*in)

Dover Publications (Verlag)

Erschienen am 26. April 2013

942 Seiten

E-Book

ePUB mit Adobe-DRM

Systemvoraussetzungen

978-0-486-32013-7 (ISBN)

26,49 €inkl. 7% MwSt.

Systemvoraussetzungen

für ePUB mit Adobe-DRM

E-Book Einzellizenz

Als Download verfügbar

Beschreibung

Weitere Details

Weitere Ausgaben

Inhalt

Cover
Title
Copyright
Contents
Preface
Preface2
Chapter 1 Optimization Problems
1.1 Introduction
1.2 Optimization Problems
1.3 Neighborhoods
1.4 Local and Global Optima
1.5 Convex Sets and Functions
1.6 Convex Programming Problems
Problems
Notes and References
Appendix: Terminology and Notation
A.1 Linear Algebra
A.2 Graph Theory
A.3 Pidgin Algol
Chapter 2 The Simplex Algorithm
2.1 Forms of the Linear Programming Problem
2.2 Basic Feasible Solutions
2.3 The Geometry of Linear Programs
2.3.1 Linear and Affine Spaces
2.3.2 Convex Polytopes
2.3.3 Polytopes and LP
2.4 Moving from bfs to bfs
2.5 Organization of a Tableau
2.6 Choosing a Profitable Column
2.7 Degeneracy and Bland's Anticycling Algorithm
2.8 Beginning the Simplex Algorithm
2.9 Geometric Aspects of Pivoting
Problems
Notes and References
Chapter 3 Duality
3.1 The Dual of a Linear Program in General Form
3.2 Complementary Slackness
3.3 Farkas' Lemma
3.4 The Shortest-Path Problem and Its Dual
3.5 Dual Information in the Tableau
3.6 The Dual Simplex Algorithm
3.7 Interpretation of the Dual Simplex Algorithm
Problems
Notes and References
Chapter 4 Computational Considerations for the Simplex Algorithm
4.1 The Revised Simplex Algorithm
4.2 Computational Implications of the Revised Simplex Algorithm
4.3 The Max-Flow Problem and Its Solution by the Revised Method
4.4 Dantzig-Wolfe Decomposition
Problems
Notes and References
Chapter 5 The Primal-Dual Algorithm
5.1 Introduction
5.2 The Primal-Dual Algorithm
5.3 Comments on the Primal-Dual Algorithm
5.4 The Primal-Dual Method Applied to the Shortest-Path Problem
5.5 Comments on Methodology
5.6 The Primal-Dual Method Applied to Max-Flow
Problems
Notes and References
Chapter 6 Primal-Dual Algorithms for Max-Flow and Shortest Path: Ford-Fulkerson and Dijkstra
6.1 The Max-Flow, Min-Cut Theorem
6.2 The Ford and Fulkerson Labeling Algorithm
6.3 The Question of Finiteness of the Labeling Algorithm
6.4 Dijkstra's Algorithm
6.5 The Floyd-Warshall Algorithm
Problems
Notes and References
Chapter 7 Primal-Dual Algorithmsfor Min-Cost Flow
7.1 The Min-Cost Flow Problem
7.2 Combinatorializing the Capacities - Algorithm Cycle
7.3 Combinatorializing the Cost - Algorithm Buildup
7.4 An Explicit Primal-Dual Algorithm for the Hitchcock Problem -Algorithm Alphabeta
7.5 A Transformation of Min-Cost Flow to Hitchcock
7.6 Conclusion
Problems
Notes and References
Chapter 8 Algorithms and Complexity
8.1 Computability
8.2 Time Bounds
8.3 The Size of an Instance
8.4 Analysis of Algorithms
8.5 Polynomial-Time Algorithms
8.6 Simplex Is not a Polynomial-Time Algorithm
8.7 The Ellipsoid Algorithm
8.7.1 LP, LI, and LSI
8.7.2 Affine Transformations and Ellipsoids
8.7.3 The Algorithm
8.7.4 Arithmetic Precision
Problems
Notes and References
Chapter 9 Efficient Algorithms for the Max-Flow Problem
9.1 Graph Search
9.2 What Is Wrong with the Labeling Algorithm
9.3 Network Labeling and Digraph Search
9.4 An O(|V|3) Max-Flow Algorithm
9.5 The Case of Unit Capacities
Problems
Notes and References
Chapter 10 Algorithms for Matching
10.1 The Matching Problem
10.2 A Bipartite Matching Algorithm
10.3 Bipartite Matching and Network Flow
10.4 Nonbipartite Matching: Blossoms
10.5 Nonbipartite Matching: An Algorithm
Problems
Notes and References
Chapter 11 Weighted Matching
11.1 Introduction
11.2 The Hungarian Method for the Assignment Problem
11.3 The Nonbipartite Weighted Matching Problem
11.4 Conclusions
Problems
Notes and References
12.1 The Minimum Spanning Tree Problem
12.2 An O(|E|log|V|) Algorithm for the Minimum Spanning Tree Problem
12.3 The Greedy Algorithm
12.4 Matroids
12.5 The Intersection of Two Matroids
12.6 On Certain Extensions of the Matroid Intersection Problem
12.6.1 Weighted Matroid Intersection
12.6.2 Matroid Parity
12.6.3 The Intersection of Three Matroids,
Problems
Notes and References
Chapter 12 Spanning Trees and Matroids
13.1 Introduction
13.2 Total Unimodularity
13.3 Upper Bounds for Solutions of ILP's
Problems
Notes and References
Chapter 13 Integer Linear Programming
14.1 GomoryCuts
14.2 Lexicography
14.3 Finiteness of the Fractional Dual Algorithm
14.4 Other Cutting-Plane Algorithms
Problems
Notes and References
Chapter 14 A Cutting-Plane Algorithm for Integer Linear Programs
15.1 Introduction
15.2 An Optimization Problem Is Three Problems
15.3 The Classes P and NP
15.4 Polynomial-Time Reductions
15.5 Cook's Theorem
15.6 Some Other NP-Complete Problems: Clique and the TSP
15.7 More NP-Complete Problems: Matching, Covering, and Partitioning
Problems
Notes and References
Chapter 15 NP-Complete Problems
16.1 The Class co-NP
16.2 Pseudo-Polynomial Algorithms and "Strong" NP- Completeness
16.3 Special Cases and Generalizations of /VP-Complete Problems
16.3.1 NP-Completeness by Restriction
16.3.2 Easy Special Cases of NP-Complete Problems
16.3.3 Hard Special Cases of NP-Complete Problems
16.4 A Glossary of Related Concepts
16.4.1 Polynomial-Time Reductions
16.4.2 NP-Hard Problems
16.4.3 Nondeterministic Turing Machines
16.4.4 Polynomial-Space Complete Problems
16.5 Epilogue
Problems
Notes and References
Chapter 16 More About NP-Completeness
17.1 Heuristics for Node Cover: An Example
17.2 Approximation Algorithms for the Traveling Salesman Problem
17.3 Approximation Schemes
17.4 Negative Results
Problems
Notes and References
Chapter 17 Approximation Algorithms
18.1 Branch-and-Bound for Integer Linear Programming
18.2 Branch-and-Bound in a General Context
18.3 Dominance Relations
18.4 Branch-and-Bound Strategies
18.5 Application to a Flowshop Scheduling Problem
18.6 Dynamic Programming
Problems
Notes and References
Chapter 18 Branch-and-Bound and Dynamic Programming
Chapter 19 Local Search
19.1 Introduction
19.2 Problem 1:The TSP
19.3 Problem 2:Minimum-Cost Survivable Networks
19.4 Problem 3:Topology of Offshore Natural-GasPipeline Systems
19.5 Problem 4:Uniform Graph Partitioning
19.6 General Issues in Local Search
19.7 The Geometry of Local Search
19.8 An Example of a Large Minimal Exact Neighborhood
19.9 The Complexity of Exact Local Search for the TSP
Problems
Notes and References
Index

Systemvoraussetzungen

Als PDF speichern Als Link merken