{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,12]],"date-time":"2026-09-12T07:40:49Z","timestamp":1789198849656,"version":"build-2803163510"},"reference-count":28,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2005,1]]},"abstract":"<jats:p>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.<\/jats:p>","DOI":"10.1137\/s0097539700382820","type":"journal-article","created":{"date-parts":[[2006,2,4]],"date-time":"2006-02-04T21:00:21Z","timestamp":1139086821000},"page":"713-728","source":"Crossref","is-referenced-by-count":268,"title":["A Polynomial Time Approximation Scheme for the Multiple Knapsack Problem"],"prefix":"10.1137","volume":"35","author":[{"given":"Chandra","family":"Chekuri","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Sanjeev","family":"Khanna","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,27]]},"reference":[{"key":"R1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(76)90048-7"},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1023\/A:1009894503716"},{"key":"R3","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579456"},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.1137\/S1052623493254455"},{"key":"R5","doi-asserted-by":"crossref","unstructured":"L. Fleischer, M. Goemans, V. Mirrokni, and M. Sviridenko,\n                      (Almost) Tight Approximation Algorithms for Maximizing General Assignment Problems\n                      , to appear in Proceedings of the 17th Annual ACM\u2010SIAM Symposium on Discrete Algorithms, 2005.","DOI":"10.1145\/1109557.1109624"},{"key":"R6","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0121195"},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1016\/0377-2217(84)90053-5"},{"key":"R8","volume-title":"Computers and intractability","author":"Garey Michael","year":"1979"},{"key":"R9","doi-asserted-by":"crossref","unstructured":"Ashish Goel, Piotr Indyk, Stochastic load balancing and related problems, IEEE Computer Soc., Los Alamitos, CA, 1999, 579\u2013586MR1917597","DOI":"10.1109\/SFFCS.1999.814632"},{"key":"R10","doi-asserted-by":"publisher","DOI":"10.1137\/0217033"},{"key":"R11","doi-asserted-by":"publisher","DOI":"10.1002\/nav.3800250316"},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1002\/nav.3800260409"},{"key":"R13","doi-asserted-by":"publisher","DOI":"10.1145\/321906.321909"},{"key":"R14","doi-asserted-by":"publisher","DOI":"10.1287\/opre.23.6.1110"},{"key":"R15","unstructured":"J. R. Kalagnanam, M. W. Dawande, M. Trubmo, and H. S. Lee,\n                      Inventory Problems in Steel Industry\n                      , Technical report RC21171, IBM T. J. Watson Research Center, 1998."},{"key":"R16","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(91)90246-E"},{"key":"R17","doi-asserted-by":"crossref","unstructured":"Narendra Karmarkar, Richard Karp, An efficient approximation scheme for the one\u2010dimensional bin\u2010packing problem, IEEE, New York, 1982, 312\u2013320MR0780411","DOI":"10.1109\/SFCS.1982.61"},{"key":"R18","doi-asserted-by":"crossref","unstructured":"Hans Kellerer, A polynomial time approximation scheme for the multiple knapsack problem, Lecture Notes in Comput. Sci., Vol. 1671, Springer, Berlin, 1999, 51\u2013622001d:68236","DOI":"10.1007\/978-3-540-48413-4_6"},{"key":"R19","doi-asserted-by":"publisher","DOI":"10.1287\/moor.4.4.339"},{"key":"R20","doi-asserted-by":"crossref","unstructured":"E. L. Lawler, J. K. Lenstra, A. H. G. Rinnooy Kan, and D. B. Shmoys,\n                      Sequencing and scheduling: Algorithms and complexity\n                      , in Handbooks in Operations Research and Management Science, Vol. 4, S. C. Graves et al., eds., Elsevier, New York, 1993, pp. 445\u2013522.","DOI":"10.1016\/S0927-0507(05)80189-6"},{"key":"R21","doi-asserted-by":"publisher","DOI":"10.1007\/BF01585745"},{"key":"R22","doi-asserted-by":"crossref","unstructured":"J. Lin and J. S. Vitter,\n                      \u03b5\u2010approximations with minimum packing constraint\n                      , in Proceedings of the 24th Annual ACM Symposium on Theory of Computing, 1992, pp. 771\u2013782.","DOI":"10.1145\/129712.129787"},{"key":"R23","doi-asserted-by":"publisher","DOI":"10.1016\/0377-2217(80)90143-5"},{"key":"R24","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(81)90005-6"},{"key":"R25","doi-asserted-by":"publisher","DOI":"10.1007\/BF02243544"},{"key":"R26","unstructured":"S. Martello and P. Toth,\n                      Knapsack Problems: Algorithms and Computer Implementations\n                      , John Wiley and Sons, New York, 1990."},{"key":"R27","doi-asserted-by":"publisher","DOI":"10.1137\/0216012"},{"key":"R28","doi-asserted-by":"publisher","DOI":"10.1007\/BF01585178"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/S0097539700382820","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:16:03Z","timestamp":1787336163000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/S0097539700382820"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005,1]]},"references-count":28,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2005,1]]}},"alternative-id":["10.1137\/S0097539700382820"],"URL":"https:\/\/doi.org\/10.1137\/s0097539700382820","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2005,1]]}}}