Combinatorial Optimization: Algorithms and ComplexityPrentice Hall, 1982 - 496 Seiten Christos 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. |
Inhalt
THE SIMPLEX ALGORITHM | 26 |
DUALITY | 67 |
COMPUTATIONAL CONSIDERATIONS | 88 |
Urheberrecht | |
17 weitere Abschnitte werden nicht angezeigt.
Andere Ausgaben - Alle anzeigen
Häufige Begriffe und Wortgruppen
augmenting path auxiliary digraph b₁ basis bipartite matching blossom c₁ Chapter clique column combinatorial optimization complete components Consider constraints construct convex corresponding cost cycle defined digraph Dijkstra's algorithm dual e₁ edges example feasible solution Figure finite 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 matrix matroid max-flow problem maximum 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