Combinatorial Optimization: Algorithms and ComplexityCourier Corporation, 26.04.2013 - 528 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. |
Andere Ausgaben - Alle anzeigen
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 arcs augmenting path auxiliary digraph basis bipartite matching blossom certificate Chapter clique column combinatorial optimization complete components Consider constraints construct convex corresponding cost cycle defined definition digraph edges ellipsoid algorithm example feasible solution Figure final find finding finite first fixed flow Floyd-Warshall algorithm formulation graph G greedy algorithm Hamilton circuit hence inequality input integer integer linear programming iteration KNAPSACK labeling algorithm Lemma linear programming local search lower bound matching problem matroid max-flow problem 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 satisfiable 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 zero