Combinatorial Optimization: Algorithms and Complexity

Front Cover
Dover Publications, 1998 - Mathematics - 496 pages
1 Review
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.

From inside the book

What people are saying - Write a review

Review: Combinatorial Optimization: Algorithms and Complexity

User Review  - DJ - Goodreads

another gem from Dover Read full review

Review: Combinatorial Optimization: Algorithms and Complexity

User Review  - dead letter office - Goodreads

a $19 classic text on combinatorial optimization. thank you dover. Read full review

Contents

OPTIMIZATION PROBLEMS 1
3
THE SIMPLEX ALGORITHM
26
DUALITY
67
Copyright

11 other sections not shown

Common terms and phrases

About the author (1998)

Christos H. Papadimitriou is C. Lester Hogan Professor of Computer Science at the University of California, Berkeley and a member of the National Academy of Engineering and the American Academy of Arts and Sciences. He is the author of many books on computational theory.

Bibliographic information