Combinatorial Optimization: Algorithms and Complexity
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.
What people are saying - Write a review
We haven't found any reviews in the usual places.
Other editions - View all
applied arcs augmenting path auxiliary digraph basis bipartite matching blossom certiﬁcate Chapter clique column combinatorial optimization complete components Consider constraints construct convex corresponding cost cycle deﬁned deﬁnition digraph edges ellipsoid algorithm example feasible solution Figure ﬁnal ﬁnd ﬁnding ﬁnite ﬁrst ﬁxed ﬂow Floyd-Warshall algorithm formulation graph G greedy algorithm Hamilton circuit hence inequality input integer integer linear programming iteration KNAPSACK labeling algorithm Lemma linear programming local search lower bound matching problem matroid max-ﬂow problem maximum matching method min-cost ﬂow minimum spanning tree neighborhood NP-complete problems optimal solution optimum partition pivot polynomial polynomial-time algorithm polytope primal primal-dual algorithm Proof result satisﬁable sequence shortest path shortest-path problem Show shown in Fig simplex algorithm solve spanning tree stage subset Suppose tableau Theorem theory tour transformation Traveling Salesman Problem variables vector vertex vertices zero