Start Over Please hold this item Export MARC Display Return To Browse
 
     
Record: Previous Record Next Record
Author Papadimitriou, Christos H.
Title Combinatorial optimization : algorithms and complexity.
Publication Info New York : Dover Publications, 2013.


Click on the following to:
Go to ebook
Persistent link to this item
Click link and copy URL from browser navigation toolbar

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
 Click on the terms below to find similar items in the catalogue
Author Papadimitriou, Christos H.
Series Dover books on computer science
Dover books on computer science
Subject Combinatorial optimization.
Computational complexity.
Mathematical optimization.
Alt author Steiglitz, Kenneth.
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
Author Papadimitriou, Christos H.
Series Dover books on computer science
Dover books on computer science
Subject Combinatorial optimization.
Computational complexity.
Mathematical optimization.
Alt author Steiglitz, Kenneth.

Subject Combinatorial optimization.
Computational complexity.
Mathematical optimization.
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
Alt author Steiglitz, Kenneth.
ISBN 9780486320137
Persistent link to this item
Click link and copy URL from browser navigation toolbar

Links and services for this item:

Persistent link to this item
Click link and copy URL from browser navigation toolbar