Descript |
1 online resource (942 p.) |
Note |
Description based upon print version of record. |
Contents |
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 |
Note |
Unlimited number of concurrent users. UkHlHU |
ISBN |
9780486320137 |
|