## Combinatorial Optimization: Algorithms and ComplexityThis 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

#### Review: Combinatorial Optimization: Algorithms and Complexity

User Review - DJ - Goodreadsanother gem from Dover Read full review

#### Review: Combinatorial Optimization: Algorithms and Complexity

User Review - dead letter office - Goodreadsa $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

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