Combinatorial optimization : algorithms and complexity / Christos H. Papadimitriou, Kenneth Steiglitz.
By: Papadimitriou, Christos H
.
Contributor(s): Steiglitz, Kenneth.
Material type: 
BookPublisher: Mineola, N.Y. : Dover Publications, 1998Description: xvi, 496 p. : ill. ; 22 cm. + pbk.ISBN: 0486402584 .Subject(s): Mathematical optimization | Combinatorial optimization | Computational complexityDDC classification: 519.3 | Item type | Current library | Call number | Copy number | Status | Barcode | |
|---|---|---|---|---|---|---|
| General lending | MTU Bishopstown Library Lending | 519.3 (Browse shelf(Opens below)) | 1 | Available | 00078153 |
Browsing MTU Bishopstown Library shelves, Shelving location: Lending Close shelf browser (Hides shelf browser)
Enhanced descriptions from Syndetics:
This clearly written, mathematically rigorous text includes a novel algorithmic exposition of the simplex method and also discusses the Soviet ellipsoid algorithm for linear programming; efficient algorithms for network flow, matching, spanning trees, and matroids; the theory of NP-complete problems; approximation algorithms, local search heuristics for NP-complete problems, more. All chapters are supplemented by thought-provoking problems. A useful work for graduate-level students with backgrounds in computer science, operations research, and electrical engineering. "Mathematicians wishing a self-contained introduction need look no further." -- American Mathematical Monthly.
Originally published: Englewood Cliffs, N.J. : Prentice Hall, c1982. With new pref.
Includes bibliographical references and index.
Optimization problems -- The simplex algorithm -- Duality -- Computational considerations for the simplex algorithm -- The primal-dual algorithm -- Primal-dual algorithms for max-flow and shortest path; ford-fulkerson and dijkstra -- Primal-dual algorithms for min-cost flow -- Algorithms and complexity -- Efficient algorithms for the max-flow problem -- Algorithms for matching -- Weighted matching -- Spanning trees and matroids -- Integer linear programming -- A cutting-plane algorithm for integer linear programs -- NP-complete problems -- More about NP-completeness -- Approximation algorithms -- Branch-and-bound and dynamic programming -- Local search.