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.
OPTIMIZATION PROBLEMS 1
THE SIMPLEX ALGORITHM
11 other sections not shown
Other editions - View all
applied AT'-complete augmenting path auxiliary digraph basis bipartite matching blossom branch-and-bound capacities Chapter clique column combinatorial optimization combinatorial optimization problem complete components Consider constraints construct convex corresponding cost cycle defined digraph Dijkstra's algorithm edges equations feasible solution Figure finite Floyd-Warshall algorithm formulation function graph G greedy algorithm Hamilton circuit hence inequality input integer integer linear programming iteration KNAPSACK labeling algorithm Lemma linear programming lower bound matching problem matroid max-flow problem maximum matching method min-cost flow minimum spanning tree NP-complete optimal solution optimum partition pivot polynomial polynomial-time algorithm polytope primal primal-dual algorithm Proof result satisfy schedule 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 W-complete zero