Combinatorial Optimization: Algorithms and ComplexityDover Publications, 1998 - 496 Seiten 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. |
Inhalt
PREFACE TO THE DOVER EDITION | 7 |
OPTIMIZATION PROBLEMS | 13 |
THE SIMPLEX ALGORITHM | 26 |
Urheberrecht | |
12 weitere Abschnitte werden nicht angezeigt.
Andere Ausgaben - Alle anzeigen
Combinatorial Optimization: Algorithms and Complexity Christos H. Papadimitriou,Kenneth Steiglitz Eingeschränkte Leseprobe - 2013 |
Combinatorial Optimization: Algorithms and Complexity Christos H. Papadimitriou,Kenneth Steiglitz Eingeschränkte Leseprobe - 1998 |
Combinatorial Optimization: Algorithms and Complexity Christos H. Papadimitriou,Kenneth Steiglitz Keine Leseprobe verfügbar - 1998 |
Häufige Begriffe und Wortgruppen
applied augmenting path auxiliary digraph b₁ basis bipartite matching c₁ Chapter clique column combinatorial optimization complete Consider constraints construct convex corresponding cost cycle defined digraph Dijkstra's algorithm dual e₁ edges equations 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 lower bound matching problem matrix matroid max-flow problem maximum maximum matching 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 Show shown in Fig simplex algorithm solve spanning tree stage subset Suppose tableau Theorem theory tour Traveling Salesman Problem u₁ v₁ variables vector vertex vertices zero