Articoli correlati a Knapsack Problems

Knapsack Problems - Brossura

 
9783642073113: Knapsack Problems
Vedi tutte le copie di questo ISBN:
 
 
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.

Le informazioni nella sezione "Riassunto" possono far riferimento a edizioni diverse di questo titolo.

Recensione:

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." (Jürgen Köhler, 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. Šoric, Zentralblatt MATH, Vol. 1103 (5), 2007)

Contenuti:
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 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.

Le informazioni nella sezione "Su questo libro" possono far riferimento a edizioni diverse di questo titolo.

  • EditoreSpringer Nature
  • Data di pubblicazione2010
  • ISBN 10 3642073115
  • ISBN 13 9783642073113
  • RilegaturaCopertina flessibile
  • Numero di pagine546

Altre edizioni note dello stesso titolo

9783540402862: Knapsack Problems

Edizione in evidenza

ISBN 10:  ISBN 13:  9783540402862
Casa editrice: Springer Nature, 2003
Rilegato

  • 9783642534591: Knapsack Problems

    Springer, 2012
    Brossura

I migliori risultati di ricerca su AbeBooks

Foto dell'editore

Kellerer, Hans; Pferschy, Ulrich; Pisinger, David
Editore: Springer (2010)
ISBN 10: 3642073115 ISBN 13: 9783642073113
Nuovo Brossura Quantità: 1
Da:
GF Books, Inc.
(Hawthorne, CA, U.S.A.)
Valutazione libreria

Descrizione libro Condizione: New. Book is in NEW condition. Codice articolo 3642073115-2-1

Informazioni sul venditore | Contatta il venditore

Compra nuovo
EUR 229,39
Convertire valuta

Aggiungere al carrello

Spese di spedizione: GRATIS
In U.S.A.
Destinazione, tempi e costi
Foto dell'editore

Kellerer, Hans; Pferschy, Ulrich; Pisinger, David
Editore: Springer (2010)
ISBN 10: 3642073115 ISBN 13: 9783642073113
Nuovo Brossura Quantità: 1
Da:
Book Deals
(Tucson, AZ, U.S.A.)
Valutazione libreria

Descrizione libro Condizione: New. New! This book is in the same immaculate condition as when it was published. Codice articolo 353-3642073115-new

Informazioni sul venditore | Contatta il venditore

Compra nuovo
EUR 229,39
Convertire valuta

Aggiungere al carrello

Spese di spedizione: GRATIS
In U.S.A.
Destinazione, tempi e costi
Immagini fornite dal venditore

Kellerer, Hans", "Pferschy, Ulrich", "Pisinger, David"
Editore: Springer (2010)
ISBN 10: 3642073115 ISBN 13: 9783642073113
Nuovo Soft Cover Quantità: 10
Da:
booksXpress
(Bayonne, NJ, U.S.A.)
Valutazione libreria

Descrizione libro Soft Cover. Condizione: new. Codice articolo 9783642073113

Informazioni sul venditore | Contatta il venditore

Compra nuovo
EUR 229,43
Convertire valuta

Aggiungere al carrello

Spese di spedizione: GRATIS
In U.S.A.
Destinazione, tempi e costi
Foto dell'editore

Kellerer, Hans; Pferschy, Ulrich; Pisinger, David
Editore: Springer (2010)
ISBN 10: 3642073115 ISBN 13: 9783642073113
Nuovo Brossura Quantità: > 20
Da:
Lucky's Textbooks
(Dallas, TX, U.S.A.)
Valutazione libreria

Descrizione libro Condizione: New. Codice articolo ABLIING23Mar3113020216206

Informazioni sul venditore | Contatta il venditore

Compra nuovo
EUR 249,07
Convertire valuta

Aggiungere al carrello

Spese di spedizione: EUR 3,69
In U.S.A.
Destinazione, tempi e costi
Immagini fornite dal venditore

Hans Kellerer|Ulrich Pferschy|David Pisinger
ISBN 10: 3642073115 ISBN 13: 9783642073113
Nuovo Brossura Quantità: > 20
Print on Demand
Da:
moluna
(Greven, Germania)
Valutazione libreria

