{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,29]],"date-time":"2025-09-29T08:19:36Z","timestamp":1759133976133},"publisher-location":"Berlin, Heidelberg","reference-count":28,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783662439470"},{"type":"electronic","value":"9783662439487"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-662-43948-7_68","type":"book-chapter","created":{"date-parts":[[2014,6,11]],"date-time":"2014-06-11T12:10:36Z","timestamp":1402488636000},"page":"823-834","source":"Crossref","is-referenced-by-count":6,"title":["Precedence-Constrained Scheduling of Malleable Jobs with Preemption"],"prefix":"10.1007","author":[{"given":"Konstantin","family":"Makarychev","sequence":"first","affiliation":[]},{"given":"Debmalya","family":"Panigrahi","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"68_CR1","doi-asserted-by":"crossref","unstructured":"Bansal, N., Khot, S.: Optimal long code test with one free bit. In: FOCS, pp. 453\u2013462 (2009)","DOI":"10.1109\/FOCS.2009.23"},{"issue":"4","key":"68_CR2","doi-asserted-by":"crossref","first-page":"817","DOI":"10.1007\/s00224-011-9349-0","volume":"49","author":"H.-L. Chan","year":"2011","unstructured":"Chan, H.-L., Edmonds, J., Pruhs, K.: Speed scaling of processes with arbitrary speedup curves on a multiprocessor. Theory Comput. Syst.\u00a049(4), 817\u2013833 (2011)","journal-title":"Theory Comput. Syst."},{"issue":"2","key":"68_CR3","doi-asserted-by":"publisher","first-page":"212","DOI":"10.1006\/jagm.2001.1184","volume":"41","author":"C. Chekuri","year":"2001","unstructured":"Chekuri, C., Bender, M.A.: An efficient approximation algorithm for minimizing makespan on uniformly related machines. J. Algorithms\u00a041(2), 212\u2013224 (2001)","journal-title":"J. Algorithms"},{"key":"68_CR4","first-page":"21","volume":"3","author":"B. Chen","year":"1998","unstructured":"Chen, B., Potts, C.N., Woeginger, G.J.: A review of machine scheduling: Complexity, algorithms and approximability. Handbook of Combinatorial Optimization\u00a03, 21\u2013169 (1998)","journal-title":"Handbook of Combinatorial Optimization"},{"issue":"2","key":"68_CR5","doi-asserted-by":"publisher","first-page":"323","DOI":"10.1006\/jagm.1998.0987","volume":"30","author":"F.A. Chudak","year":"1999","unstructured":"Chudak, F.A., Shmoys, D.B.: Approximation algorithms for precedence-constrained scheduling problems on parallel machines that run at different speeds. J. Algorithms\u00a030(2), 323\u2013343 (1999)","journal-title":"J. Algorithms"},{"issue":"2","key":"68_CR6","doi-asserted-by":"publisher","first-page":"176","DOI":"10.1137\/0402016","volume":"2","author":"J. Du","year":"1989","unstructured":"Du, J., Leung, J.Y.-T.: Scheduling tree-structured tasks on two processors to minimize schedule length. SIAM J. Discrete Math.\u00a02(2), 176\u2013196 (1989)","journal-title":"SIAM J. Discrete Math."},{"key":"68_CR7","unstructured":"Dutot, P.-F., Mounie, G., Trystram, D.: Scheduling parallel tasks approximation algorithms. In: Handbook of Scheduling: Algorithms, Models, and Performance Analysis (2004)"},{"issue":"1","key":"68_CR8","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1016\/S0304-3975(99)00186-3","volume":"235","author":"J. Edmonds","year":"2000","unstructured":"Edmonds, J.: Scheduling in the dark. Theor. Comput. Sci.\u00a0235(1), 109\u2013141 (2000)","journal-title":"Theor. Comput. Sci."},{"issue":"3","key":"68_CR9","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1023\/A:1022952324290","volume":"6","author":"J. Edmonds","year":"2003","unstructured":"Edmonds, J., Chinn, D.D., Brecht, T., Deng, X.: Non-clairvoyant multiprocessor scheduling of jobs with changing execution characteristics. J. Scheduling\u00a06(3), 231\u2013250 (2003)","journal-title":"J. Scheduling"},{"issue":"3","key":"68_CR10","doi-asserted-by":"publisher","first-page":"28","DOI":"10.1145\/2229163.2229172","volume":"8","author":"J. Edmonds","year":"2012","unstructured":"Edmonds, J., Pruhs, K.: Scalably scheduling processes with arbitrary speedup curves. ACM Transactions on Algorithms\u00a08(3), 28 (2012)","journal-title":"ACM Transactions on Algorithms"},{"key":"68_CR11","doi-asserted-by":"crossref","unstructured":"Fox, K., Im, S., Moseley, B.: Energy efficient scheduling of parallelizable jobs. In: SODA, pp. 948\u2013957 (2013)","DOI":"10.1137\/1.9781611973105.68"},{"issue":"7","key":"68_CR12","doi-asserted-by":"publisher","first-page":"1139","DOI":"10.1016\/j.jcss.2008.04.001","volume":"74","author":"D. Gangal","year":"2008","unstructured":"Gangal, D., Ranade, A.G.: Precedence constrained scheduling in (2 - 7\/(3p+1)) optimal. J. Comput. Syst. Sci.\u00a074(7), 1139\u20131146 (2008)","journal-title":"J. Comput. Syst. Sci."},{"key":"68_CR13","doi-asserted-by":"crossref","unstructured":"Graham, R.L.: Bounds for certain multiprocessing anomalies. Siam Journal on Applied Mathematics (1966)","DOI":"10.1002\/j.1538-7305.1966.tb01709.x"},{"issue":"2","key":"68_CR14","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1016\/S0167-5060(08)70356-X","volume":"5","author":"R.L. Graham","year":"1979","unstructured":"Graham, R.L., Lawler, E.L., Lenstra, J.K., Rinnooy Kan, A.H.G.: Optimization and approximation in deterministic sequencing and scheduling: a survey. Annals of Discrete Mathematics\u00a05(2), 287\u2013326 (1979)","journal-title":"Annals of Discrete Mathematics"},{"issue":"3","key":"68_CR15","doi-asserted-by":"publisher","first-page":"743","DOI":"10.1137\/S0097539704444440","volume":"34","author":"Y. Huo","year":"2005","unstructured":"Huo, Y., Leung, J.Y.-T.: Online scheduling of precedence constrained tasks. SIAM J. Comput.\u00a034(3), 743\u2013762 (2005)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"68_CR16","doi-asserted-by":"publisher","first-page":"416","DOI":"10.1145\/1159892.1159899","volume":"2","author":"K. Jansen","year":"2006","unstructured":"Jansen, K., Zhang, H.: An approximation algorithm for scheduling malleable tasks under general precedence constraints. ACM Transactions on Algorithms\u00a02(3), 416\u2013434 (2006)","journal-title":"ACM Transactions on Algorithms"},{"issue":"1","key":"68_CR17","doi-asserted-by":"publisher","first-page":"245","DOI":"10.1016\/j.jcss.2011.04.003","volume":"78","author":"K. Jansen","year":"2012","unstructured":"Jansen, K., Zhang, H.: Scheduling malleable tasks with precedence constraints. J. Comput. Syst. Sci.\u00a078(1), 245\u2013259 (2012)","journal-title":"J. Comput. Syst. Sci."},{"issue":"3","key":"68_CR18","doi-asserted-by":"publisher","first-page":"518","DOI":"10.1137\/0206037","volume":"6","author":"S. Lam","year":"1977","unstructured":"Lam, S., Sethi, R.: Worst case analysis of two scheduling algorithms. SIAM J. Comput.\u00a06(3), 518\u2013536 (1977)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"68_CR19","doi-asserted-by":"publisher","first-page":"22","DOI":"10.1287\/opre.26.1.22","volume":"26","author":"J.K. Lenstra","year":"1978","unstructured":"Lenstra, J.K., Kan, R.A.H.G.: Complexity of Scheduling under Precedence Constraints. Operations Research\u00a026(1), 22\u201335 (1978)","journal-title":"Operations Research"},{"issue":"4","key":"68_CR20","doi-asserted-by":"publisher","first-page":"613","DOI":"10.1142\/S0129054102001308","volume":"13","author":"R. Lep\u00e8re","year":"2002","unstructured":"Lep\u00e8re, R., Trystram, D., Woeginger, G.J.: Approximation algorithms for scheduling malleable tasks under precedence constraints. Int. J. Found. Comput. Sci.\u00a013(4), 613\u2013627 (2002)","journal-title":"Int. J. Found. Comput. Sci."},{"key":"68_CR21","doi-asserted-by":"crossref","unstructured":"Makarychev, K., Panigrahi, D.: Precedence-constrained scheduling of malleable jobs with preemption. CoRR, abs\/1404.6850 (2014)","DOI":"10.1007\/978-3-662-43948-7_68"},{"key":"68_CR22","doi-asserted-by":"crossref","unstructured":"Srinivasa Prasanna, G.N., Musicus, B.R.: Generalised multiprocessor scheduling using optimal control. In: SPAA, pp. 216\u2013228 (1991)","DOI":"10.1145\/113379.113399"},{"key":"68_CR23","doi-asserted-by":"crossref","unstructured":"Srinivasa Prasanna, G.N., Musicus, B.R.: Generalized multiprocessor scheduling for directed acyclic graphs. In: SC, pp. 237\u2013246 (1994)","DOI":"10.1145\/602809.602812"},{"issue":"1","key":"68_CR24","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1007\/BF01942605","volume":"15","author":"G.N. Srinivasa Prasanna","year":"1996","unstructured":"Srinivasa Prasanna, G.N., Musicus, B.R.: The optimal control approach to generalized multiprocessor scheduling. Algorithmica\u00a015(1), 17\u201349 (1996)","journal-title":"Algorithmica"},{"key":"68_CR25","unstructured":"Robert, J., Schabanel, N.: Non-clairvoyant scheduling with precedence constraints. In: SODA, pp. 491\u2013500 (2008)"},{"key":"68_CR26","unstructured":"Skutella, M.: Approximation algorithms for the discrete time-cost tradeoff problem. In: SODA, pp. 501\u2013508 (1997)"},{"issue":"5","key":"68_CR27","doi-asserted-by":"publisher","first-page":"1258","DOI":"10.1137\/100810502","volume":"40","author":"O. Svensson","year":"2011","unstructured":"Svensson, O.: Hardness of precedence constrained scheduling on identical machines. SIAM J. Comput.\u00a040(5), 1258\u20131274 (2011)","journal-title":"SIAM J. Comput."},{"key":"68_CR28","doi-asserted-by":"crossref","unstructured":"Turek, J., Wolf, J.L., Yu, P.S.: Approximate algorithms scheduling parallelizable tasks. In: SPAA, pp. 323\u2013332 (1992)","DOI":"10.1145\/140901.141909"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages, and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-43948-7_68","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,26]],"date-time":"2019-05-26T22:32:27Z","timestamp":1558909947000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-43948-7_68"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783662439470","9783662439487"],"references-count":28,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-43948-7_68","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2014]]}}}