{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,26]],"date-time":"2025-10-26T14:11:39Z","timestamp":1761487899958,"version":"3.33.0"},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540424871"},{"type":"electronic","value":"9783540446699"}],"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-44669-9_56","type":"book-chapter","created":{"date-parts":[[2007,8,10]],"date-time":"2007-08-10T10:32:26Z","timestamp":1186741946000},"page":"495-507","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":7,"title":["On Minimizing Average Weighted Completion Time: A PTAS for Scheduling General Multiprocessor Tasks"],"prefix":"10.1007","author":[{"given":"Aleksei V.","family":"Fishkin","sequence":"first","affiliation":[]},{"given":"Klaus","family":"Jansen","sequence":"additional","affiliation":[]},{"given":"Lorant","family":"Porkolab","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2001,8,2]]},"reference":[{"key":"56_CR1","doi-asserted-by":"crossref","unstructured":"F. Afrati, E. Bampis, C. Chekuri, D. Karger, C. Kenyon, S. Khanna, I. Millis, M. Queyranne, M. Skutella, C. Stein, and M. Sviridenko, Approximation schemes for minimizing average weighted completion time with release dates, Proceedings 40th IEEE Symposium on Foundations of Computer Science (1999), 32\u201343.","DOI":"10.1109\/SFFCS.1999.814574"},{"key":"56_CR2","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"454","DOI":"10.1007\/3-540-44450-5_37","volume-title":"Proceedings 20th Conference on Foundations of Software Technology and Theoretical Computer Science","author":"F. Afrati","year":"2000","unstructured":"F. Afrati, E. Bampis, A. V. Fishkin, K. Jansen, C. Kenyon, Scheduling to minimize the average completion time of dedicated tasks, Proceedings 20th Conference on Foundations of Software Technology and Theoretical Computer Science, LNCS 1974, Springer Verlag (2000), 454\u2013464."},{"key":"56_CR3","series-title":"Lect Notes Comput Sci","first-page":"1","volume-title":"Proceedings 5th European Symposium on Algorithms","author":"A. K. Amoura","year":"1997","unstructured":"A. K. Amoura, E. Bampis, C. Kenyon, and Y. Manoussakis, Scheduling independent multiprocessor tasks, Proceedings 5th European Symposium on Algorithms, LNCS 1284, Springer Verlag (1997), 1\u201312."},{"key":"56_CR4","doi-asserted-by":"publisher","first-page":"323","DOI":"10.1002\/1099-1425(200011\/12)3:6<323::AID-JOS52>3.0.CO;2-E","volume":"3","author":"F. Afrati","year":"2000","unstructured":"F. Afrati, E. Bampis, C. Kenyon and I. Milis, A PTAS for the average weighted completion time problem on unrelated machines, Journal of Scheduling 3 (2000), 323\u2013332.","journal-title":"Journal of Scheduling"},{"key":"56_CR5","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1006\/inco.1997.2677","volume":"140","author":"A. Bar-Noy","year":"1998","unstructured":"A. Bar-Noy, M. Bellare, M. M. Halld\u00f3rsson, H. Shachnai, and T. Tamir, On chromatic sums and distributed resource allocation, Information and Computation 140 (1998), 183\u2013202.","journal-title":"Information and Computation"},{"key":"56_CR6","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"390","DOI":"10.1007\/3-540-48481-7_34","volume-title":"Proceedings 7th European Symposium on Algorithms","author":"A. Bar-Noy","year":"1999","unstructured":"A. Bar-Noy and M. M. Halld\u00f3rsson and G. Kortsarz and R. Salman and H. Shachnai, Sum multicoloring of graphs, Proceedings 7th European Symposium on Algorithms, LNCS 1643, Springer Verlag (1999), 390\u2013401."},{"key":"56_CR7","first-page":"504","volume-title":"Proceedings of the IFIP Congress","author":"J. L. Bruno","year":"1974","unstructured":"J. L. Bruno, E. G. Coffman, Jr., R. Sethi, Algorithms for minimizing mean flow time, Proceedings of the IFIP Congress, North-Holland, Amsterdam, (1974), 504\u2013510."},{"key":"56_CR8","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1002\/(SICI)1520-6750(199803)45:2<231::AID-NAV7>3.0.CO;2-9","volume":"45","author":"X. Cai","year":"1998","unstructured":"X. Cai, C.-Y. Lee, and C.-L. Li, Minimizing total completion time in two-processor task systems with prespecified processor allocation, Naval Research Logistics 45 (1998), 231\u2013242.","journal-title":"Naval Research Logistics"},{"key":"56_CR9","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"646","DOI":"10.1007\/3-540-61440-0_166","volume-title":"Proceedings 23rd International Colloquium on Automata, Languages and Programming","author":"S. Chakrabarti","year":"1996","unstructured":"S. Chakrabarti, C. A. Philips, A. S. Schulz, D. B. Shmoys, C. Stein, and J. Wein, Improved scheduling algorithms for minsum criteria, Proceedings 23rd International Colloquium on Automata, Languages and Programming, LNCS 1099, Springer Verlag (1996), 646\u2013657."},{"key":"56_CR10","doi-asserted-by":"crossref","unstructured":"J. Chen and A. Miranda, A polynomial time approximation scheme for general multiprocessor job scheduling, Proceedings 31st ACM Symposium on the Theory of Computing (1999), 418\u2013427.","DOI":"10.1145\/301250.301363"},{"key":"56_CR11","doi-asserted-by":"publisher","first-page":"473","DOI":"10.1137\/0402042","volume":"2","author":"J. Du","year":"1989","unstructured":"J. Du and J. Leung, Complexity of scheduling parallel task systems, SIAM Journal on Discrete Mathematics 2 (1989), 473\u2013487.","journal-title":"SIAM Journal on Discrete Mathematics"},{"issue":"2","key":"56_CR12","doi-asserted-by":"publisher","first-page":"187","DOI":"10.1006\/jcss.1998.1587","volume":"57","author":"U. Feige","year":"1998","unstructured":"U. Feige and J. Kilian, Zero-knowledge and the chromatic number, in Journal of Computer and System Science 57(2) (1998), 187\u2013199.","journal-title":"Journal of Computer and System Science"},{"key":"56_CR13","unstructured":"A. V. Fishkin, K. Jansen, L. Porkolab, On minimizing average weighted completion time of multiprocessor tasks with release dates, to appear on ICALP01."},{"key":"56_CR14","volume-title":"Computers and intractability: A guide to the theory of NP-completeness","author":"M. R. Garey","year":"1979","unstructured":"M. R. Garey and D. S. Johnson, Computers and intractability: A guide to the theory of NP-completeness, Freeman, San Francisco, CA, 1979."},{"key":"56_CR15","doi-asserted-by":"publisher","first-page":"513","DOI":"10.1287\/moor.22.3.513","volume":"22","author":"L. A. Hall","year":"1997","unstructured":"L. A. Hall, A. S. Schulz, D. B. Shmoys, and J. Wein, Scheduling to minimize average time: Offline and online algorithm, Mathematics of Operation Research 22 (1997), 513\u2013544.","journal-title":"Mathematics of Operation Research"},{"key":"56_CR16","doi-asserted-by":"publisher","first-page":"259","DOI":"10.1016\/0166-218X(94)90012-4","volume":"55","author":"J. A. Hoogeveen","year":"1994","unstructured":"J. A. Hoogeveen, S. L. Van de Velde, and B. Veltman, Complexity of scheduling multiprocessor tasks with prespecified processor allocations, Discrete Applied Mathematics 55 (1994), 259\u2013272.","journal-title":"Discrete Applied Mathematics"},{"key":"56_CR17","series-title":"Lect Notes Comput Sci","doi-asserted-by":"publisher","first-page":"110","DOI":"10.1007\/3-540-48447-7_13","volume-title":"Proceedings 6th International Workshop on Algorithms and Data Structures","author":"K. Jansen","year":"1999","unstructured":"K. Jansen and L. Porkolab, General multiprocessor task scheduling: approximate solution in linear time, Proceedings 6th International Workshop on Algorithms and Data Structures, LNCS 1663, Springer Verlag (1999), 110\u2013121."},{"key":"56_CR18","doi-asserted-by":"crossref","unstructured":"M. Skutella and G. J. Woeginger, A PTAS for minimizing the weighted sum of job completion times on parallel machines, Proceedings 31st ACM Symposium on Theory of Computing (1999), 400\u2013407.","DOI":"10.1145\/301250.301356"},{"key":"56_CR19","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 Research Logistic Quarterly 3 (1956), 59\u201366.","journal-title":"Naval Research Logistic Quarterly"},{"key":"56_CR20","doi-asserted-by":"crossref","unstructured":"J. Turek, W. Ludwig, J. Wolf, and P. Yu, Scheduling parallel tasks to minimize average response times, Proceedings 5th ACM-SIAM Symposium on Discrete Algorithms (1994), 112\u2013121.","DOI":"10.1145\/181014.181331"}],"container-title":["Lecture Notes in Computer Science","Fundamentals of Computation Theory"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-44669-9_56","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,20]],"date-time":"2025-01-20T07:28:01Z","timestamp":1737358081000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-44669-9_56"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2001]]},"ISBN":["9783540424871","9783540446699"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/3-540-44669-9_56","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2001]]},"assertion":[{"value":"2 August 2001","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}