{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,19]],"date-time":"2025-03-19T17:01:33Z","timestamp":1742403693916},"publisher-location":"Berlin, Heidelberg","reference-count":23,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540006237"},{"type":"electronic","value":"9783540364948"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2003]]},"DOI":"10.1007\/3-540-36494-3_51","type":"book-chapter","created":{"date-parts":[[2010,3,29]],"date-time":"2010-03-29T17:12:04Z","timestamp":1269882724000},"page":"583-595","source":"Crossref","is-referenced-by-count":10,"title":["Performance Ratios for the Differencing Method Applied to the Balanced Number Partitioning Problem"],"prefix":"10.1007","author":[{"given":"Wil","family":"Michiels","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jan","family":"Korst","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Emile","family":"Aarts","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jan","family":"van Leeuwen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2003,2,17]]},"reference":[{"key":"51_CR1","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1007\/BF01193837","volume":"47","author":"L. Babel","year":"1998","unstructured":"L. Babel, H. Kellerer, and V. Kotov. The k-partitioning problem. Mathematical Methods of Operations Research, 47, pages 59\u201382, 1998.","journal-title":"Mathematical Methods of Operations Research"},{"key":"51_CR2","doi-asserted-by":"crossref","first-page":"192","DOI":"10.1287\/opre.36.2.192","volume":"36","author":"M. Ball","year":"1988","unstructured":"M. Ball and M. Magazine. Sequencing of insertions in printed circuit board assembly. Operations Research, 36, pages 192\u2013201, 1988.","journal-title":"Operations Research"},{"key":"51_CR3","doi-asserted-by":"publisher","first-page":"260","DOI":"10.1287\/moor.9.2.260","volume":"9","author":"E. Coffman","year":"1984","unstructured":"E. Coffman, G. Frederickson, and G. Lueker. A note on expected makespans for largest-first sequences of independent tasks on two processors. Mathematics of Operations Research, 9, pages 260\u2013266, 1984.","journal-title":"Mathematics of Operations Research"},{"issue":"1","key":"51_CR4","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1137\/0207001","volume":"7","author":"E.G. Coffman Jr","year":"1978","unstructured":"E.G. Coffman Jr, M.R. Garey, and D.S. Johnson. An application of bin-packing to multiprocessor scheduling. SIAM Journal on Computing, 7(1):1\u201317, 1978.","journal-title":"SIAM Journal on Computing"},{"key":"51_CR5","unstructured":"E.G. Coffman Jr. and W. Whitt. Recent asymptotic results in the probabilistic analysis of schedule makespans. In P. Chretienne, E.G. Coffman Jr., J.K. Lenstra, and Z. Liu, editors, Scheduling Theory and its Applications, pages 15\u201331.Wiley, 1995."},{"key":"51_CR6","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1007\/BF02591687","volume":"37","author":"M. Fischetti","year":"1987","unstructured":"M. Fischetti and S. Martello. Worst-case analysis of the differencing method for the partition problem. Mathematical Programming, 37, pages 117\u2013120, 1987.","journal-title":"Mathematical Programming"},{"key":"51_CR7","unstructured":"M. Garey and D. Johnson. Computers and Intractability: A Guide to the Theory of NPCompleteness. W.H. Freeman and Company, 1979."},{"key":"51_CR8","doi-asserted-by":"crossref","first-page":"1563","DOI":"10.1002\/j.1538-7305.1966.tb01709.x","volume":"45","author":"R. Graham","year":"1966","unstructured":"R. Graham. Bounds for certain multiprocessing anomalies. Bell System Technical Journal, 45, pages 1563\u20131581, 1966.","journal-title":"Bell System Technical Journal"},{"key":"51_CR9","doi-asserted-by":"publisher","first-page":"416","DOI":"10.1137\/0117039","volume":"17","author":"R. Graham","year":"1969","unstructured":"R. Graham. Bounds on multiprocessing timing anomalies. SIAM Journal on Applied Mathematics, 17, pages 416\u2013429, 1969.","journal-title":"SIAM Journal on Applied Mathematics"},{"key":"51_CR10","unstructured":"N. Karmarkar and R. Karp. The differencing method of set partitioning. Technical Report UCB\/CSD 82\/113, University of California, Berkeley, 1982."},{"issue":"1","key":"51_CR11","first-page":"48","volume":"37","author":"H. Kellerer","year":"1999","unstructured":"H. Kellerer and V. Kotov. A7\/6-approximation algorithm for 3-partitioning and its application to multiprocessor scheduling. INFOR, 37(1), pages 48\u201356, 1999.","journal-title":"INFOR"},{"key":"51_CR12","doi-asserted-by":"publisher","first-page":"249","DOI":"10.1016\/0166-218X(93)90013-E","volume":"45","author":"H. Kellerer","year":"1993","unstructured":"H. Kellerer and G. Woeginger.Atight bound for 3-partitioning. Discrete Applied Mathematics, 45, pages 249\u2013259, 1993.","journal-title":"Discrete Applied Mathematics"},{"key":"51_CR13","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1016\/S0004-3702(98)00086-1","volume":"106","author":"R. Korf","year":"1998","unstructured":"R. Korf. A complete anytime algorithm for number partitioning. Artificial Intelligence, 106, pages 181\u2013203, 1998.","journal-title":"Artificial Intelligence"},{"key":"51_CR14","doi-asserted-by":"publisher","first-page":"285","DOI":"10.1016\/0167-6377(87)90044-7","volume":"6","author":"G. Lueker","year":"1987","unstructured":"G. Lueker. A note on the average-case behavior of a simple differencing method for partitioning. Operations Research Letters, 6, pages 285\u2013288, 1987.","journal-title":"Operations Research Letters"},{"key":"51_CR15","unstructured":"S. Mertens. A complete anytime algorithm for balanced number partitioning, 1999. preprint \n                    http:\/\/xxx.lanl.gov\/abs\/cs.DS\/9903011\n                    \n                  ."},{"key":"51_CR16","unstructured":"W. Michiels. Performance Ratios for Differencing Methods. PhD thesis, Technische Universiteit Eindhoven, 2003."},{"key":"51_CR17","doi-asserted-by":"publisher","first-page":"271","DOI":"10.1002\/jos.80","volume":"4","author":"W. Michiels","year":"2001","unstructured":"W. Michiels and J. Korst. Min-max subsequence problems in multi-zone disk recording. Journal of Scheduling, 4, pages 271\u2013283, 2001.","journal-title":"Journal of Scheduling"},{"key":"51_CR18","unstructured":"W. Michiels, J. Korst, E. Aarts, and J. van Leeuwen. Performance ratios for the Karmarkar-Karp Differencing Method. Technical Report 02\/17, Technische Universiteit Eindhoven, 2002. Submitted to Journal of Algorithms."},{"key":"51_CR19","doi-asserted-by":"publisher","first-page":"175","DOI":"10.1016\/0166-218X(94)00032-9","volume":"63","author":"L. Tasi","year":"1995","unstructured":"L. Tasi. The modified differencing method for the set partitioning problem with cardinality constraints. Discrete Applied Mathematics, 63, pages 175\u2013180, 1995.","journal-title":"Discrete Applied Mathematics"},{"key":"51_CR20","unstructured":"L. Tsai. The loading and scheduling problems in flexible manufacturing systems. PhD thesis, University of California, Berkeley, 1987."},{"key":"51_CR21","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1137\/0221007","volume":"21","author":"L. Tsai","year":"1992","unstructured":"L. Tsai. Asymptotic analysis of an algorithm for balanced parallel processor scheduling. SIAM Journal on Computing, 21, pages 59\u201364, 1992.","journal-title":"SIAM Journal on Computing"},{"key":"51_CR22","unstructured":"H. Williams. Model Building in Mathematical Programming. Wiley, 1978."},{"key":"51_CR23","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1287\/moor.21.1.85","volume":"21","author":"B. Yakir","year":"1996","unstructured":"B. Yakir. The differencing algorithm ldm for partitioning: A proof of karp\u2019s conjecture. Mathematics of Operations Research, 21, pages 85\u201399, 1996.","journal-title":"Mathematics of Operations Research"}],"container-title":["Lecture Notes in Computer Science","STACS 2003"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-36494-3_51","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,1,24]],"date-time":"2019-01-24T18:44:40Z","timestamp":1548355480000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-36494-3_51"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003]]},"ISBN":["9783540006237","9783540364948"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/3-540-36494-3_51","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2003]]}}}