{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,22]],"date-time":"2026-03-22T00:17:39Z","timestamp":1774138659174,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":17,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540422877","type":"print"},{"value":"9783540482246","type":"electronic"}],"license":[{"start":{"date-parts":[[2001,1,1]],"date-time":"2001-01-01T00:00:00Z","timestamp":978307200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2001]]},"DOI":"10.1007\/3-540-48224-5_69","type":"book-chapter","created":{"date-parts":[[2007,10,28]],"date-time":"2007-10-28T02:29:04Z","timestamp":1193538544000},"page":"848-861","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":14,"title":["A PTAS for Minimizing Weighted Completion Time on Uniformly Related Machines"],"prefix":"10.1007","author":[{"given":"Chandra","family":"Chekuri","sequence":"first","affiliation":[]},{"given":"Sanjeev","family":"Khanna","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2001,7,4]]},"reference":[{"key":"69_CR1","unstructured":"F. Afrati, E. Bampis, C. Chekuri, D. Karger, C. Kenyon, S. Khanna, I. Milis, M. Queyranne, M. Skutella, C. Stein, and M. Sviridenko. Approximation Schemes for Minimizing Average Weighted Completion Time with Release Dates. FOCS\u2019 99."},{"key":"69_CR2","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1002\/(SICI)1099-1425(199806)1:1<55::AID-JOS2>3.0.CO;2-J","volume":"1","author":"N. Alon","year":"1998","unstructured":"N. Alon, Y. Azar, G. J. Woeginger, and T. Yadid. Approximation schemes for scheduling on parallel machines. Journal of Scheduling, 1:55\u201366, 1998.","journal-title":"Journal of Scheduling"},{"key":"69_CR3","unstructured":"S. Chakrabarti, C. A. Phillips, A. S. Schulz, D. B. Shmoys, C. Stein, and J. Wein. Improved scheduling algorithms for minsum criteria. ICALP\u2019 96."},{"key":"69_CR4","unstructured":"C. Chekuri and S. Khanna. A PTAS for the Multiple Knapsack Problem. SODA\u2019 00."},{"key":"69_CR5","unstructured":"C. Chekuri, R. Motwani, B. Natarajan, and C. Stein. Approximation techniques for average completion time scheduling. SODA\u2019 97."},{"key":"69_CR6","unstructured":"M. X. Goemans. Improved approximation algorithms for scheduling with release dates. SODA\u2019 97."},{"key":"69_CR7","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1016\/S0167-5060(08)70356-X","volume":"5","author":"R. L. Graham","year":"1979","unstructured":"R. L. Graham, E. L. Lawler, J. K. Lenstra, and A. H. G Rinnooy Kan. Optimization and approximation in deterministic sequencing and scheduling: a survey. Ann. Discrete Math., 5:287\u2013326, 1979.","journal-title":"Ann. Discrete Math."},{"key":"69_CR8","doi-asserted-by":"crossref","unstructured":"L. A. Hall, A. S. Schulz, D. B. Shmoys, and J. Wein. Scheduling to minimize average completion time: Offline and online algorithms. Math. of OR, 513-44,\u2019 97.","DOI":"10.1287\/moor.22.3.513"},{"key":"69_CR9","doi-asserted-by":"publisher","first-page":"144","DOI":"10.1145\/7531.7535","volume":"34","author":"D. S. Hochbaum","year":"1987","unstructured":"D. S. Hochbaum and D. B. Shmoys. Using dual approximation algorithms for scheduling problems: theoretical and practical results. JACM, 34:144\u2013162, 1987.","journal-title":"JACM"},{"key":"69_CR10","doi-asserted-by":"publisher","first-page":"539","DOI":"10.1137\/0217033","volume":"17","author":"D. S. Hochbaum","year":"1988","unstructured":"D. S. Hochbaum and D. B. Shmoys. A polynomial approximation scheme for scheduling on uniform processors: using the dual approximation approach. SIAM Journal on Computing, 17:539\u2013551, 1988.","journal-title":"SIAM Journal on Computing"},{"key":"69_CR11","unstructured":"J. A. Hoogeveen, P. Schuurman, and G. J. Woeginger. Non-approximability results for scheduling problems with minsum criteria. IPCO\u2019 98."},{"key":"69_CR12","doi-asserted-by":"publisher","first-page":"343","DOI":"10.1016\/S0167-5060(08)70743-X","volume":"1","author":"J. K. Lenstra","year":"1977","unstructured":"J. K. Lenstra, A. H. G. Rinnooy Kan, and P. Brucker. Complexity of machine scheduling problems. Annals of Discrete Mathematics, 1:343\u2013362, 1977.","journal-title":"Annals of Discrete Mathematics"},{"key":"69_CR13","unstructured":"A. Munier, M. Queyranne, and A. S. Schulz. Approximation bounds for a general class of precedence constrained parallel machine scheduling problems. IPCO\u2019 98."},{"key":"69_CR14","first-page":"199","volume":"82","author":"C. Phillips","year":"1998","unstructured":"C. Phillips, C. Stein, and J. Wein. Minimizing average completion time in the presence of release dates. Mathematical Programming B, 82:199\u2013223, 1998.","journal-title":"Mathematical Programming B"},{"key":"69_CR15","unstructured":"A. S. Schulz and M. Skutella. Scheduling-LPs bear probabilities: Randomized approximations for min-sum criteria. ESA\u2019 97."},{"key":"69_CR16","unstructured":"M. Skutella and G. J. Woeginger. A PTAS for minimizing the weighted sum of job completion times on parallel machines. STOC\u2019 99."},{"key":"69_CR17","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1002\/nav.3800030106","volume":"3","author":"W. E. Smith","year":"1956","unstructured":"W. E. Smith. Various optimizers for single-stage production. Naval Res. Logist. Quart., 3:59\u201366, 1956.","journal-title":"Naval Res. Logist. Quart."}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-48224-5_69","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,19]],"date-time":"2019-05-19T10:46:51Z","timestamp":1558262811000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-48224-5_69"}},"subtitle":["Extended Abstract"],"short-title":[],"issued":{"date-parts":[[2001]]},"ISBN":["9783540422877","9783540482246"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/3-540-48224-5_69","relation":{},"ISSN":["0302-9743"],"issn-type":[{"value":"0302-9743","type":"print"}],"subject":[],"published":{"date-parts":[[2001]]},"assertion":[{"value":"4 July 2001","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}