Now Australia's Biggest Toy Store

Shop over 1.5 Million Toys in our Huge New Range

Knapsack Problems


Product Description
Product Details

Table of Contents

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.


From the reviews:

"The book explores the knapsack problem and its variants in 15 chapters ... . On the whole, the authors present a rich amount of material, much of which belongs to the most recent advancement in the subject ... . This self-contained monograph is a valuable addition to the existing literature on knapsack problems. It will certainly make an excellent reference for researchers in combinatorial optimization. ... In this regard, the libraries in this field-should have a copy of this book on their shelves." (J Xue, Journal of the Operational Research Society, Vol. 56 (11), 2005)

"This book provides a comprehensive overview of the methods for solving KP, its variants and generalizations. ... By presenting a range of algorithmic techniques, this book is also a suitable tool for studying modern algorithms. ... With its more than 500 references and its author and subject indexes, this book will be a valuable tool for many researchers in combinatorial optimization." (Peter Butkovic, Mathematical Reviews, 2006 d)

"This book presents a large number of new results for knapsack problems, especially related to exact and approximate (heuristic) algorithms. Moreover, many modifications and extensions of the knapsack problem are treated. To do this, the authors found and consequently used a close connection between manifold contents and a clear, stimulating presentation. ... With an introduction into NP-completeness of knapsack problems a monograph ends, which spans the range from a comprehensive introduction to the most recent and advanced results very nicely." (Jurgen Koehler, OR Spectrum, Issue 27, 2005)

"The book starts with a basic introduction to the knapsack problem ... . It proceeds with a discussion about the basic techniques available for the solution to this problem, which makes it useful reading for undergraduate students of computer science, mathematics and economics. ... In conclusion, it could be said that the book is a valuable source for students, but also for researchers interested in this problem." (K. Soric, Zentralblatt MATH, Vol. 1103 (5), 2007)

Ask a Question About this Product More...
Write your question below:
Look for similar items by category
People also searched for
How Fishpond Works
Fishpond works with suppliers all over the world to bring you a huge selection of products, really great prices, and delivery included on over 25 million products that we sell. We do our best every day to make Fishpond an awesome place for customers to shop and get what they want — all at the best prices online.
Webmasters, Bloggers & Website Owners
You can earn a 5% commission by selling Knapsack Problems on your website. It's easy to get started - we will give you example code. After you're set-up, your website can earn you money while you work, play or even sleep! You should start right now!
Authors / Publishers
Are you the Author or Publisher of a book? Or the manufacturer of one of the millions of products that we sell. You can improve sales and grow your revenue by submitting additional information on this title. The better the information we have about a product, the more we will sell!
Item ships from and is sold by Fishpond Retail Limited.
Back to top