{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,1,17]],"date-time":"2025-01-17T09:18:57Z","timestamp":1737105537753,"version":"3.33.0"},"publisher-location":"Berlin, Heidelberg","reference-count":26,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540679967"},{"type":"electronic","value":"9783540444367"}],"license":[{"start":{"date-parts":[[2000,1,1]],"date-time":"2000-01-01T00:00:00Z","timestamp":946684800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2000]]},"DOI":"10.1007\/3-540-44436-x_24","type":"book-chapter","created":{"date-parts":[[2007,6,18]],"date-time":"2007-06-18T09:33:14Z","timestamp":1182159194000},"page":"238-249","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":7,"title":["Polynomial Time Approximation Schemes for Class-Constrained Packing Problems"],"prefix":"10.1007","author":[{"given":"Hadas","family":"Shachnai","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tami","family":"Tamir","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2003,6,3]]},"reference":[{"key":"24_CR1","unstructured":"A. Caprara, H. Kellerer, U. Pferschy, and D. Pisinger. Approximation algorithms for knapsack problems with cardinalityc onstraints. European Journal of Operations Research. To appear."},{"key":"24_CR2","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1016\/0304-3975(76)90048-7","volume":"3","author":"A.K. Chandra","year":"1976","unstructured":"A.K. Chandra, D.S. Hirschberg, and C.K. Wong. Approximate algorithms for some generalized knapsack problems. Theoretical Computer Science, 3:293\u2013304, 1976.","journal-title":"Theoretical Computer Science"},{"key":"24_CR3","unstructured":"C. Chekuri and S. Khanna. A PTAS for the multiple knapsack problem. SODA\u2019 00. pp. 213\u2013222."},{"key":"24_CR4","unstructured":"E.G. Coffman, M.R. Garey, and D.S. Johnson. Approximation Algorithms for Bin Packing: A Survey. in Approximation Algorithms for NP-hard Problems. D.S. Hochbaum (Ed.). PWS Publishing Company, 1995."},{"key":"24_CR5","volume-title":"Variable sized bin packing with color-constraints","author":"M. Dawande","year":"1999","unstructured":"M. Dawande, J. Kalagnanam, and J. Sethuraman. Variable sized bin packing with color-constraints. TR, IBM, T.J.Watson Research Center, Yorktown Heights, 1999."},{"key":"24_CR6","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"151","DOI":"10.1007\/3-540-48481-7_14","volume-title":"ESA\u2019 99","author":"L. Epstein","year":"1999","unstructured":"L. Epstein and J. Sgall. Approximation schemes for scheduling on uniformlyre lated and identical parallel machines.ESA\u2019 99, LNCS 1643, pp. 151\u2013162. Springer-Verlag."},{"key":"24_CR7","doi-asserted-by":"publisher","first-page":"858","DOI":"10.1137\/S1052623493254455","volume":"6","author":"C.E. Ferreira","year":"1996","unstructured":"C.E. Ferreira, A. Martin and, R. Weismantel. Solving multiple knapsack problems byc utting planes. SIAM J. on Opt., 6:858\u2013877, 1996.","journal-title":"SIAM J. on Opt."},{"key":"24_CR8","doi-asserted-by":"publisher","first-page":"499","DOI":"10.1145\/322077.322090","volume":"25","author":"M.R. Gareyan","year":"1978","unstructured":"M.R. Gareyan and D.S. Johnson. Strong NP-completeness results: Motivations, examples, and implications. Journal of the ACM, 25:499\u2013508, 1978.","journal-title":"Journal of the ACM"},{"key":"24_CR9","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"292","DOI":"10.1007\/3-540-09526-8_26","volume-title":"The 8th International Symp. on Mathematical Foundations of Computer Science","author":"G.V. Gens","year":"1979","unstructured":"G.V. Gens and E.V. Levner. Computational complexityof approximation algorithms for combinatorial problems. The 8th International Symp. on Mathematical Foundations of Computer Science, LNCS 74, pp. 292\u2013300. Springer-Verlag, 1979."},{"key":"24_CR10","unstructured":"L. Golubchik, S. Khanna, S. Khuller, R. Thurimella, and A. Zhu. Approximation algorithms for data placement on parallel disks. SODA\u201900, pp. 223\u2013232."},{"issue":"1","key":"24_CR11","doi-asserted-by":"publisher","first-page":"144","DOI":"10.1145\/7531.7535","volume":"34","author":"D.S. Hochbaum","year":"1987","unstructured":"D.S. Hochbaum and D.B. Shmoys. Using dual approximation algorithms for scheduling problems: Practical and theoretical results. Journal of the ACM, 34(1):144\u2013162, 1987.","journal-title":"Journal of the ACM"},{"issue":"4","key":"24_CR12","doi-asserted-by":"crossref","first-page":"643","DOI":"10.1002\/nav.3800260409","volume":"26","author":"M.S. Hung","year":"1979","unstructured":"M.S. Hung and J.C. Fisk. A heuristic routine for solving large loading problems. Naval Research Logistical Quarterly, 26(4):643\u201350, 1979.","journal-title":"Naval Research Logistical Quarterly"},{"key":"24_CR13","unstructured":"T. Ibaraki and N. Katoh. Resource Allocation Problems-Algorithmic Approaches. The MIT Press, 1988."},{"issue":"4","key":"24_CR14","doi-asserted-by":"publisher","first-page":"463","DOI":"10.1145\/321906.321909","volume":"22","author":"O.H. Ibarra","year":"1975","unstructured":"O.H. Ibarra and C.E. Kim. Fast approximation for the knapsack and the sum of subset problems. Journal of the ACM, 22(4):463\u2013468, 1975.","journal-title":"Journal of the ACM"},{"issue":"6","key":"24_CR15","doi-asserted-by":"publisher","first-page":"110","DOI":"10.1287\/opre.23.6.1110","volume":"23","author":"G. Ingargiola","year":"1975","unstructured":"G. Ingargiola and J. F. Korsh. An algorithm for the solution of 0-1 loading problems. Operations Research, 23(6):110\u2013119, 1975.","journal-title":"Operations Research"},{"key":"24_CR16","unstructured":"N. Karmakar and R.M. Karp. An effcient approximation scheme for the onedimensional bin packing problem. FOCS\u201982, pp. 312\u2013320."},{"key":"24_CR17","series-title":"Lect Notes Comput Sci","first-page":"51","volume-title":"APPROX\u201999","author":"H. Kellerer","year":"2004","unstructured":"H. Kellerer. A polynomial time approximation scheme for the multiple knapsack problem. APPROX\u201999, LNCS 1671, pp. 51\u201362. Springer-Verlag."},{"issue":"4","key":"24_CR18","doi-asserted-by":"crossref","first-page":"274","DOI":"10.1080\/03155986.1998.11732364","volume":"36","author":"E. Y.-H. Lin","year":"1998","unstructured":"E. Y-H Lin. A bibliographical surveyon some well-known non-standard knapsack problems. Information Systems and Oper. Research, 36:4, pp. 274\u2013317, 1998.","journal-title":"Information Systems and Oper. Research"},{"key":"24_CR19","first-page":"213","volume":"31","author":"S. Martello","year":"1987","unstructured":"S. Martello and P. Toth. Algorithms for knapsack problems. Annals of Discrete Math., 31:213\u2013258, 1987.","journal-title":"Annals of Discrete Math."},{"key":"24_CR20","series-title":"Technical report","volume-title":"Lecture notes on approximation algorithms","author":"R. Motwani","year":"1992","unstructured":"R. Motwani. Lecture notes on approximation algorithms. Technical report, Dept. of Computer Science, Stanford Univ., CA, 1992."},{"key":"24_CR21","unstructured":"H. Shachnai and T. Tamir. On two class-constrained versions of the multiple knapsack problem. Algorithmica. To appear."},{"key":"24_CR22","unstructured":"H. Shachnai and T. Tamir. Scheduling with limited number of machine allotments and limited parallelism. Manuscript, 2000."},{"key":"24_CR23","unstructured":"H. Shachnai and T. Tamir. Polynomial time approximation schemes for classconstrained packing problems (full version). http:\/\/www.cs.technion.ac.il\/~hadas ."},{"key":"24_CR24","doi-asserted-by":"crossref","unstructured":"J. Turek, J. Wolf, and P. Yu. Approximate algorithms for scheduling parallelizable tasks. SPAA\u201992, pp. 323\u2013332.","DOI":"10.1145\/140901.141909"},{"key":"24_CR25","doi-asserted-by":"publisher","first-page":"349","DOI":"10.1007\/BF02579456","volume":"1","author":"W.F. Vega","year":"1981","unstructured":"W.F. Vega and G.S. Leuker. Bin packing can be solved within 1+\u03b5 in linear time. Combinatorica, 1:349\u2013355, 1981.","journal-title":"Combinatorica"},{"key":"24_CR26","doi-asserted-by":"publisher","first-page":"358","DOI":"10.1007\/s005300050067","volume":"5","author":"J.L. Wolf","year":"1997","unstructured":"J.L. Wolf, P.S. Yu, and H. Shachnai. Disk load balancing for video-on-demand systems. ACM Multimedia Systems Journal, 5:358\u2013370, 1997.","journal-title":"ACM Multimedia Systems Journal"}],"container-title":["Lecture Notes in Computer Science","Approximation Algorithms for Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-44436-X_24","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,17]],"date-time":"2025-01-17T08:33:18Z","timestamp":1737102798000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-44436-X_24"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2000]]},"ISBN":["9783540679967","9783540444367"],"references-count":26,"URL":"https:\/\/doi.org\/10.1007\/3-540-44436-x_24","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2000]]},"assertion":[{"value":"3 June 2003","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}