Combinatorial Optimization: Theory and AlgorithmsSpringer Science & Business Media, 27.01.2006 - 597 Seiten This well-written textbook on combinatorial optimization puts special emphasis on theoretical results and algorithms with provably good performance, in contrast to heuristics. The book contains complete (but concise) proofs, as well as many deep results, some of which have not appeared in any previous books. |
Inhalt
Introduction | 1 |
Exercises | 9 |
Maximum Matchings | 10 |
Network Design Problems | 20 |
Exercises | 42 |
3 | 49 |
Linear Programming Algorithms | 65 |
Spanning Trees and Arborescences | 118 |
bMatchings and TJoins | 271 |
Exercises | 282 |
References | 288 |
Generalizations of Matroids | 323 |
NPCompleteness | 343 |
The Knapsack Problem | 419 |
BinPacking | 427 |
Exercises | 438 |
Exercises | 132 |
Shortest Paths | 140 |
Exercises | 153 |
References | 155 |
8 | 160 |
Minimum Cost Flows | 190 |
3 | 243 |
Weighted Matching | 245 |
Multicommodity Flows and EdgeDisjoint Paths | 442 |
Exercises | 495 |
Facility Location | 536 |
| 570 | |
| 573 | |
| 585 | |
Andere Ausgaben - Alle anzeigen
Combinatorial Optimization: Theory and Algorithms Bernhard Korte,Jens Vygen Keine Leseprobe verfügbar - 2009 |
Häufige Begriffe und Wortgruppen
approximation algorithm arborescence augmenting path b-flow bipartite graph blossom cardinality circuit combinatorial optimization Computing connected components consider contains Corollary define Definition deleting digraph digraph G dual ear-decomposition edge edge-disjoint Edmonds Eulerian Exercise exists feasible finite given graph G greedoid Hamiltonian implies incidence vectors induction inequality integral vector iteration Journal Lemma Let G linear program Lovász matching in G Mathematics matrix matroid max{cx maximal maximum flow MAXIMUM FLOW PROBLEM minimal MINIMUM COST FLOW MINIMUM SPANNING TREE minimum weight nonnegative NP-complete NP-hard optimization problems optimum solution oracle outer PATHS PROBLEM perfect matching planar planar graph polyhedron polynomial polynomial-time algorithm polytope Proof Proposition prove reachable running s-t-cut s-t-flow s-t-path satisfies Schrijver Section shortest path SHORTEST PATH PROBLEM solve Steiner tree strongly connected components subgraph submodular function subset T-cut T-join Tarjan Theorem undirected graph vertices