{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,1]],"date-time":"2025-08-01T03:47:58Z","timestamp":1754020078348},"reference-count":28,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2008,4,8]],"date-time":"2008-04-08T00:00:00Z","timestamp":1207612800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2010,4]]},"DOI":"10.1007\/s00453-008-9188-9","type":"journal-article","created":{"date-parts":[[2008,4,7]],"date-time":"2008-04-07T15:36:48Z","timestamp":1207582608000},"page":"505-528","source":"Crossref","is-referenced-by-count":17,"title":["Bin Packing with Rejection Revisited"],"prefix":"10.1007","volume":"56","author":[{"given":"Leah","family":"Epstein","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2008,4,8]]},"reference":[{"key":"9188_CR1","doi-asserted-by":"crossref","unstructured":"Bansal, N., Blum, A., Chawla, S., Dhamdhere, K.: Scheduling for flow-time with admission control. In: Proc. of the 11th Annual European Symposium on Algorithms (ESA2003), pp.\u00a043\u201354 (2003)","DOI":"10.1007\/978-3-540-39658-1_7"},{"issue":"1","key":"9188_CR2","doi-asserted-by":"crossref","first-page":"64","DOI":"10.1137\/S0895480196300522","volume":"13","author":"Y. Bartal","year":"2000","unstructured":"Bartal, Y., Leonardi, S., Marchetti-Spaccamela, A., Sgall, J., Stougie, L.: Multiprocessor scheduling with rejection. SIAM J. Discrete Math. 13(1), 64\u201378 (2000)","journal-title":"SIAM J. Discrete Math."},{"key":"9188_CR3","doi-asserted-by":"crossref","unstructured":"Bein, W.W., Correa, J.R., Han, X.: A\u00a0fast asymptotic approximation scheme for bin packing with rejection. In: Proc. of the 1st International Symposium on Combinatorics, Algorithms, Probabilistic and Experimental Methodologies (ESCAPE2007), pp.\u00a0209\u2013218 (2007)","DOI":"10.1007\/978-3-540-74450-4_19"},{"key":"9188_CR4","doi-asserted-by":"crossref","first-page":"58","DOI":"10.1002\/nav.10058","volume":"92","author":"A. Caprara","year":"2003","unstructured":"Caprara, A., Kellerer, H., Pferschy, U.: Approximation schemes for ordered vector packing problems. Naval Res. Logist. 92, 58\u201369 (2003)","journal-title":"Naval Res. Logist."},{"key":"9188_CR5","volume-title":"Approximation Algorithms","author":"E.G. Coffman","year":"1997","unstructured":"Coffman, E.G., Garey, M.R., Johnson, D.S.: Approximation algorithms for bin packing: a\u00a0survey. In: Hochbaum, D. (ed.) Approximation Algorithms. PWS Publishing Company, Boston (1997)"},{"key":"9188_CR6","doi-asserted-by":"crossref","unstructured":"Csirik, J., Woeginger, G.J.: On-line packing and covering problems. In: Fiat,\u00a0A., Woeginger,\u00a0G.J. (eds.) Online Algorithms: The State of the Art, pp.\u00a0147\u2013177 (1998)","DOI":"10.1007\/BFb0029568"},{"issue":"2","key":"9188_CR7","doi-asserted-by":"crossref","first-page":"308","DOI":"10.1016\/S0196-6774(02)00202-X","volume":"44","author":"J. Csirik","year":"2002","unstructured":"Csirik, J., Woeginger, G.J.: Resource augmentation for online bounded space bin packing. J.\u00a0Algorithms 44(2), 308\u2013320 (2002)","journal-title":"J.\u00a0Algorithms"},{"key":"9188_CR8","doi-asserted-by":"crossref","first-page":"349","DOI":"10.1007\/BF02579456","volume":"1","author":"W. Fernandez de la Vega","year":"1981","unstructured":"Fernandez de la Vega, W., Lueker, G.S.: Bin packing can be solved within 1+\u03b5 in linear time. Combinatorica 1, 349\u2013355 (1981)","journal-title":"Combinatorica"},{"key":"9188_CR9","doi-asserted-by":"crossref","unstructured":"D\u00f3sa, G.: The tight bound of first fit decreasing bin-packing algorithm is FFD(I)\u226411\/9OPT(I)+6\/9. In: Proc. of the 1st International Symposium on Combinatorics, Algorithms, Probabilistic and Experimental Methodologies (ESCAPE2007), pp.\u00a01\u201311 (2007)","DOI":"10.1007\/978-3-540-74450-4_1"},{"issue":"5","key":"9188_CR10","doi-asserted-by":"crossref","first-page":"795","DOI":"10.1016\/j.ic.2006.02.003","volume":"204","author":"G. D\u00f3sa","year":"2006","unstructured":"D\u00f3sa, G., He, Y.: Bin packing problems with rejection penalties and their dual problems. Inf. Comput. 204(5), 795\u2013815 (2006)","journal-title":"Inf. Comput."},{"issue":"1","key":"9188_CR11","doi-asserted-by":"crossref","first-page":"175","DOI":"10.1016\/S0196-6774(03)00078-6","volume":"49","author":"D.W. Engels","year":"2003","unstructured":"Engels, D.W., Karger, D.R., Kolliopoulos, S.G., Sengupta, S., Uma, R.N., Wein, J.: Techniques for scheduling with rejection. J.\u00a0Algorithms 49(1), 175\u2013191 (2003)","journal-title":"J.\u00a0Algorithms"},{"key":"9188_CR12","unstructured":"Epstein, L., Levin, A.: AFPTAS results for common variants of bin packing: a\u00a0new method to handle the small items. Manuscript (2007)"},{"key":"9188_CR13","volume-title":"Computers and Intractability","author":"M.R. Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability. Freeman, New York (1979)"},{"issue":"1","key":"9188_CR14","first-page":"144","volume":"34","author":"D.S. Hochbaum","year":"1987","unstructured":"Hochbaum, D.S., Shmoys, D.B.: Using dual approximation algorithms for scheduling problems: theoretical and practical results. J.\u00a0ACM 34(1), 144\u2013162 (1987)","journal-title":"J.\u00a0ACM"},{"key":"9188_CR15","doi-asserted-by":"crossref","unstructured":"Hoogeveen, H., Skutella, M., Woeginger, G.J.: Preemptive scheduling with rejection. In: Proc. of the 8th Annual European Symposium on Algorithms (ESA2000), pp.\u00a0268\u2013277 (2000)","DOI":"10.1007\/3-540-45253-2_25"},{"key":"9188_CR16","doi-asserted-by":"crossref","first-page":"272","DOI":"10.1016\/S0022-0000(74)80026-7","volume":"8","author":"D.S. Johnson","year":"1974","unstructured":"Johnson, D.S.: Fast algorithms for bin packing. J.\u00a0Comput. Syst. Sci. 8, 272\u2013314 (1974)","journal-title":"J.\u00a0Comput. Syst. Sci."},{"key":"9188_CR17","doi-asserted-by":"crossref","first-page":"256","DOI":"10.1137\/0203025","volume":"3","author":"D.S. Johnson","year":"1974","unstructured":"Johnson, D.S., Demers, A., Ullman, J.D., Garey, M.R., Graham, R.L.: Worst-case performance bounds for simple one-dimensional packing algorithms. SIAM J. Comput. 3, 256\u2013278 (1974)","journal-title":"SIAM J. Comput."},{"key":"9188_CR18","doi-asserted-by":"crossref","unstructured":"Karmarkar, N., Karp, R.M.: An efficient approximation scheme for the one-dimensional bin-packing problem. In: Proceedings of the 23rd Annual Symposium on Foundations of Computer Science (FOCS\u201982), pp.\u00a0312\u2013320 (1982)","DOI":"10.1109\/SFCS.1982.61"},{"issue":"3","key":"9188_CR19","first-page":"562","volume":"32","author":"C.C. Lee","year":"1985","unstructured":"Lee, C.C., Lee, D.T.: A\u00a0simple online bin packing algorithm. J.\u00a0ACM 32(3), 562\u2013572 (1985)","journal-title":"J.\u00a0ACM"},{"key":"9188_CR20","doi-asserted-by":"crossref","first-page":"305","DOI":"10.1016\/0196-6774(89)90031-X","volume":"10","author":"P. Ramanan","year":"1989","unstructured":"Ramanan, P., Brown, D.J., Lee, C.C., Lee, D.T.: Online bin packing in linear time. J.\u00a0Algorithms 10, 305\u2013326 (1989)","journal-title":"J.\u00a0Algorithms"},{"issue":"5","key":"9188_CR21","first-page":"640","volume":"49","author":"S.S. Seiden","year":"2002","unstructured":"Seiden, S.S.: On the online bin packing problem. J.\u00a0ACM 49(5), 640\u2013671 (2002)","journal-title":"J.\u00a0ACM"},{"issue":"4","key":"9188_CR22","doi-asserted-by":"crossref","first-page":"579","DOI":"10.1002\/1520-6750(199406)41:4<579::AID-NAV3220410409>3.0.CO;2-G","volume":"41","author":"D. Simchi-Levi","year":"1994","unstructured":"Simchi-Levi, D.: New worst-case results for the bin-packing problem. Naval Res. Logist. 41(4), 579\u2013585 (1994)","journal-title":"Naval Res. Logist."},{"key":"9188_CR23","unstructured":"Ullman, J.D.: The performance of a memory allocation algorithm. Technical Report 100, Princeton University, Princeton, NJ (1971)"},{"issue":"5","key":"9188_CR24","doi-asserted-by":"crossref","first-page":"277","DOI":"10.1016\/0020-0190(92)90223-I","volume":"43","author":"A. Vliet van","year":"1992","unstructured":"van Vliet, A.: An improved lower bound for online bin packing algorithms. Inf. Process. Lett. 43(5), 277\u2013284 (1992)","journal-title":"Inf. Process. Lett."},{"key":"9188_CR25","first-page":"207","volume":"27","author":"A.C.C. Yao","year":"1980","unstructured":"Yao, A.C.C.: New algorithms for bin packing. J.\u00a0ACM 27, 207\u2013227 (1980)","journal-title":"J.\u00a0ACM"},{"key":"9188_CR26","doi-asserted-by":"crossref","first-page":"321","DOI":"10.1007\/BF02009683","volume":"7","author":"M. Yue","year":"1991","unstructured":"Yue, M.: A simple proof of the inequality FFD(L)\u2264(11\/9)OPT(L)+1, \u2200 L, for the FFD bin-packing algorithm. Acta Math. Appl. Sin. 7, 321\u2013331 (1991)","journal-title":"Acta Math. Appl. Sin."},{"key":"9188_CR27","unstructured":"Zhang, G.: Private communication"},{"key":"9188_CR28","doi-asserted-by":"crossref","first-page":"217","DOI":"10.1016\/S0167-6377(99)00077-2","volume":"26","author":"G. Zhang","year":"2000","unstructured":"Zhang, G., Cai, X., Wong, C.K.: Linear time approximation algorithms for bin packing. Oper. Res. Lett. 26, 217\u2013222 (2000)","journal-title":"Oper. Res. Lett."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-008-9188-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-008-9188-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-008-9188-9","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T13:45:02Z","timestamp":1559137502000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-008-9188-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,4,8]]},"references-count":28,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2010,4]]}},"alternative-id":["9188"],"URL":"https:\/\/doi.org\/10.1007\/s00453-008-9188-9","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008,4,8]]}}}