{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,7]],"date-time":"2026-07-07T04:12:07Z","timestamp":1783397527421,"version":"3.54.6"},"reference-count":23,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2007,9,15]],"date-time":"2007-09-15T00:00:00Z","timestamp":1189814400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2009,9]]},"DOI":"10.1007\/s00453-007-9004-y","type":"journal-article","created":{"date-parts":[[2007,9,14]],"date-time":"2007-09-14T16:07:55Z","timestamp":1189786075000},"page":"205-226","source":"Crossref","is-referenced-by-count":15,"title":["Scheduling on Unrelated Machines under Tree-Like Precedence Constraints"],"prefix":"10.1007","volume":"55","author":[{"given":"V. S.","family":"Anil Kumar","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Madhav V.","family":"Marathe","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Srinivasan","family":"Parthasarathy","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Aravind","family":"Srinivasan","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2007,9,15]]},"reference":[{"issue":"3","key":"9004_CR1","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1016\/S0167-6377(99)00010-3","volume":"24","author":"D. Bertsimas","year":"1999","unstructured":"Bertsimas, D., Teo, C.-P., Vohra, R.: On dependent randomized rounding algorithms. Oper. Res. Lett. 24(3), 105\u2013114 (1999)","journal-title":"Oper. Res. Lett."},{"key":"9004_CR2","doi-asserted-by":"crossref","first-page":"212","DOI":"10.1006\/jagm.2001.1184","volume":"41","author":"C. Chekuri","year":"2001","unstructured":"Chekuri, C., Bender, M.: An efficient approximation algorithm for minimizing makespan on uniformly related machines. J.\u00a0Algorithms 41, 212\u2013224 (2001)","journal-title":"J.\u00a0Algorithms"},{"key":"9004_CR3","unstructured":"Chekuri, C., Khanna, S.: Approximation algorithms for minimizing average weighted completion time. In: Leung, J. (ed.) Handbook of Scheduling: Algorithms, Models, and Performance Analysis, pp.\u00a011-1\u201311-30. CRC Press (2004)"},{"key":"9004_CR4","doi-asserted-by":"crossref","unstructured":"Chekuri, C., Goel, A., Khanna, S., Kumar, A.: Multi-processor scheduling to minimize flow time with \u03b5 resource augmentation. In: STOC \u201904: Proceedings of the Thirty-Sixth Annual ACM Symposium on Theory of Computing, pp.\u00a0363\u2013372 (2004)","DOI":"10.1145\/1007352.1007411"},{"issue":"2","key":"9004_CR5","doi-asserted-by":"crossref","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.\u00a0Algorithms 30(2), 323\u2013343 (1999)","journal-title":"J.\u00a0Algorithms"},{"key":"9004_CR6","doi-asserted-by":"crossref","first-page":"361","DOI":"10.1007\/s004930200018","volume":"22","author":"U. Feige","year":"2002","unstructured":"Feige, U., Scheideler, C.: Improved bounds for acyclic job shop scheduling. Combinatorica 22, 361\u2013399 (2002)","journal-title":"Combinatorica"},{"key":"9004_CR7","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1137\/S0895480199326104","volume":"14","author":"L.A. Goldberg","year":"2001","unstructured":"Goldberg, L.A., Paterson, M., Srinivasan, A., Sweedyk, E.: Better approximation guarantees for job-shop scheduling. SIAM J. Discret. Math. 14, 67\u201392 (2001)","journal-title":"SIAM J. Discret. Math."},{"key":"9004_CR8","unstructured":"Hall, L.: Approximation algorithms for scheduling. In: Hochbaum, D.S. (ed.) Approximation Algorithms for NP-Hard Problems. PWS Press (1997)"},{"key":"9004_CR9","doi-asserted-by":"crossref","first-page":"513","DOI":"10.1287\/moor.22.3.513","volume":"22","author":"L. Hall","year":"1997","unstructured":"Hall, L., Schulz, A., Shmoys, D.B., Wein, J.: Scheduling to minimize average completion time: offline and online algorithms. Math. Oper. Res. 22, 513\u2013544 (1997)","journal-title":"Math. Oper. Res."},{"key":"9004_CR10","doi-asserted-by":"crossref","unstructured":"Jansen, K., Porkolab, L.: Improved approximation schemes for scheduling unrelated parallel machines. In: Proc. ACM Symposium on Theory of Computing (STOC), pp. 408\u2013417 (1999)","DOI":"10.1145\/301250.301361"},{"key":"9004_CR11","doi-asserted-by":"crossref","unstructured":"Jansen, K., Solis-Oba, R.: Scheduling jobs with chain precedence constraints. In: Parallel Processing and Applied Mathematics, PPAM. Lecture Notes in Computer Science, vol.\u00a03019, pp. 105\u2013112 (2003)","DOI":"10.1007\/978-3-540-24669-5_14"},{"key":"9004_CR12","doi-asserted-by":"crossref","unstructured":"Jansen, K., Solis-Oba, R., Sviridenko, M.: Makespan minimization in job shops: a polynomial time approximation scheme. In: Proc. ACM Symposium on Theory of Computing (STOC), pp. 394\u2013399 (1999)","DOI":"10.1145\/301250.301351"},{"key":"9004_CR13","doi-asserted-by":"crossref","first-page":"167","DOI":"10.1007\/BF01215349","volume":"14","author":"F.T. Leighton","year":"1994","unstructured":"Leighton, F.T., Maggs, B., Rao, S.: Packet routing and jobshop scheduling in O(congestion + dilation) steps. Combinatorica 14, 167\u2013186 (1994)","journal-title":"Combinatorica"},{"key":"9004_CR14","doi-asserted-by":"crossref","first-page":"375","DOI":"10.1007\/s004930050061","volume":"19","author":"F.T. Leighton","year":"1999","unstructured":"Leighton, F.T., Maggs, B., Richa, A.: Fast algorithms for finding O(congestion + dilation) packet routing schedules. Combinatorica 19, 375\u2013401 (1999)","journal-title":"Combinatorica"},{"key":"9004_CR15","doi-asserted-by":"crossref","first-page":"259","DOI":"10.1007\/BF01585745","volume":"46","author":"J.K. Lenstra","year":"1990","unstructured":"Lenstra, J.K., Shmoys, D.B., Tardos, \u00c9.: Approximation algorithms for scheduling unrelated parallel machines. Math.\u00a0Program. 46, 259\u2013271 (1990)","journal-title":"Math.\u00a0Program."},{"key":"9004_CR16","doi-asserted-by":"crossref","unstructured":"Leonardi, S., Raz, D.: Approximating total flow time on parallel machines. In: Proc. ACM Symposium on Theory of Computing, pp.\u00a0110\u2013119 (1997)","DOI":"10.1145\/258533.258562"},{"key":"9004_CR17","doi-asserted-by":"crossref","unstructured":"Lin, J.H., Vitter, J.S.: \u03b5-approximations with minimum packing constraint violation. In: Proceedings of the ACM Symposium on Theory of Computing, pp.\u00a0771\u2013782 (1992)","DOI":"10.1145\/129712.129787"},{"key":"9004_CR18","doi-asserted-by":"crossref","unstructured":"Linial, N., Magen, A., Saks, M.E.: Trees and Euclidean metrics. In: Proceedings of the ACM Symposium on Theory of Computing, pp.\u00a0169\u2013175 (1998)","DOI":"10.1145\/276698.276726"},{"key":"9004_CR19","doi-asserted-by":"crossref","first-page":"350","DOI":"10.1137\/S0097539793250767","volume":"26","author":"A. Panconesi","year":"1997","unstructured":"Panconesi, A., Srinivasan, A.: Randomized distributed edge coloring via an extension of the Chernoff-Hoeffding bounds. SIAM J. Comput. 26, 350\u2013368 (1997)","journal-title":"SIAM J. Comput."},{"key":"9004_CR20","doi-asserted-by":"crossref","first-page":"287","DOI":"10.1002\/jos.96","volume":"5","author":"M. Queyranne","year":"2002","unstructured":"Queyranne, M., Sviridenko, M.: Approximation algorithms for shop scheduling problems with minsum objective. J.\u00a0Sched. 5, 287\u2013305 (2002)","journal-title":"J.\u00a0Sched."},{"issue":"2","key":"9004_CR21","doi-asserted-by":"crossref","first-page":"121","DOI":"10.1002\/jos.93","volume":"5","author":"A. Schulz","year":"2002","unstructured":"Schulz, A., Skutella, M.: The power of \u03b1-points in preemptive single machine scheduling. J. Sched. 5(2), 121\u2013133 (2002)","journal-title":"J. Sched."},{"key":"9004_CR22","doi-asserted-by":"crossref","first-page":"617","DOI":"10.1137\/S009753979222676X","volume":"23","author":"D.B. Shmoys","year":"1994","unstructured":"Shmoys, D.B., Stein, C., Wein, J.: Improved approximation algorithms for shop scheduling problems. SIAM J. Comput. 23, 617\u2013632 (1994)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"9004_CR23","first-page":"206","volume":"46","author":"M. Skutella","year":"2001","unstructured":"Skutella, M.: Convex quadratic and semidefinite relaxations in scheduling. J.\u00a0ACM 46(2), 206\u2013242 (2001)","journal-title":"J.\u00a0ACM"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-007-9004-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-007-9004-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-007-9004-y","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T13:44:59Z","timestamp":1559137499000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-007-9004-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,9,15]]},"references-count":23,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2009,9]]}},"alternative-id":["9004"],"URL":"https:\/\/doi.org\/10.1007\/s00453-007-9004-y","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2007,9,15]]}}}