Knapsack Problems
Hans Kellerer
Language: English
Pages: 548
ISBN: 3540402861
Format: PDF / Kindle (mobi) / ePub
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.
Data Mining in Agriculture (Springer Optimization and Its Applications)
An Introduction to Parallel Programming
Probabilistics Search for Tracking Targets: Theory and Modern Applications
Machine Learning: The Art and Science of Algorithms that Make Sense of Data
Haptic Human-Computer Interaction
Reader of the first three chapters willing to go into more depth, can use this book to study advanced algorithms for the knapsack problem and its relatives. On the other hand, we hope scientific researchers or expert practitioners will find the book a valuable source of reference for a quick update on the state of the art and on the most efficient algorithms currently available. In particular, a collection of computational experiments, many of them published for the first time in this book,.
Nand d = 1, ... , c. It is easy to see how X· can be reconstructed by going through the pointers. If An(c) = 1 then item n is added to X· and we proceed with checking An-l (c - w n). If An(c) = 0 then item n is not part of the optimal solution set and we proceed with An-l (c). The resulting version of DP-1 computes both z· andX· in O(nc) time and space. Looking at the values of Aj(d) it can be observed that it is not really necessary to store this table explicitly. Note that every entry of Aj(d),.
MinS(CkKP,Il) /L~O (5.22) The profits and weights are positive for any value of Il ~ O. hence the surrogate variant is slightly easier to solve. As in the Lagrangian relaxation case described above. we notice that the only interesting values of Il are those where two items i, j interchange the role of being the split item when solving the LP-relaxation. This may occur when items i and j have the same efficiency. i.e. when wrL/L = w;i/L' so there are again O(n 2 ) values of Il to be.
J[_I. A detailed formulation of the resulting algorithm CKPP following mostly the presentation in [65] (but with a more precise application of Greedy-Split) is given in 6.1 Polynomial Time Approximation Schemes 163 Algorithm CKPP: e:=min{f~1-2,n} renumber the items such that PI ~ P2 ~ ... ~ Pn generate all subsets L with cardinality less than for all subsets LeN with ILl ~ 1 do if EjEL Wj ~ ethen update the currently best solution e- e e generate all subsets L with cardinality denoted by.
This tree model will be used again in the proof of Theorem 6.2.10. The statement of the Lemma will be shown by backwards induction moving "upwards" in the tree, i.e. starting with its leafs and applying induction to the inner nodes. The leafs of the tree are executions of Recursion with no further recursive calls. Hence, the two corresponding conditions yield + z!{ = ql + q2 = ij and the statement of the Lemma follows from the claim concerning Backtracking. zf If the node under consideration.