Author | Kellerer, Hans. author |
---|---|
Title | Knapsack Problems [electronic resource] / by Hans Kellerer, Ulrich Pferschy, David Pisinger |
Imprint | Berlin, Heidelberg : Springer Berlin Heidelberg : Imprint: Springer, 2004 |
Connect to | http://dx.doi.org/10.1007/978-3-540-24777-7 |
Descript | XX, 548 p. online resource |
1 Introduction -- 1.1 Introducing the Knapsack Problem -- 1.2 Variants and Extensions of the Knapsack Prยฉblem -- 1.3 Single-Capacity Versus All-Capacities Problem -- 1.4 Assumptions on the Input Data -- 1.5 Performance of Algorithms -- 2. Basic Algorithmic Concepts -- 2.1 The Greedy Algorithm -- 2.2 Linear Programming Relaxation -- 2.3 Dynamic Programming -- 2.4 Branch-and-Bound -- 2.5 Approximation Algorithms -- 2.6 Approximation Schemes -- 3. Advanced Algorithmic Concepts -- 3.1 Finding the Split Item in Linear Time -- 3.2 Variable Reduction -- 3.3 Storage Reduction in Dynamic Programming -- 3.4 Dynamic Programming with Lists -- 3.5 Combining Dynamic Programming and Upper Bounds -- 3.6 Balancing -- 3.7 Word RAM Algorithms -- 3.8 Relaxations -- 3.9 Lagrangian Decomposition -- 3.10 The Knapsack Polytope -- 4. The Subset Sum Problem -- 4.1 Dynamic Programming -- 4.2 Branch-and-Bound -- 4.3 Core Algorithms -- 4.4 Computational Results: Exact Algorithms -- 4.5 Polynomial Time Approximation Schemes for Subset Sum -- 4.6 A Fully Polynomial Time Approximation Scheme for Subset Sum -- 4.7 Computational Results: FPTAS -- 5. Exact Solution of the Knapsack Problem -- 5.1 Branch-and-Bound -- 5.2 Primal Dynamic Programming Algorithms -- 5.3 Primal-Dual Dynamic Programming Algorithms -- 5.4 The Core Concept -- 5.5 Computational Experiments -- 6. Approximation Algorithms for the Knapsack Problem -- 6.1 Polynomial Time Approximation Schemes -- 6.2 Fully Polynomial Time Approximation Schemes -- 7. The Bounded Knapsack Problem -- 7.1 Introduction -- 7.2 Dynamic Programming -- 7.3 Branch-and-Bound -- 7.4 Approximation Algorithms -- 8. The Unbounded Knapsack Problem -- 8.1 Introduction -- 8.2 Periodicity and Dominance -- 8.3 Dynamic Programming -- 8.4 Branch-and-Bound -- 8.5 Approximation Algorithms -- 9 Multidimensional Knapsack Problems -- 9.1 Introduction -- 9.2 Relaxations and Reductions -- 9.3 Exact Algorithms -- 9.4 Approximation -- 9.5 Heuristic Algorithms -- 9.6 The Two-Dimensional Knapsack Problem -- 9.7 The Cardinality Constrained Knapsack Problem -- 9.8 The Multidimensional Multiple-Choice Knapsack Problem -- 10. Multiple Knapsack Problems -- 10.1 Introduction -- 10.2 Upper Bounds -- 10.3 Branch-and-Bound -- 10.4 Approximation Algorithms -- 10.5 Polynomial Time Approximation Schemes -- 10.6 Variants of the Multiple Knapsack Problem -- 11. The Multiple-Choice Knapsack Problem -- 11.1 Introduction -- 11.2 Dominance and Upper Bounds -- 11.3 Class Reduction -- 11.4 Branch-and-Bound -- 11.5 Dynamic Programming -- 11.6 Reduction of States -- 11.7 Hybrid Algorithms and Expanding Core Algorithms -- 11.8 Computational Experiments -- 11.9 Heuristics and Approximation Algorithms -- 11.10 Variants of the Multiple-Choice Knapsack Problem -- 12. The Quadratic Knapsack Problem -- 12.1 Introduction -- 12.2 Upper Bounds -- 12.3 Variable Reduction -- 12.4 Branch-and-Bound -- 12.5 The Algorithm by Caprara, Pisinger and Toth -- 12.6 Heuristics -- 12.7 Approximation Algorithms -- 12.8 Computational Experiments Exact Algorithms -- 12.9 Computational Experiments Upper Bounds -- 13. Other Knapsack Problems -- 13.1 Multiobjective Knapsack Problems -- 13.2 The Precedence Constraint Knapsack Problem (PCKP) -- 13.3 Further Variants -- 14. Stochastic Aspects of Knapsack Problems -- 14.1 The Probabilistic Model -- 14.2 Structural Results -- 14.3 Algorithms with Expected Performance Guarantee -- 14.4 Expected Performance of Greedy-Type Algorithms -- 14.5 Algorithms with Expected Running Time -- 14.6 Results for the Subset Sum Problem -- 14.7 Results for the Multidimensional Knapsack Problem -- 14.8 The On-Line Knapsack Problem -- 15. Some Selected Applications -- 15.1 Two-Dimensional Two-Stage Cutting Problems -- 15.2 Column Generation in Cutting Stock Problems -- 15.3 Separation of Cover Inequalities -- 15.4 Financial Decision Problems -- 15.5 Asset-Backed Securitization -- 15.6 Knapsack Cryptosystems -- 15.7 Combinatorial Auctions -- A. Introduction to NP-Completeness of Knapsack Problems -- A.1 Definitions -- A.2 NP-Completeness of the Subset Sum Problem -- A.3 NP-Completeness of the Knapsack Problem -- A.4 NP-Completeness of Other Knapsack Problems -- References -- Author Index