Synopsis
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.1.1 Word RAM Algorithm.- 4.1.2 Primal-Dual Dynamic Programming Algorithms.- 4.1.3 Primal-Dual Word-RAM Algorithm.- 4.1.4 Horowitz and Sahni Decomposition.- 4.1.5 Balancing.- 4.1.6 Bellman Recursion in Decision Form.- 4.2 Branch-and-Bound.- 4.2.1 Upper Bounds.- 4.2.2 Hybrid Algorithms.- 4.3 Core Algorithms.- 4.3.1 Fixed Size Core.- 4.3.2 Expanding Core.- 4.3.3 Fixed Size Core and Decomposition.- 4.4 Computational Results: Exact Algorithms.- 4.4.1 Solution of All-Capacities Problems.- 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.1.1 Upper Bounds f©r (KP).- 5.1.2 Lower Bounds for (KP).- 5.1.3 Variable Reduction.- 5.1.4 Branch-and-Bound Implementations.- 5.2 Primal Dynamic Programming Algorithms.- 5.2.1 Word RAM Algorithm.- 5.2.2 Horowitz and Sahni Decomposition.- 5.3 Primal-Dual Dynamic Programming Algorithms.- 5.3.1 Balanced Dynamic Programming.- 5.4 The Core Concept.- 5.4.1 Finding a Core.- 5.4.2 Core Algorithms.- 5.4.3 Combining Dynamic Programming with Tight Bounds.- 5.5 Computational Experiments.- 5.5.1 Difficult Instances.- 5.5.2 Difficult Instances with Large Coefficients.- 5.5.3 Difficult Instances With Small Coefficients.- 6. Approximation Algorithms for the Knapsack Problem.- 6.1 Polynomial Time Approximation Schemes.- 6.1.1 Improving the PTAS for (KP).- 6.2 Fully Polynomial Time Approximation Schemes.- 6.2.1 Scaling and Reduction of the Item Set.- 6.2.2 An Auxiliary Vector Merging Problem.- 6.2.3 Solving the Reduced Problem.- 6.2.4 Putting the Pieces Together.- 7. The Bounded Knapsack Problem.- 7.1 Introduction.- 7.1.1 Transformation of (BKP) into (KP).- 7.2 Dynamic Programming.- 7.2.1 A Minimal Algorithm for (BKP).- 7.2.2 Improved Dynamic Programming: Reaching (KP) Complexity for (BKP).- 7.2.3 Word RAM Algorithm.- 7.2.4 Balancing.- 7.3 Branch-and-Bound.- 7.3.1 Upper Bounds.- 7.3.2 Branch-and Bound Algorithms.- 7.3.3 Computational Experiments.- 7.4 Approximation Algorithms.- 8. The Unbounded Knapsack Problem.- 8.1 Introduction.- 8.2 Periodicity and Dominance.- 8.2.1 Periodicity.- 8.2.2 Dominance.- 8.3 Dynamic Programming.- 8.3.1 Some Basic Algorithms.- 8.3.2 An Advanced Algorithm.- 8.3.3 Word RAM Algorithm.- 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.3.1 Branch-and-Bound Algorithms.- 9.3.2 Dynamic Programming.- 9.4 Approximation.- 9.4.1 Negative Approximation Results.- 9.4.2 Polynomial Time Approximation Schemes.- 9.5 Heuristic Algorithms.- 9.5.1 Greedy-Type Heuristics.- 9.5.2 Relaxation-Based Heuristics.- 9.5.3 Advanced Heuristics.- 9.5.4 Approximate Dynamic Programming.- 9.5.5 Metaheuristics.- 9.6 The Two-Dimensional Knapsack Problem.- 9.7 The Cardinality Constrained Knapsack Problem.- 9.7.1 Related Problems.- 9.7.2 Branch-and-Bound.- 9.7.3 Dynamic Programming.- 9.7.4 Approximation Algorithms.- 9.8 The Multidimensional Multiple-Choice Knapsack Problem.- 10. Multiple Knapsack P
Les informations fournies dans la section « Synopsis » peuvent faire référence à une autre édition de ce titre.
