Knapsack problems
著者
書誌事項
Knapsack problems
Springer, c2004
- : pbk
大学図書館所蔵 全17件
  青森
  岩手
  宮城
  秋田
  山形
  福島
  茨城
  栃木
  群馬
  埼玉
  千葉
  東京
  神奈川
  新潟
  富山
  石川
  福井
  山梨
  長野
  岐阜
  静岡
  愛知
  三重
  滋賀
  京都
  大阪
  兵庫
  奈良
  和歌山
  鳥取
  島根
  岡山
  広島
  山口
  徳島
  香川
  愛媛
  高知
  福岡
  佐賀
  長崎
  熊本
  大分
  宮崎
  鹿児島
  沖縄
  韓国
  中国
  タイ
  イギリス
  ドイツ
  スイス
  フランス
  ベルギー
  オランダ
  スウェーデン
  ノルウェー
  アメリカ
注記
"Softcover reprint of the hardcover 1st edition 2004"--T.p. verso of pbk
Includes bibliographical references and indexes
内容説明・目次
内容説明
Thirteen years have passed since the seminal book on knapsack problems by Martello and Toth appeared. On this occasion a former colleague exclaimed back in 1990: "How can you write 250 pages on the knapsack problem?" Indeed, the definition of the knapsack problem is easily understood even by a non-expert who will not suspect the presence of challenging research topics in this area at the first glance. However, in the last decade a large number of research publications contributed new results for the knapsack problem in all areas of interest such as exact algorithms, heuristics and approximation schemes. Moreover, the extension of the knapsack problem to higher dimensions both in the number of constraints and in the num ber of knapsacks, as well as the modification of the problem structure concerning the available item set and the objective function, leads to a number of interesting variations of practical relevance which were the subject of intensive research during the last few years. Hence, two years ago the idea arose to produce a new monograph covering not only the most recent developments of the standard knapsack problem, but also giving a comprehensive treatment of the whole knapsack family including the siblings such as the subset sum problem and the bounded and unbounded knapsack problem, and also more distant relatives such as multidimensional, multiple, multiple-choice and quadratic knapsack problems in dedicated chapters.
目次
1 Introduction.- 1.1 Introducing the Knapsack Problem.- 1.2 Variants and Extensions of the Knapsack Pr (c)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 (c)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 Problems.- 10.1 Introduction.- 10.2 Upper Bounds.- 10.2.1 Variable Reduction and Tightening of Constraints.- 10.3 Branch-and-Bound.- 10.3.1 The MTM Algorithm.- 10.3.2 The Mulknap Algorithm.- 10.3.3 Computational Results.- 10.4 Approximation Algorithms.- 10.4.1 Greedy-Type Algorithms and Further Approximation Algorithms.- 10.4.2 Approximability Results for (B-MSSP).- 10.5 Polynomial Time Approximation Schemes.- 10.5.1 A PTAS for the Multiple Subset Problem.- 10.5.2 A PTAS for the Multiple Knapsack Problem.- 10.6 Variants of the Multiple Knapsack Problem.- 10.6.1 The Multiple Knapsack Problem with Assignment Restrictions.- 10.6.2 The Class-Constrained Multiple Knapsack Problem.- 11. The Multiple-Choice Knapsack Problem.- 11.1 Introduction.- 11.2 Dominance and Upper Bounds.- 11.2.1 Linear Time Algorithms for the LP-Relaxed Problem.- 11.2.2 Bounds from Lagrangian Relaxation.- 11.2.3 Other 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.- 11.10.1 Multiple-Choice Subset Sum Problem.- 11.10.2 Generalized Multiple-Choice Knapsack Problem.- 11.10.3 The Knapsack Sharing Problem.- 12. The Quadratic Knapsack Problem.- 12.1 Introduction.- 12.2 Upper Bounds.- 12.2.1 Continuous Relaxation.- 12.2.2 Bounds from Lagrangian Relaxation of the Capacity Constraint.- 12.2.3 Bounds from Upper Planes.- 12.2.4 Bounds from Linearisation.- 12.2.5 Bounds from Reformulation.- 12.2.6 Bounds from Lagrangian Decomposition.- 12.2.7 Bounds from Semidefinite Relaxation.- 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.1.1 Introduction.- 13.1.2 Exact Algorithms for (MOKP).- 13.1.3 Approximation of the Multiobjective Knapsack Problem.- 13.1.4 An FPTAS for the Multiobjective Knapsack Problem.- 13.1.5 A PTAS for (MOd-KP).- 13.1.6 Metaheuristics.- 13.2 The Precedence Constraint Knapsack Problem (PCKP).- 13.2.1 Dynamic Programming Algorithms for Trees.- 13.2.2 Other Results for (PCKP).- 13.3 Further Variants.- 13.3.1 Nonlinear Knapsack Problems.- 13.3.2 The Max-Min Knapsack Problem.- 13.3.3 The Minimization Knapsack Problem.- 13.3.4 The Equality Knapsack Problem.- 13.3.5 The Strongly Correlated Knapsack Problem.- 13.3.6 The Change-Making Problem.- 13.3.7 The Collapsing Knapsack Problem.- 13.3.8 The Parametric Knapsack Problem.- 13.3.9 The Fractional Knapsack Problem.- 13.3.10 The Set-Union Knapsack Problem.- 13.3.11 The Multiperiod Knapsack Problem.- 14. Stochastic Aspects of Knapsack Problems.- 14.1 The Probabilistic Model.- 14.2 Structural Results.- 14.3 Algorithms with Expected Performance Guarantee.- 14.3.1 Related Models and Algorithms.- 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.- 14.8.1 Time Dependent On-Line Knapsack Problems.- 15. Some Selected Applications.- 15.1 Two-Dimensional Two-Stage Cutting Problems.- 15.1.1 Cutting a Given Demand from a Minimal Number of Sheets.- 15.1.2 Optimal Utilization of a Single Sheet.- 15.2 Column Generation in Cutting Stock Problems.- 15.3 Separation of Cover Inequalities.- 15.4 Financial Decision Problems.- 15.4.1 Capital Budgeting.- 15.4.2 Portfolio Selection.- 15.4.3 Interbank Clearing Systems.- 15.5 Asset-Backed Securitization.- 15.5.1 Introducing Securitization and Amortization Variants.- 15.5.2 Formal Problem Definition.- 15.5.3 Approximation Algorithms.- 15.6 Knapsack Cryptosystems.- 15.6.1 The Merkle-Hellman Cryptosystem.- 15.6.2 Breaking the Merkte-Hellman Cryptosystem.- 15.6.3 Further Results on Knapsack Cryptosystems.- 15.7 Combinatorial Auctions.- 15.7.1 Multi-Unit Combinatorial Auctions and Multi-Dimensional Knapsacks.- 15.7.2 A Multi-Unit Combinatorial Auction Problem with Decreasing Costs per Unit.- A. Introduction to NP-Completeness of Knapsack Problems.- A.1 Definitions.- A.2 NP-Completeness of the Subset Sum Problem.- A.2.1 Merging of Constraints.- A.2.2 NP-Completeness.- A.3 NP-Completeness of the Knapsack Problem.- A.4 NP-Completeness of Other Knapsack Problems.- References.- Author Index.
「Nielsen BookData」 より