{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T22:23:16Z","timestamp":1725488596360},"publisher-location":"Berlin, Heidelberg","reference-count":43,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540424871"},{"type":"electronic","value":"9783540446699"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2001]]},"DOI":"10.1007\/3-540-44669-9_50","type":"book-chapter","created":{"date-parts":[[2007,8,10]],"date-time":"2007-08-10T10:32:26Z","timestamp":1186741946000},"page":"432-444","source":"Crossref","is-referenced-by-count":1,"title":["Designing PTASs for MIN-SUM Scheduling Problems"],"prefix":"10.1007","author":[{"given":"F.","family":"Afrati","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"I.","family":"Milis","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2001,8,2]]},"reference":[{"key":"50_CR1","doi-asserted-by":"crossref","unstructured":"F. Afrati, E. Bampis, C. Chekuri, D. Karger, C. Kenyon, S. Khanna, I. Milis, M. Queyranne, M. Skutella, C. Stein, M. Sviridenko: Approximation schemes for minimizing average weighted completion time with release dates. In Proceedings of 40th FOCS (1999) 32\u201343.","DOI":"10.1109\/SFFCS.1999.814574"},{"key":"50_CR2","doi-asserted-by":"crossref","unstructured":"F. Afrati, E. Bampis, A. V. Fishkin, K. Jansen, C. Kenyon: Scheduling to minimize the average completion time of dedicated tasks. In Proceedings of 20th FSTTCS (2000) 454\u2013464.","DOI":"10.1007\/3-540-44450-5_37"},{"key":"50_CR3","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, I. Milis: Scheduling to minimize the weighted sum of completion times. Journal of Scheduling 3 (2000) 323\u2013332.","journal-title":"Journal of Scheduling"},{"key":"50_CR4","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, T. Yadid: Approximation schemes for scheduling on parallel machines. Journal of Scheduling 1 (1998) 55\u201366.","journal-title":"Journal of Scheduling"},{"key":"50_CR5","unstructured":"P. Bruker: Scheduling Algorithms. Springer, 1998. See also http:\/\/www.mathematik.uni-osnabrueck.de\/research\/OR\/class\/"},{"key":"50_CR6","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, C. L. Li: Minimizing total completion time in two-processor task systems with prespecified processor allocations. Naval Research Logistics, 45 (1998) 231\u2013242.","journal-title":"Naval Research Logistics"},{"key":"50_CR7","unstructured":"C. Chekuri, R. Motwani: Minimizing weigthed completion time on a single machine. In Proceedings of 10th SODA (1999) 873\u2013874."},{"key":"50_CR8","unstructured":"C. Chekuri, R. Motwani, B. Natarajan, C. Stein: Approximation techniques for average completion time scheduling. In Proceedings of 8th SODA (1997) 609\u2013618."},{"key":"50_CR9","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1016\/0166-218X(90)90104-K","volume":"26","author":"M. E. Dyer","year":"1990","unstructured":"M. E. Dyer, L. A. Wosley: Formulating the single machine sequencing problem with release dates as a mixed integer program. Discrete Applied Math. 26 (1990) 255\u2013270.","journal-title":"Discrete Applied Math."},{"key":"50_CR10","doi-asserted-by":"crossref","unstructured":"A. V. Fishkin, K. Jansen, L. Porkolab: On minimizing average weigthed time completion time of multiprocessor tasks with release dates. Submitted, 2001.","DOI":"10.1007\/3-540-48224-5_71"},{"key":"50_CR11","unstructured":"M. X. Goemans, M. Queyranne, A. S. Shulz, M. Skutella, Y. Wang: Single machine scheduling with release dates. Submitted, 1999 (see http:\/\/www.math.tu-berlin.de\/~skutella\/publications.html )."},{"key":"50_CR12","doi-asserted-by":"crossref","first-page":"1563","DOI":"10.1002\/j.1538-7305.1966.tb01709.x","volume":"45","author":"R.L. Graham","year":"1996","unstructured":"R.L. Graham: Bounds on certain multiprocessor anomalies. Bell Systems Tech. J. 45 (1996) 1563\u20131581.","journal-title":"Bell Systems Tech. J."},{"key":"50_CR13","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, A.H.G. Rinnooy Kan: Optimization and approximation in deterministic sequencing and scheduling. Ann. Discrete Math. 5 (1979) 287\u2013326.","journal-title":"Ann. Discrete Math."},{"key":"50_CR14","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, J. Wein: Scheduling to minimize average completion time: on-line and off-line approximation algorithms. Mathematics of Operations Research 22 (1997) 513\u2013544.","journal-title":"Mathematics of Operations Research"},{"key":"50_CR15","unstructured":"L.A. Hall, D.B. Shmoys, J. Wein: Scheduling to minimize average completion time: on-line and off-line algorithms. In Proceedings of 7th SODA (1996) 142\u2013151."},{"key":"50_CR16","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"353","DOI":"10.1007\/3-540-69346-7_27","volume-title":"Proceedings of 6th IPCO","author":"H. Hoogeveen","year":"1998","unstructured":"H. Hoogeveen, P. Schuurman, G.J. Woeginger: Non-approximability results for scheduling problems with minsum criteria. In Proceedings of 6th IPCO, LNCS 1412 (1998) 353\u2013366."},{"key":"50_CR17","doi-asserted-by":"publisher","first-page":"1119","DOI":"10.1137\/0215081","volume":"15","author":"T. Kawaguchi","year":"1986","unstructured":"T. Kawaguchi, S. Kyan: Worst case bound of an LRF schedule for the mean weighted flow-time problem. SIAM J. on Computing 15 (1986) 1119\u20131129.","journal-title":"SIAM J. on Computing"},{"key":"50_CR18","unstructured":"H. Kellerer, T. Tautenhahnm, G. J. Woeginger: Approximability and nonappprox-imability results for minimizing total flow time on a single machine. In Proceedings of 28th STOC (1996) 418\u2013426."},{"key":"50_CR19","unstructured":"Leonardi, D. Raz: Approximating total flow time on parallel machines. In Proceedings of 29th STOC (1997) 110\u2013119."},{"key":"50_CR20","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1016\/0020-0190(95)00099-X","volume":"56","author":"J. Y. T. Leung","year":"1995","unstructured":"J. Y. T. Leung, W. D. Wei: Tighter bounds on a heuristic for a partition problem. Information Processing Letters 56 (1995) 51\u201357.","journal-title":"Information Processing Letters"},{"key":"50_CR21","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"367","DOI":"10.1007\/3-540-69346-7_28","volume-title":"Proceedings of 6th IPCO","author":"A. Munier","year":"1998","unstructured":"A. Munier, M. Queyranne, A. S. Schulz: Approximation bounds for a general class of precedence-constrained parallel machine scheduling problems. In Proceedings of 6th IPCO, LNCS 1412 (1998) 367\u2013382."},{"key":"50_CR22","series-title":"Lect Notes Comput Sci","first-page":"290","volume-title":"Proceedings of 4th WADS","author":"C. Philips","year":"1995","unstructured":"C. Philips, C. Stein, J. Wein: Scheduling job that arrive over time. In Proceedings of 4th WADS, LNCS 955 (1995) 290\u2013301."},{"key":"50_CR23","doi-asserted-by":"crossref","first-page":"78","DOI":"10.1007\/BFb0120909","volume":"13","author":"C.N. Potts","year":"1980","unstructured":"C.N. Potts: An algorithm for the single machine sequencing problem with precedence constraints. Math. Programming Stud. 13 (1980) 78\u201387.","journal-title":"Math. Programming Stud."},{"key":"50_CR24","doi-asserted-by":"publisher","first-page":"263","DOI":"10.1007\/BF01581271","volume":"58","author":"M. Queyranne","year":"1993","unstructured":"M. Queyranne: Structure of a simple scheduling polyhedron. Math. Programming 58 (1993) 263\u2013285.","journal-title":"Math. Programming"},{"key":"50_CR25","unstructured":"M. Queyranne, A. S. Shulz: Polyhedral approaches to machine scheduling. Preprint No. 408\/1994, Department of Mathematics, Technical University Berlin, 1994."},{"key":"50_CR26","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"751","DOI":"10.1007\/3-540-54233-7_180","volume-title":"Proceedings of 18th ICALP","author":"R. Ravi","year":"1991","unstructured":"R. Ravi, A. Agrawal, P. Klein: Ordering problems approximated: single processor scheduling and interval graph completion. In Proceedings of 18th ICALP, LNCS 510 (1991) 751\u2013762."},{"key":"50_CR27","doi-asserted-by":"publisher","first-page":"116","DOI":"10.1145\/321921.321934","volume":"23","author":"S. Sahni","year":"1976","unstructured":"S. Sahni: Algorithms for scheduling independent tasks. J. ACM 23 (1976) 116\u2013127.","journal-title":"J. ACM"},{"key":"50_CR28","unstructured":"M. W. P. Savelsbergh, R. N. Uma, J. M. Wein: An experimental study of LP-based approximation algorithms for scheduling problems. In Proceedings of 9th SODA (1998) 453\u2013462."},{"key":"50_CR29","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"119","DOI":"10.1007\/3-540-63248-4_11","volume-title":"Proceedings of RANDOM\u201997","author":"A.S. Schulz","year":"1997","unstructured":"A.S. Schulz, M. Skutella: Random-based scheduling: New approximations and LP lower bounds. In Proceedings of RANDOM\u201997, LNCS 1269 (1997) 119\u2013133."},{"key":"50_CR30","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"416","DOI":"10.1007\/3-540-63397-9_32","volume-title":"Proceedings of 5th ESA","author":"A.S. Schulz","year":"1997","unstructured":"A.S. Schulz, M. Skutella: Scheduling-LPs bear probabilities: Randomized approximations for min-sum criteria. In Proceedings of 5th ESA, LNCS 1284 (1997) 416\u2013429."},{"key":"50_CR31","unstructured":"A.S. Schulz, M. Skutella: The power of alpha-points in preemptive single machine scheduling. Submitted, 1999 (see http:\/\/www.math.tu-berlin.de\/~skutella\/publications.html )."},{"key":"50_CR32","doi-asserted-by":"crossref","unstructured":"P. Schuurman, G.J. Woeginger: Polynomial time algorithms for machine scheduling: Ten open problems. Manuscript, 1999.","DOI":"10.1002\/(SICI)1099-1425(199909\/10)2:5<203::AID-JOS26>3.3.CO;2-X"},{"key":"50_CR33","unstructured":"J. Sethuraman, M. S. Squillante: Optimal scheduling of multiclass parallel machines. In Proceedings of 10th SODA (1999) 963\u2013964."},{"key":"50_CR34","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"15","DOI":"10.1007\/BFb0053960","volume-title":"Proceedings of APPROX\u201998","author":"D. B. Shmoys","year":"1998","unstructured":"D. B. Shmoys: Using linear programming in the design and analysis of approximation algorithms: Two illustrative problems. In Proceedings of APPROX\u201998, LNCS 1444 (1998) 15\u201332."},{"key":"50_CR35","doi-asserted-by":"crossref","unstructured":"M. Skutella: Semidefinite relaxations for parallel machine scheduling. In Proceedings of 39th FOCS (1998) 472\u2013481.","DOI":"10.1109\/SFCS.1998.743498"},{"key":"50_CR36","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"127","DOI":"10.1007\/3-540-48481-7_12","volume-title":"Proceedings of 7th ESA","author":"M. Skutella","year":"1999","unstructured":"M. Skutella: Convex quadratic programming relaxations for network scheduling problems. In Proceedings of 7th ESA, LNCS 1643 (1999) 127\u2013138."},{"key":"50_CR37","unstructured":"M. Skutella, G.J. Woeginger: A PTAS for minimizing the weigthed sum of job completion times on parallel machines. In Proceedings of 31th STOC (1999) 400\u2013407."},{"key":"50_CR38","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1002\/nav.3800030106","volume":"3","author":"W. Smith","year":"1956","unstructured":"W. Smith: Various optimizers for single-stage production. Naval Res. Logist. Quart. 3(1956) 59\u201366.","journal-title":"Naval Res. Logist. Quart."},{"key":"50_CR39","unstructured":"E. Torng and P. Uthaisombut: Lower bounds for srpt-subsequence algorithms for nonpreemptive scheduling. In Proceedings of the 10th SODA (1999) 973\u2013974."},{"key":"50_CR40","unstructured":"J. Turek, W. Ludwing, J. Wolf, P. Yu: Scheduling parallel tasks to minimize average responce times. In Proceedings of 5th SODA (1994) 112\u2013121."},{"key":"50_CR41","unstructured":"G.J. Woeginger: When does a dynamic programming formulation guarantee the existence of an FPTAS? In Proceedings of 10th SODA (1999) 820\u2013829."},{"key":"50_CR42","volume-title":"Invited talk at 12th International Symposium on Mathematical Programming","author":"L. A. Wosley","year":"1985","unstructured":"L. A. Wosley: Mixed integer programming formulations for production planning and scheduling problems. Invited talk at 12th International Symposium on Mathematical Programming, MIT, Cambriddge, 1985."},{"key":"50_CR43","unstructured":"R. N. Uma and J. Wein: On the relationship between combinatorial and lp-based approaches to NP-hard scheduling problems. In Proceedings of the 7th IPCO (1999) 394\u2013408."}],"container-title":["Lecture Notes in Computer Science","Fundamentals of Computation Theory"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-44669-9_50","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,1]],"date-time":"2019-05-01T22:13:06Z","timestamp":1556748786000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-44669-9_50"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2001]]},"ISBN":["9783540424871","9783540446699"],"references-count":43,"URL":"https:\/\/doi.org\/10.1007\/3-540-44669-9_50","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2001]]}}}