{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,6]],"date-time":"2025-11-06T05:54:58Z","timestamp":1762408498036},"reference-count":22,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2006,10,7]],"date-time":"2006-10-07T00:00:00Z","timestamp":1160179200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2006,11,15]]},"DOI":"10.1007\/s10878-006-9010-z","type":"journal-article","created":{"date-parts":[[2006,10,6]],"date-time":"2006-10-06T11:14:43Z","timestamp":1160133283000},"page":"19-32","source":"Crossref","is-referenced-by-count":7,"title":["Performance ratios of the Karmarkar-Karp differencing method"],"prefix":"10.1007","volume":"13","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 van","family":"Leeuwen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2006,10,7]]},"reference":[{"key":"9010_CR1","doi-asserted-by":"crossref","unstructured":"Coffman EG Jr, Frederickson GN, Lueker GS (1984) A note on expected makespans for largest-first sequences of independent tasks on two processors. Math Oper Res 9:260\u2013266","DOI":"10.1287\/moor.9.2.260"},{"key":"9010_CR2","doi-asserted-by":"crossref","unstructured":"Coffman EG Jr, Garey MR, Johnson DS (1978) An application of bin-packing to multiprocessor scheduling. SIAM J Comput 7:1\u201317","DOI":"10.1137\/0207001"},{"key":"9010_CR3","unstructured":"Coffman EG Jr, Whitt W (1995) Recent asymptotic results in the probabilistic analysis of schedule makespans In: Chretienne P, Coffman EG Jr, Lenstra JK, Liu Z (eds) Scheduling theory and its applications, Wiley, pp 15\u201331"},{"key":"9010_CR4","doi-asserted-by":"crossref","first-page":"117","DOI":"10.1007\/BF02591687","volume":"37","author":"M Fischetti","year":"1987","unstructured":"Fischetti M, Martello S (1987) Worst-case analysis of the differencing method for the partition problem, Math Program 37:117\u2013120","journal-title":"Math Program"},{"key":"9010_CR5","doi-asserted-by":"crossref","first-page":"187","DOI":"10.1016\/0166-218X(86)90060-0","volume":"14","author":"JBG Frenk","year":"1986","unstructured":"Frenk JBG, Rinnooy Kan AHG (1986) The rate of convergence to optimality of the LPT rule. Discrete Appli Math 14:187\u2013197","journal-title":"Discrete Appli Math"},{"key":"9010_CR6","doi-asserted-by":"crossref","first-page":"170","DOI":"10.1137\/0213013","volume":"13","author":"DK Friesen","year":"1984","unstructured":"Friesen DK (1984) Tighter bounds for the multifit processor scheduling algorithm. SIAM J Comput 13:170\u2013181","journal-title":"SIAM J Comput"},{"key":"9010_CR7","volume-title":"Computers and intractability: a guide to the theory of NP-completeness","author":"MR Garey","year":"1979","unstructured":"Garey MR, Johnson DS (1979) Computers and intractability: a guide to the theory of NP-completeness. W.H. Freeman and Company, New York"},{"key":"9010_CR8","doi-asserted-by":"crossref","first-page":"416","DOI":"10.1137\/0117039","volume":"17","author":"RL Graham","year":"1969","unstructured":"Graham RL (1969) Bounds on multiprocessing timing anomalies. SIAM J Appl Math 17:416\u2013429","journal-title":"SIAM J Appl Math"},{"key":"9010_CR9","doi-asserted-by":"crossref","first-page":"287","DOI":"10.1016\/S0167-5060(08)70356-X","volume":"5","author":"RL Graham","year":"1979","unstructured":"Graham RL, Lawler EL, Lenstra JK, Rinnooy Kan AHG (1979) Optimization and approximation in deterministic sequencing and scheduling: a survey. Ann Discrete Math 5:287\u2013326","journal-title":"Ann Discrete Math"},{"key":"9010_CR10","doi-asserted-by":"crossref","first-page":"144","DOI":"10.1145\/7531.7535","volume":"34","author":"DS Hochbaum","year":"1987","unstructured":"Hochbaum DS, Shmoys DB (1987) Using dual approximation algorithms for scheduling problems: theoretical and practical results. J ACM 34:144\u2013162","journal-title":"J ACM"},{"key":"9010_CR11","unstructured":"Karmarkar N, Karp RM (1982) The differencing method of set partitioning. Technical Report UCB\/CSD 82\/113, University of California, Berkeley"},{"key":"9010_CR12","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1016\/S0004-3702(98)00086-1","volume":"106","author":"RE Korf","year":"1998","unstructured":"Korf RE (1998) A complete anytime algorithm for number partitioning. Artif Intell 106:181\u2013203","journal-title":"Artif Intell"},{"key":"9010_CR13","doi-asserted-by":"crossref","first-page":"285","DOI":"10.1016\/0167-6377(87)90044-7","volume":"6","author":"GS Lueker","year":"1987","unstructured":"Lueker GS (1987) A note on the average-case behavior of a simple differencing method for partitioning. Oper Res Lett 6:285\u2013287","journal-title":"Oper Res Lett"},{"key":"9010_CR14","unstructured":"Mertens S (1999) A complete anytime algorithm for balanced number partitioning, Preprint xxx.lanl.gov\/abs\/cs.DS\/9903011"},{"key":"9010_CR15","unstructured":"Michiels W (2004) Performance ratios for the differencing method. Ph.D. thesis, Eindhoven University of Technology"},{"key":"9010_CR16","doi-asserted-by":"crossref","unstructured":"Michiels W, Korst J, Aarts E, van Leeuwen J (2003) Performance ratios for the differencing method applied to the balanced number partitioning problem. In Proceedings of the 20th international symposium on theoretical aspects of computer science, Berlin, pp 583\u2013595","DOI":"10.1007\/3-540-36494-3_51"},{"key":"9010_CR17","doi-asserted-by":"crossref","first-page":"251","DOI":"10.1007\/BF02192530","volume":"89","author":"W Ruml","year":"1996","unstructured":"Ruml W, Ngo JTO, Marks J, Shieber S (1996) Easily searched encodings for number partitioning. J Optim Theory Appl 89:251\u2013291","journal-title":"J Optim Theory Appl"},{"key":"9010_CR18","doi-asserted-by":"crossref","first-page":"465","DOI":"10.1007\/BF02156630","volume":"63","author":"RH Storer","year":"1996","unstructured":"Storer RH, Flanders SW, Wu SD (1996) Problem space local search for number partitioning. Ann Oper Res 63:465\u2013487","journal-title":"Ann Oper Res"},{"key":"9010_CR19","doi-asserted-by":"crossref","first-page":"175","DOI":"10.1016\/0166-218X(94)00032-9","volume":"63","author":"LH Tasi","year":"1995","unstructured":"Tasi LH (1995) The modified differencing method for the set partitioning problem with cardinality constraints. Discrete Appl Math 63:175\u2013180","journal-title":"Discrete Appl Math"},{"key":"9010_CR20","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1137\/0221007","volume":"21","author":"LH Tsai","year":"1992","unstructured":"Tsai LH (1992) Asymptotic analysis of an algorithm for balanced parallel processor scheduling. SIAM J Comput 21:59\u201364","journal-title":"SIAM J Comput"},{"key":"9010_CR21","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1287\/moor.21.1.85","volume":"21","author":"B Yakir","year":"1996","unstructured":"Yakir B (1996) The differencing algorithm LDM for partitioning: a proof of Karp\u2019s conjecture. Math Oper Res 21:85\u201399","journal-title":"Math Oper Res"},{"key":"9010_CR22","doi-asserted-by":"crossref","first-page":"233","DOI":"10.1007\/BF02216826","volume":"24","author":"M Yue","year":"1990","unstructured":"Yue M (1990) On the exact upper bound for the multifit processor scheduling algorithm. Ann Oper Res 24:233\u2013259","journal-title":"Ann Oper Res"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-006-9010-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10878-006-9010-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-006-9010-z","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,31]],"date-time":"2019-05-31T00:18:10Z","timestamp":1559261890000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10878-006-9010-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,10,7]]},"references-count":22,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2006,11,15]]}},"alternative-id":["9010"],"URL":"https:\/\/doi.org\/10.1007\/s10878-006-9010-z","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"value":"1382-6905","type":"print"},{"value":"1573-2886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006,10,7]]}}}