Combinatorial Optimization: Algorithms and Complexity.

TLDR

This text offers a mathematically rigorous exposition of linear‑programming algorithms—including the simplex and ellipsoid methods—alongside efficient algorithms for network flow, matching, spanning trees, and matroids, and it discusses NP‑complete problems, approximation algorithms, and local‑search heuristics, all supplemented by thought‑provoking problems for graduate students in computer science, operations research, and electrical engineering. It provides a self‑contained introduction for mathematicians. 1982 edition.

Abstract

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 NPcomplete problems, more. All chapters are supplemented by thoughtprovoking 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. 1982 ed.