{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,26]],"date-time":"2025-10-26T14:12:13Z","timestamp":1761487933550},"reference-count":23,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2007,10,24]],"date-time":"2007-10-24T00:00:00Z","timestamp":1193184000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2008,7]]},"DOI":"10.1007\/s00224-007-9082-x","type":"journal-article","created":{"date-parts":[[2007,10,23]],"date-time":"2007-10-23T10:46:16Z","timestamp":1193136376000},"page":"81-98","source":"Crossref","is-referenced-by-count":25,"title":["Approximation Schemes for Packing with Item Fragmentation"],"prefix":"10.1007","volume":"43","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"}]},{"given":"Omer","family":"Yehezkely","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2007,10,24]]},"reference":[{"key":"9082_CR1","doi-asserted-by":"crossref","first-page":"307","DOI":"10.1016\/S0304-3975(98)00003-6","volume":"205","author":"P. Beling","year":"1998","unstructured":"Beling, P., Megiddo, N.: Using fast matrix multiplication to find basic solutions. Theor. Comput. Sci. 205, 307\u2013316 (1998)","journal-title":"Theor. Comput. Sci."},{"issue":"3","key":"9082_CR2","doi-asserted-by":"crossref","first-page":"671","DOI":"10.1137\/S0097539702410697","volume":"32","author":"O. Braun","year":"2003","unstructured":"Braun, O., Schmidt, G.: Parallel processor scheduling with limited number of preemptions. SIAM J. Comput. 32(3), 671\u2013680 (2003)","journal-title":"SIAM J. Comput."},{"key":"9082_CR3","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-540-24804-0","volume-title":"Scheduling Algorithms","author":"P. Brucker","year":"2004","unstructured":"Brucker, P.: Scheduling Algorithms, 4th edn. Springer, Berlin (2004)","edition":"4"},{"key":"9082_CR4","first-page":"46","volume-title":"Approximation Algorithms for NP-Hard Problems","author":"E.G. Coffman Jr.","year":"1997","unstructured":"Coffman, E.G. Jr., Garey, M.R., Johnson, D.S.: Approximation algorithms for bin packing: a survey. In: Hochbaum, D.S. (ed.) Approximation Algorithms for NP-Hard Problems, pp.\u00a046\u201393. PWS Publishing, Boston (1997)"},{"key":"9082_CR5","volume-title":"Introduction to Algorithms","author":"T.H. Cormen","year":"2002","unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, 2nd edn. MIT Press\/McGraw\u2013Hill, Cambridge\/New York (2002)","edition":"2"},{"key":"9082_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"151","DOI":"10.1007\/3-540-48481-7_14","volume-title":"Proc. of the 7th European Symposium on Algorithms","author":"L. Epstein","year":"1999","unstructured":"Epstein, L., Sgall, J.: Approximation schemes for scheduling on uniformly related and identical parallel machines. In: Proc. of the 7th European Symposium on Algorithms. Lecture Notes in Computer Science, vol. 1643, pp.\u00a0151\u2013162. Springer, Berlin (1999)"},{"key":"9082_CR7","doi-asserted-by":"crossref","first-page":"349","DOI":"10.1007\/BF02579456","volume":"1","author":"W. Fernandez de\u00a0la\u00a0Vega","year":"1981","unstructured":"Fernandez de\u00a0la\u00a0Vega, W., Lueker, G.S.: Bin packing can be solved within 1+\u03b5 in linear time. Combinatorica 1, 349\u2013355 (1981)","journal-title":"Combinatorica"},{"key":"9082_CR8","volume-title":"Computers and Intractability: A\u00a0Guide to the Theory of NP-Completeness","author":"M.R. Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A\u00a0Guide to the Theory of NP-Completeness. Freeman, San Francisco (1979)"},{"issue":"1","key":"9082_CR9","doi-asserted-by":"crossref","first-page":"144","DOI":"10.1145\/7531.7535","volume":"34","author":"D.S. Hochbaum","year":"1987","unstructured":"Hochbaum, D.S., Shmoys, D.B.: Using dual approximation algorithms for scheduling problems: Practical and theoretical results. J. ACM 34(1), 144\u2013162 (1987)","journal-title":"J. ACM"},{"key":"9082_CR10","doi-asserted-by":"crossref","first-page":"373","DOI":"10.1007\/BF02579150","volume":"4","author":"N. Karmarkar","year":"1984","unstructured":"Karmarkar, N.: A\u00a0new polynomial-time algorithm for linear programming. Combinatorica 4, 373\u2013396 (1984)","journal-title":"Combinatorica"},{"key":"9082_CR11","unstructured":"Karmarkar, N., Karp, R.M.: An efficient approximation scheme for the one dimensional bin packing problem. In: Proc. 23rd IEEE Annual Symposium on Foundations of Computer Science, pp.\u00a0312\u2013320, 1982"},{"key":"9082_CR12","series-title":"Computer and Information Science Series","volume-title":"Handbook of Scheduling: Algorithms, Models and Performance Analysis","year":"2004","unstructured":"Leung, J.Y.-T. (ed.): Handbook of Scheduling: Algorithms, Models and Performance Analysis. Computer and Information Science Series. Chapman & Hall\/CRC, Boca Raton (2004)"},{"issue":"11","key":"9082_CR13","doi-asserted-by":"crossref","first-page":"91","DOI":"10.1016\/S0898-1221(98)00087-X","volume":"35","author":"C.A. Mandal","year":"1998","unstructured":"Mandal, C.A., Chakrabarti, P.P., Ghose, S.: Complexity of fragmentable object bin packing and an application. Comp. Math. Appl. 35(11), 91\u201397 (1998)","journal-title":"Comp. Math. Appl."},{"key":"9082_CR14","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1287\/mnsc.6.1.1","volume":"6","author":"R. McNaughton","year":"1959","unstructured":"McNaughton, R.: Scheduling with deadlines and loss functions. Manag. Sci. 6, 1\u201312 (1959)","journal-title":"Manag. Sci."},{"key":"9082_CR15","unstructured":"Menakerman, N., Rom, R.: Bin packing problems with item fragmentations. In: Proc. of WADS, 2001"},{"key":"9082_CR16","unstructured":"Motwani, R.: Lecture notes on approximation algorithms. Technical report, Dept. of Computer Science, Stanford Univ., CA (1992)"},{"key":"9082_CR17","unstructured":"Multimedia Cable Network System Ltd.: Data-over-cable service interface specification, http:\/\/www.cablelabs.com (2000)"},{"key":"9082_CR18","unstructured":"Naaman, N., Rom, R.: Packet scheduling with fragmentation. In: Proc. of INFOCOM\u201902, pp.\u00a0824\u2013831, 2002"},{"key":"9082_CR19","doi-asserted-by":"crossref","first-page":"309","DOI":"10.1007\/s00453-005-1171-0","volume":"42","author":"H. Shachnai","year":"2005","unstructured":"Shachnai, H., Tamir, T., Woeginger, G.J.: Minimizing makespan and preemption costs on a system of uniform machines. Algorithmica 42, 309\u2013334 (2005)","journal-title":"Algorithmica"},{"key":"9082_CR20","unstructured":"Sourd, F.: Preemptive scheduling with position costs. Algorithmic Oper. Res. AOR 1(2) (2006)"},{"key":"9082_CR21","doi-asserted-by":"crossref","first-page":"375","DOI":"10.1007\/s10107-003-0448-9","volume":"97","author":"D.A. Spielman","year":"2003","unstructured":"Spielman, D.A., Teng, S.-H.: Smoothed analysis of termination of linear programming algorithms. Math. Program. Ser. B 97, 375\u2013404 (2003)","journal-title":"Math. Program. Ser. B"},{"key":"9082_CR22","doi-asserted-by":"crossref","first-page":"417","DOI":"10.1007\/s101070100261","volume":"91","author":"M.J. Todd","year":"2002","unstructured":"Todd, M.J.: The many facets of linear programming. Math. Program. Ser. B 91, 417\u2013436 (2002)","journal-title":"Math. Program. Ser. B"},{"key":"9082_CR23","first-page":"74","volume-title":"Approximation Algorithms","author":"V.V. Vazirani","year":"2001","unstructured":"Vazirani, V.V.: Bin packing. In: Approximation Algorithms, pp.\u00a074\u201378. Springer, Berlin (2001)"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-007-9082-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-007-9082-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-007-9082-x","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,24]],"date-time":"2019-05-24T07:51:35Z","timestamp":1558684295000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-007-9082-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,10,24]]},"references-count":23,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2008,7]]}},"alternative-id":["9082"],"URL":"https:\/\/doi.org\/10.1007\/s00224-007-9082-x","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2007,10,24]]}}}