Combinatorial Optimization: Algorithms and ComplexityChristos H. Papadimitriou and Kenneth Steiglitz have combined the theory of computational complexity developed by computer scientists, and the foundations of mathematical programming developed by the operations research community. This text will be useful to students with a wide range of backgrounds, including computer science, operations research, and electrical engineering. |
Contents
THE SIMPLEX ALGORITHM | 26 |
DUALITY | 67 |
COMPUTATIONAL CONSIDERATIONS | 88 |
Copyright | |
17 other sections not shown
Common terms and phrases
augmenting path auxiliary digraph b₁ basis bipartite matching blossom c₁ Chapter clique column combinatorial optimization Consider constraints construct convex corresponding cost cycle defined digraph Dijkstra's algorithm dual e₁ edges ellipsoid algorithm example feasible solution Figure finite Floyd-Warshall algorithm formulation graph G greedy algorithm Hamilton circuit hence inequality input integer integer linear programming iteration labeling algorithm Lemma linear programming local search lower bound matching problem matrix matroid max-flow problem maximum method min-cost flow minimum spanning tree neighborhood NP-complete problems optimal solution optimum partition pivot polynomial polynomial-time algorithm polytope primal primal-dual algorithm Proof result S₁ satisfy sequence shortest path shortest-path problem shown in Fig simplex algorithm solve spanning tree stage subset Suppose tableau Theorem tour Traveling Salesman Problem u₁ v₁ variables vector vertex vertices x₁ zero