## 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

We haven't found any reviews in the usual places.

### Contents

OPTIMIZATION PROBLEMS 1 | 3 |

THE SIMPLEX ALGORITHM | 26 |

DUALITY | 67 |

Copyright | |

11 other sections not shown

### Other editions - View all

### 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