The DOI matches its Crossref record; 14 of the 14 references it cites were found in a registry or an index.
A Polynomial Time Approximation Scheme for the Multiple Knapsack Problem
Abstract
The multiple knapsack problem (MKP) is a natural and well-known generalization of the single knapsack problem and is defined as follows. We are given a set of n items and m bins (knapsacks) such that each item i has a profit $p(i)$ and a size $s(i)$, and each bin j has a capacity $c(j)$. The goal is to find a subset of items of maximum profit such that they have a feasible packing in the bins. MKP is a special case of the generalized assignment problem (GAP) where the profit and the size of an item can vary based on the specific bin that it is assigned to. GAP is APX-hard and a 2-approximation, for it is implicit in the work of Shmoys and Tardos [Math. Program. A, 62 (1993), pp. 461-474], and thus far, this was also the best known approximation for MKP\@. The main result of this paper is a polynomial time approximation scheme (PTAS) for MKP\@. Apart from its inherent theoretical interest as a common generalization of the well-studied knapsack and bin packing problems, it appears to be the strongest special case of GAP that is not APX-hard. We substantiate this by showing that slight generalizations of MKP are APX-hard. Thus our results help demarcate the boundary at which instances of GAP become APX-hard. An interesting aspect of our approach is a PTAS-preserving reduction from an arbitrary instance of MKP to an instance with $O(\log n)$ distinct sizes and profits.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
(1979) · Cited by 43,841
An analysis of approximations for maximizing submodular set functions—I
Nemhauser, G. L., Wolsey, L. A., & Fisher, M. L. (1978) · Mathematical Programming · doi:10.1007/bf01588971 · Cited by 4,412
Knapsack Problems: Algorithms and Computer Implementations
Connolly, D., Martello, S., & Toth, P. (1991) · Journal of the Operational Research Society · doi:10.2307/2583458 · Cited by 3,120
Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems
Ibarra, O. H., & Kim, C. E. (1975) · Journal of the ACM · doi:10.1145/321906.321909 · Cited by 959
An approximation algorithm for the generalized assignment problem
Shmoys, D. B., & Tardos, É. (1993) · Mathematical Programming · doi:10.1007/bf01585178 · Cited by 726
An analysis of approximations for maximizing submodular set functions—II
Fisher, M. L., Nemhauser, G. L., & Wolsey, L. A. (1978) · Mathematical Programming Studies · doi:10.1007/bfb0121195 · Cited by 589
Bin packing can be solved within 1 + ε in linear time
de la Véga, W. F., & Lueker, G. S. (1981) · COMBINATORICA · doi:10.1007/bf02579456 · Cited by 510
An efficient approximation scheme for the one-dimensional bin-packing problem
Karmarkar, N. K., & Karp, R. M. (1982) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1982.61 · Cited by 491
Fast Approximation Algorithms for Knapsack Problems
Lawler, E. L. (1979) · Mathematics of Operations Research · doi:10.1287/moor.4.4.339 · Cited by 411
e-approximations with minimum packing constraint violation (extended abstract)
Lin, J.-H., & Vitter, J. S. (1992) · Proceedings of the twenty-fourth annual ACM symposium on Theory of computing - STOC '92 · doi:10.1145/129712.129787 · Cited by 215
Approximation Algorithms for the Multiple Knapsack Problem with Assignment Restrictions
Dawande, M., Kalagnanam, J., Keskinocak, P., Salman, F. S., & Ravi, R. (2000) · Journal of Combinatorial Optimization · doi:10.1023/a:1009894503716 · Cited by 148
Heuristic algorithms for the multiple knapsack problem
Martello, S., & Toth, P. (1981) · Computing · doi:10.1007/bf02243544 · Cited by 82
An Efficient Approximation Scheme for Variable-Sized Bin Packing
Murgolo, F. D. (1987) · SIAM Journal on Computing · doi:10.1137/0216012 · Cited by 79
A Polynomial Time Approximation Scheme for the Multiple Knapsack Problem
Kellerer, H. G. (1999) · Lecture notes in computer science · doi:10.1007/978-3-540-48413-4_6 · Cited by 58
Cited by
Maximizing a Monotone Submodular Function Subject to a Matroid Constraint
Calinescu, G., Chekuri, C., Pál, M., & Vondrák, J. (2011) · SIAM Journal on Computing · doi:10.1137/080733991 · Cited by 795
Self-citationOnline Matching and Ad Allocation
Mehta, A. (2010) · Foundations and Trends® in Theoretical Computer Science · doi:10.1561/0400000057 · Cited by 387
Han, S., Shen, H., Philipose, M., Agarwal, S., Wolman, A., & Krishnamurthy, A. (2016) · Proceedings of the 14th Annual International Conference on Mobile Systems, Applications, and Services · doi:10.1145/2906388.2906396 · Cited by 367
Bin Packing Approximation Algorithms: Survey and Classification
Coffman, E. G., Csirik, J., Galambos, G., Martello, S., & Vigo, D. (2013) · Handbook of Combinatorial Optimization · doi:10.1007/978-1-4419-7997-1_35 · Cited by 289
(2015) · Cited by 14
Metadata
- Authors
- Chekuri, C., & Khanna, S.
- Venue
- SIAM Journal on Computing
- Published
- 2005-01
- Volume
- 35
- Issue
- 3
- Pages
- 713-728
- ISSN
- 0097-5397 (ISSN-L)
- 1095-7111
- OpenAlex
- W2000444555
- Cited by
- 332
- References
- 14
- FWCI
- 19.04
- Type
- journal article
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.