{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,26]],"date-time":"2026-09-26T23:39:54Z","timestamp":1790465994146,"version":"4.1.0"},"reference-count":31,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2004,1]]},"abstract":"<jats:p>We study the approximability of multidimensional generalizations of three classical packing problems: multiprocessor scheduling, bin packing, and the knapsack problem. Specifically, we study the vector scheduling problem, its dual problem, namely, the vector bin packing problem, and a class of packing integer programs. The vector scheduling problem is to schedule nd -dimensional tasks on m machines such that the maximum load over all dimensions and all machines is minimized. The vector bin packing problem, on the other hand, seeks to minimize the number of bins needed to schedule all n tasks such that the maximum load on any dimension across all bins is bounded by a fixed quantity, say, 1. Such problems naturally arise when scheduling tasks that have multiple resource requirements. Finally, packing integer programs capture a core problem that directly relates to both vector scheduling and vector bin packing, namely, the problem of packing a maximum number of vectors in a single bin of unit height. We obtain a variety of new algorithmic as well as inapproximability results for these three problems.<\/jats:p>","DOI":"10.1137\/s0097539799356265","type":"journal-article","created":{"date-parts":[[2004,5,17]],"date-time":"2004-05-17T21:00:51Z","timestamp":1084827651000},"page":"837-851","source":"Crossref","is-referenced-by-count":149,"title":["On Multidimensional Packing Problems"],"prefix":"10.1137","volume":"33","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":[[2012,2,17]]},"reference":[{"key":"R1","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009203"},{"key":"R2","unstructured":"S. F. Assman,\n                      Problems in Discrete Applied Mathematics\n                      , Ph.D. thesis, Mathematics Department, Massachusetts Institute of Technology, Cambridge, MA, 1983."},{"key":"R3","unstructured":"Chandra Chekuri, Sanjeev Khanna, On multi\u2010dimensional packing problems, ACM, New York, 1999, 185\u20131942001a:68113"},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.1145\/129888.129894"},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1998.1587"},{"key":"R6","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579456"},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1016\/0377-2217(84)90053-5"},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1137\/0204015"},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.1016\/0097-3165(76)90001-7"},{"key":"R10","volume-title":"Computers and intractability","author":"Garey Michael","year":"1979"},{"key":"R11","doi-asserted-by":"publisher","DOI":"10.1145\/234782.234797"},{"key":"R12","doi-asserted-by":"crossref","unstructured":"M. N. Garofalakis and Y. E. Ioannidis,\n                      Multi\u2010dimensional resource scheduling for parallel queries\n                      , in Proceedings of the 1996 ACM SIGMOD International Conference on Management of Data, 1996, pp. 365\u2013376.","DOI":"10.1145\/233269.233352"},{"key":"R13","unstructured":"M. N. Garofalakis and Y. E. Ioannidis,\n                      Parallel query scheduling and optimization with time\u2010and space\u2010shared resources\n                      , in Proceedings of the 23rd International Conference on Very Large Data Bases, Morgan Kaufmann, San Francisco, 1997, pp. 296\u2013305."},{"key":"R14","unstructured":"M. N. Garofalakis, B. \u00d6zden, and A. Silberschatz,\n                      Resource scheduling in enhanced pay\u2010per\u2010view continuous media databases\n                      , in Proceedings of the 23rd International Conference on Very Large Data Bases, Morgan Kaufmann, San Francisco, 1997, pp. 516\u2013525."},{"key":"R15","doi-asserted-by":"publisher","DOI":"10.1002\/j.1538-7305.1966.tb01709.x"},{"key":"R16","doi-asserted-by":"publisher","DOI":"10.1137\/0117039"},{"key":"R17","doi-asserted-by":"crossref","unstructured":"Magn\u00fas Halld\u00f3rsson, Approximating k\u2010set cover and complementary graph coloring, Lecture Notes in Comput. Sci., Vol. 1084, Springer, Berlin, 1996, 118\u201313198b:90157","DOI":"10.1007\/3-540-61310-2_10"},{"key":"R18","doi-asserted-by":"crossref","unstructured":"J. H\u00e5stad,\n                      Clique is hard to approximate to within n1-\u03b5\n                      , in Proceedings of the 37th Annual Symposium on Foundations of Computer Science, IEEE Comput. Soc. Press, Los Alamitos, CA, 1996, pp. 627\u2013636.","DOI":"10.1109\/SFCS.1996.548522"},{"key":"R19","doi-asserted-by":"publisher","DOI":"10.1145\/7531.7535"},{"key":"R20","doi-asserted-by":"publisher","DOI":"10.1145\/321906.321909"},{"key":"R21","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\u2013320780411","DOI":"10.1109\/SFCS.1982.61"},{"key":"R22","doi-asserted-by":"crossref","unstructured":"R. M. Karp, M. Luby, and A. Marchetti\u2010Spaccamela,\n                      A probabilistic analysis of multi\u2010dimensional bin packing problems\n                      , in Proceedings of the Annual ACM Symposium on the Theory of Computing, 1984, pp. 289\u2013298.","DOI":"10.1145\/800057.808693"},{"key":"R23","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, Elsevier Science, Amsterdam, 1993, pp. 445\u2013522.","DOI":"10.1016\/S0927-0507(05)80189-6"},{"key":"R24","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(75)90058-8"},{"key":"R25","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511814075"},{"key":"R26","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(88)90003-7"},{"key":"R27","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579324"},{"key":"R28","volume-title":"Theory of linear and integer programming","author":"Schrijver Alexander","year":"1986"},{"key":"R29","doi-asserted-by":"crossref","unstructured":"A. Srinivasan,\n                      Improved approximations of packing and covering problems\n                      , in Proceedings of the 27th ACM Symposium on the Theory of Computing, 1995, pp. 268\u2013276.","DOI":"10.1145\/225058.225138"},{"key":"R30","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-6377(96)00055-7"},{"key":"R31","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(97)00179-8"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/S0097539799356265","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:16:47Z","timestamp":1787336207000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/S0097539799356265"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004,1]]},"references-count":31,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2004,1]]}},"alternative-id":["10.1137\/S0097539799356265"],"URL":"https:\/\/doi.org\/10.1137\/s0097539799356265","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2004,1]]}}}