Descrizione libro Condizione: New. Dieser Artikel ist ein Print on Demand Artikel und wird nach Ihrer Bestellung fuer Sie gedruckt. This is the only book devoted entirely to Knapsack problems, which are most basic combinatorial optimization problemsThirteen years have passed since the seminal book on knapsack problems by Martello and Toth appeared. On this occasion a former c. Codice articolo 5046386

Informazioni sul venditore | Contatta il venditore

Compra nuovo
EUR 206,40
Convertire valuta

Aggiungere al carrello

Spese di spedizione: EUR 48,99
Da: Germania a: U.S.A.
Destinazione, tempi e costi
Foto dell'editore

Hans Kellerer
Editore: Springer (2010)
ISBN 10: 3642073115 ISBN 13: 9783642073113
Nuovo Brossura Quantità: > 20
Print on Demand
Da:
Ria Christie Collections
(Uxbridge, Regno Unito)
Valutazione libreria

Descrizione libro Condizione: New. PRINT ON DEMAND Book; New; Fast Shipping from the UK. No. book. Codice articolo ria9783642073113_lsuk

Informazioni sul venditore | Contatta il venditore

Compra nuovo
EUR 254,93
Convertire valuta

Aggiungere al carrello

Spese di spedizione: EUR 11,65
Da: Regno Unito a: U.S.A.
Destinazione, tempi e costi
Immagini fornite dal venditore

Hans Kellerer
ISBN 10: 3642073115 ISBN 13: 9783642073113
Nuovo Taschenbuch Quantità: 2
Print on Demand
Da:
BuchWeltWeit Ludwig Meier e.K.
(Bergisch Gladbach, Germania)
Valutazione libreria

Descrizione libro Taschenbuch. Condizione: Neu. This item is printed on demand - it takes 3-4 days longer - Neuware -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. 568 pp. Englisch. Codice articolo 9783642073113

Informazioni sul venditore | Contatta il venditore

Compra nuovo
EUR 246,09
Convertire valuta

Aggiungere al carrello

Spese di spedizione: EUR 23,00
Da: Germania a: U.S.A.
Destinazione, tempi e costi
Immagini fornite dal venditore

Hans Kellerer
ISBN 10: 3642073115 ISBN 13: 9783642073113
Nuovo Taschenbuch Quantità: 1
Da:
AHA-BUCH GmbH
(Einbeck, Germania)
Valutazione libreria

Descrizione libro Taschenbuch. Condizione: Neu. Druck auf Anfrage Neuware - Printed after ordering - 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. Codice articolo 9783642073113

Informazioni sul venditore | Contatta il venditore

Compra nuovo
EUR 249,04
Convertire valuta

Aggiungere al carrello

Spese di spedizione: EUR 32,99
Da: Germania a: U.S.A.
Destinazione, tempi e costi
Foto dell'editore

Kellerer, Hans
Editore: Springer (2010)
ISBN 10: 3642073115 ISBN 13: 9783642073113
Nuovo Brossura Quantità: 1
Da:
Front Cover Books
(Denver, CO, U.S.A.)
Valutazione libreria

Descrizione libro Condizione: new. Codice articolo FrontCover3642073115

Informazioni sul venditore | Contatta il venditore

Compra nuovo
EUR 298,48
Convertire valuta

Aggiungere al carrello

Spese di spedizione: EUR 3,98
In U.S.A.
Destinazione, tempi e costi
Foto dell'editore

Kellerer, Hans
Editore: Springer (2010)
ISBN 10: 3642073115 ISBN 13: 9783642073113
Nuovo Paperback Quantità: 1
Da:
Wizard Books
(Long Beach, CA, U.S.A.)
Valutazione libreria

Descrizione libro Paperback. Condizione: new. New. Codice articolo Wizard3642073115

Informazioni sul venditore | Contatta il venditore

Compra nuovo
EUR 299,23
Convertire valuta

Aggiungere al carrello

Spese di spedizione: EUR 3,24
In U.S.A.
Destinazione, tempi e costi

Vedi altre copie di questo libro

Vedi tutti i risultati per questo libro