{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,24]],"date-time":"2026-01-24T18:57:09Z","timestamp":1769281029556,"version":"3.49.0"},"reference-count":20,"publisher":"Elsevier BV","license":[{"start":{"date-parts":[[2003,4,1]],"date-time":"2003-04-01T00:00:00Z","timestamp":1049155200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Electronic Notes in Discrete Mathematics"],"published-print":{"date-parts":[[2003,4]]},"DOI":"10.1016\/s1571-0653(04)00442-1","type":"journal-article","created":{"date-parts":[[2004,10,23]],"date-time":"2004-10-23T09:17:34Z","timestamp":1098523054000},"page":"71-75","source":"Crossref","is-referenced-by-count":4,"special_numbering":"C","title":["Performance Ratios for the Karmarkar-Karp Differencing Method"],"prefix":"10.1016","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","family":"van Leeuwen i","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"78","reference":[{"key":"10.1016\/S1571-0653(04)00442-1_NEWBIB1","doi-asserted-by":"crossref","first-page":"260","DOI":"10.1287\/moor.9.2.260","article-title":"A note on expected makespans for largest-first sequences of independent tasks on two processors","volume":"9","author":"Coffman","year":"1984","journal-title":"Mathematics of Operations Research"},{"issue":"1","key":"10.1016\/S1571-0653(04)00442-1_NEWBIB2","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1137\/0207001","article-title":"An application of bin-packing to multiprocessor scheduling","volume":"7","author":"Coffman","year":"1978","journal-title":"SIAM Journal on Computing"},{"key":"10.1016\/S1571-0653(04)00442-1_NEWBIB3","series-title":"Scheduling Theory and its Applications","first-page":"15","article-title":"Recent asymptotic results in the probabilistic analysis of schedule makespans","author":"Coffman","year":"1995"},{"key":"10.1016\/S1571-0653(04)00442-1_NEWBIB4","doi-asserted-by":"crossref","first-page":"117","DOI":"10.1007\/BF02591687","article-title":"Worst-case analysis of the differencing method for the partition problem","volume":"37","author":"Fischetti","year":"1987","journal-title":"Mathematical Programming"},{"key":"10.1016\/S1571-0653(04)00442-1_NEWBIB5","doi-asserted-by":"crossref","first-page":"187","DOI":"10.1016\/0166-218X(86)90060-0","article-title":"The rate of convergence to optimality of the LPT rule","volume":"14","author":"Frenk","year":"1986","journal-title":"Discrete Applied Mathematics"},{"issue":"1","key":"10.1016\/S1571-0653(04)00442-1_NEWBIB6","doi-asserted-by":"crossref","first-page":"170","DOI":"10.1137\/0213013","article-title":"Tighter bounds for the multifit processor scheduling algorithm","volume":"13","author":"Friesen","year":"1984","journal-title":"SIAM Journal on Computing"},{"key":"10.1016\/S1571-0653(04)00442-1_NEWBIB7","series-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"Garey","year":"1979"},{"issue":"2","key":"10.1016\/S1571-0653(04)00442-1_NEWBIB8","doi-asserted-by":"crossref","first-page":"416","DOI":"10.1137\/0117039","article-title":"Bounds on multiprocessing timing anomalies","volume":"17","author":"Graham","year":"1969","journal-title":"SIAM Journal on Applied Mathematics"},{"key":"10.1016\/S1571-0653(04)00442-1_NEWBIB9","doi-asserted-by":"crossref","first-page":"287","DOI":"10.1016\/S0167-5060(08)70356-X","article-title":"Optimization and approximation in deterministic sequencing and scheduling: A survey","volume":"5","author":"Graham","year":"1979","journal-title":"Annals of Discrete Mathematics"},{"key":"10.1016\/S1571-0653(04)00442-1_NEWBIB10","doi-asserted-by":"crossref","first-page":"144","DOI":"10.1145\/7531.7535","article-title":"Using dual approximation algorithms for scheduling problems: Thoretical and practical results","volume":"34","author":"Hochbaum","year":"1987","journal-title":"Journal of the ACM"},{"key":"10.1016\/S1571-0653(04)00442-1_NEWBIB11","unstructured":"N. Karmarkar and R. M. Karp. The differencing method of set partitioning. Technical Report UCB\/CSD 82\/113, University of California, Berkeley, 1982."},{"key":"10.1016\/S1571-0653(04)00442-1_NEWBIB12","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1016\/S0004-3702(98)00086-1","article-title":"A complete anytime algorithm for number partitioning","volume":"106","author":"Korf","year":"1998","journal-title":"Artificial Intelligence"},{"issue":"6","key":"10.1016\/S1571-0653(04)00442-1_NEWBIB13","doi-asserted-by":"crossref","first-page":"285","DOI":"10.1016\/0167-6377(87)90044-7","article-title":"A note on the average-case behavior of a simple differencing method for partitioning","volume":"6","author":"Lueker","year":"1987","journal-title":"Operations Research Letters"},{"key":"10.1016\/S1571-0653(04)00442-1_NEWBIB14","unstructured":"S. Mertens. A complete anytime algorithm for balanced number partitioning, 1999. preprint xxx.lanl.gov\/abs\/cs.DS\/9903011."},{"issue":"2","key":"10.1016\/S1571-0653(04)00442-1_NEWBIB15","doi-asserted-by":"crossref","first-page":"251","DOI":"10.1007\/BF02192530","article-title":"Easily searched encodings for number partitioning","volume":"89","author":"Ruml","year":"1996","journal-title":"Journal of Optimization Theory and Applications"},{"key":"10.1016\/S1571-0653(04)00442-1_NEWBIB16","doi-asserted-by":"crossref","first-page":"465","DOI":"10.1007\/BF02156630","article-title":"Problem space local search for number partitioning","volume":"63","author":"Storer","year":"1996","journal-title":"Annals of Operations Research"},{"key":"10.1016\/S1571-0653(04)00442-1_NEWBIB17","doi-asserted-by":"crossref","first-page":"175","DOI":"10.1016\/0166-218X(94)00032-9","article-title":"The modified differencing method for the set partitioning problem with cardinality constraints","volume":"63","author":"Tasi","year":"1995","journal-title":"Discrete Applied Mathematics"},{"issue":"1","key":"10.1016\/S1571-0653(04)00442-1_NEWBIB18","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1137\/0221007","article-title":"Asymptotic analysis of an algorithm for balanced parallel processor scheduling","volume":"21","author":"Tsai","year":"1992","journal-title":"SIAM Journal on Computing"},{"issue":"1","key":"10.1016\/S1571-0653(04)00442-1_NEWBIB19","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1287\/moor.21.1.85","article-title":"The differencing algorithm LDM for partitioning: A proof of Karp's conjecture","volume":"21","author":"Yakir","year":"1996","journal-title":"Mathematics of Operations Research"},{"key":"10.1016\/S1571-0653(04)00442-1_NEWBIB20","doi-asserted-by":"crossref","first-page":"233","DOI":"10.1007\/BF02216826","article-title":"On the exact upper bound for the multifit processor scheduling algorithm","volume":"24","author":"Yue","year":"1990","journal-title":"Annals of Operations Research"}],"container-title":["Electronic Notes in Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S1571065304004421?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S1571065304004421?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2019,2,2]],"date-time":"2019-02-02T17:55:45Z","timestamp":1549130145000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S1571065304004421"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003,4]]},"references-count":20,"alternative-id":["S1571065304004421"],"URL":"https:\/\/doi.org\/10.1016\/s1571-0653(04)00442-1","relation":{},"ISSN":["1571-0653"],"issn-type":[{"value":"1571-0653","type":"print"}],"subject":[],"published":{"date-parts":[[2003,4]]}}}