Knapsack Problems: Algorithms and Computer Implementations

By Silvano Martello, Paolo Toth. 1990

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

FSD50K: An Open Dataset of Human-Labeled Sound Events (2020, methodology): “rtant classes. 2) Split Method: Given the many constraints, off-the-shelf methods such as random sampling, iterative stratiﬁcation [69] or combinatorial optimization algorithms like knapsack problems [5,70] are not well suited. Therefore, we implement an ad hoc approach consisting of iteratively all”
Bin packing and cutting stock problems: Mathematical models and exact algorithms (2016, methodology): “1): – MTP, Fortran code by Martello and Toth [107]; – BISON, Pascal code by Scholl et al.”
Chirping up the Right Tree: Incorporating Biological Taxonomies into Deep Bioacoustic Classifiers (2020, methodology): “Because the class distributions differ between the two datasets, we create a training-validation split by formulating the allocation of examples to the validation set as a knapsack problem [30] treating individual data sources containing a particular fine-level class as items, with weights correspon”
Quality driven web services composition (2003, background): “This problem is a special case of the knapsack problem and hence it is NP-hard [19].”
The Algorithm Design Manual (2020, background): “An electronic copy of [MT90a] has also been generously made available.”
Combinatorial auctions (2007, unknown): “Model (M2) is an 0-1 multidimensional knapsack problem for which exact and heuristic solution methods have been designed and implemented (Martello and Toth 1997).”
A new branch-and-cut algorithm for the capacitated vehicle routing problem (2004, methodology): “For each partition we solve the corresponding BPP using the procedures in [31] and check the FCI.”
An improved typology of cutting and packing problems (2007, methodology): “ Martello and Toth, 1990, pp. 3, 13 –77) obviously is a special case of this problem type (i.e.”
Routing problems with loading constraints (2010, background): “The loading issues above are closely related to multi-dimensional packing problems, which arise as extensions of the classical (one dimensional) bin packing (see, e.g., Martello and Toth 1990; Coffman et al. 1997, 1999).”
Improved Online Algorithms for Knapsack and GAP in the Random Order Model (2020, methodology): “We refer the readers to textbooks [25, 36] and to the surveys of previous work in [15,20] for further references.”
An Exact Approach to the Strip-Packing Problem (2003, background): “The bound presented in this section can be seen either as an extension of the bound by Martello and Toth (1990ab) or as a specialization of the general bounding technique proposed by Fekete and Schepers (1997b).”
A PTAS for the multiple knapsack problem (2000, background): “This is natural when viewed as a knapsack problem (see [24]).”
Robust Submodular Observation Selection (2008, background): “In their seminal work, Nemhauser et al. (1978) and Wolsey (1982) analyze the greedy algorithm for optimizing monotonic submodular functions.”
The load planning problem for double-stack intermodal trains (2017, background): “The load planning problem may be viewed as a special case of the packing-cuttingknapsack problems (Martello and Toth, 1990; Dowsland and Dowsland, 1992; Dyckhoff et al., 1997).”
Local Search Heuristics for Capacitated p-Median Problems (2003, methodology): “5 Each problem is solved using the Horowitz and Sahni code (see Martello and Toth [12]).”
A survey of recent developments in multiobjective optimization (2007, methodology): “An excellent survey of algorithmic approaches for solving this problem can be found in Martello and Toth (1990) and Martello et al.”
QoS-aware middleware for Web services composition (2004, background): “This problem is a special case of the knapsack problem and hence NP-hard [22].”