{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,8]],"date-time":"2025-12-08T22:01:37Z","timestamp":1765231297956,"version":"3.37.3"},"reference-count":21,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2023,3,30]],"date-time":"2023-03-30T00:00:00Z","timestamp":1680134400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2023,3,30]],"date-time":"2023-03-30T00:00:00Z","timestamp":1680134400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"DOI":"10.13039\/100000001","name":"national science foundation","doi-asserted-by":"publisher","award":["CCF-1749864"],"award-info":[{"award-number":["CCF-1749864"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100004344","name":"adobe systems","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100004344","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100006785","name":"google","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100006785","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Sched"],"published-print":{"date-parts":[[2024,8]]},"DOI":"10.1007\/s10951-023-00780-y","type":"journal-article","created":{"date-parts":[[2023,3,30]],"date-time":"2023-03-30T07:03:06Z","timestamp":1680159786000},"page":"319-328","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Approximating weighted completion time via stronger negative correlation"],"prefix":"10.1007","volume":"27","author":[{"given":"Alok","family":"Baveja","sequence":"first","affiliation":[]},{"given":"Xiaoran","family":"Qu","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0062-3684","authenticated-orcid":false,"given":"Aravind","family":"Srinivasan","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2023,3,30]]},"reference":[{"key":"780_CR1","unstructured":"Afrati, F.N., Bampis, E., Chekuri, C., Karger, D.R., Kenyon, C., Khanna, S., Milis, I., Queyranne, M., Skutella, M., Stein, C., & Sviridenko, M. (1999). Approximation schemes for minimizing average weighted completion time with release dates (pp. 32\u201344). FOCS: In Foundations of Computer Science."},{"issue":"3","key":"780_CR2","doi-asserted-by":"publisher","first-page":"307","DOI":"10.1023\/B:JOCO.0000038913.96607.c2","volume":"8","author":"AA Ageev","year":"2004","unstructured":"Ageev, A. A., & Sviridenko, M. (2004). Pipage rounding: A new method of constructing algorithms with proven performance guarantee. Journal of Combinatorial Optimization, 8(3), 307\u2013328.","journal-title":"Journal of Combinatorial Optimization"},{"key":"780_CR3","doi-asserted-by":"crossref","unstructured":"Anil Kumar, V. S., Marathe, M. V., Parthasarathy, S., & Srinivasan, A. (2009). A unified approach to scheduling on unrelated parallel machines. Journal of the ACM (JACM), 56(5), 28:1-28:31.","DOI":"10.1145\/1552285.1552289"},{"key":"780_CR4","doi-asserted-by":"crossref","unstructured":"Bansal, N. (2019). On a generalization of iterated and randomized rounding. In M. Charikar and E. Cohen (Eds.), Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, Phoenix, AZ, USA, June 23\u201326, 2019, (pp. 1125\u20131135). ACM.","DOI":"10.1145\/3313276.3316313"},{"key":"780_CR5","doi-asserted-by":"crossref","unstructured":"Bansal, N., Aravind, S., & Ola, S. (2021). Lift-and-round to improve weighted completion time on unrelated machines. In SIAM Journal on Computing, 50(3):STOC16\u2013138\u2013STOC16\u2013159, 2021. https:\/\/doi.org\/10.1137\/16M1099583. Conference version: Proc. ACM Symposium on Theory of Computing, (pp. 156\u2013167). 2016","DOI":"10.1137\/16M1099583"},{"key":"780_CR6","doi-asserted-by":"crossref","unstructured":"Becchetti, L., Leonardi, S., Marchetti-Spaccamela, A., & Pruhs, K. (2016). Flow time minimization. In Encyclopedia of Algorithms, (pp. 766\u2013768).","DOI":"10.1007\/978-1-4939-2864-4_146"},{"key":"780_CR7","doi-asserted-by":"crossref","unstructured":"Chekuri, C., & Khanna, S. (2001). A PTAS for minimizing weighted completion time on uniformly related machines. In F. Orejas, P.\u00a0G. Spirakis, & J. van Leeuwen (Eds.), Automata, Languages and Programming, 28th International Colloquium, ICALP 2001, Crete, Greece, July 8\u201312, 2001, Proceedings, volume 2076 of Lecture Notes in Computer Science, (pp. 848\u2013861). Springer.","DOI":"10.1007\/3-540-48224-5_69"},{"key":"780_CR8","doi-asserted-by":"publisher","first-page":"493","DOI":"10.1214\/aoms\/1177729330","volume":"23","author":"H Chernoff","year":"1952","unstructured":"Chernoff, H. (1952). A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations. Annals of Mathematical Statistics, 23, 493\u2013509.","journal-title":"Annals of Mathematical Statistics"},{"issue":"2","key":"780_CR9","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1287\/ijoc.13.2.157.10520","volume":"13","author":"H Hoogeveen","year":"2001","unstructured":"Hoogeveen, H., Schuurman, P., & Woeginger, G. J. (2001). Non-approximability results for scheduling problems with minsum criteria. INFORMS Journal on Computing, 13(2), 157\u2013168.","journal-title":"INFORMS Journal on Computing"},{"key":"780_CR10","doi-asserted-by":"crossref","unstructured":"Im, S., & Shadloo, M. (2020). Weighted completion time minimization for unrelated machines via iterative fair contention resolution. In S. Chawla (Ed.), Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020, Salt Lake City, UT, USA, Jan 5\u20138, 2020, (pp. 2790\u20132809). SIAM.","DOI":"10.1137\/1.9781611975994.170"},{"key":"780_CR11","doi-asserted-by":"crossref","unstructured":"Li, S. (2020). Scheduling to minimize total weighted completion time via time-indexed linear programming relaxations. SIAM Journal on Computing, 49(4). Published online April 2020.","DOI":"10.1137\/17M1156332"},{"issue":"1","key":"780_CR12","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1109\/JSAC.2015.2452415","volume":"34","author":"Y Li","year":"2016","unstructured":"Li, Y., Jin, D., Hui, P., & Han, Z. (2016). Optimal base station scheduling for device-to-device communication underlaying cellular networks. IEEE Journal on Selected Areas in Communications, 34(1), 27\u201340.","journal-title":"IEEE Journal on Selected Areas in Communications"},{"key":"780_CR13","doi-asserted-by":"crossref","unstructured":"Phillips, C. A., Stein, C., & Wein, J. (1998). Minimizing average completion time in the presence of release dates. Mathematical Programming, 82, 199\u2013223.","DOI":"10.1007\/BF01585872"},{"key":"780_CR14","doi-asserted-by":"crossref","unstructured":"Pruhs, K. (2019). Green computing algorithmics. In B. Steffen & G.\u00a0J. Woeginger (Eds.), Computing and Software Science-State of the Art and Perspectives, volume 10000 of Lecture Notes in Computer Science, (pp. 161\u2013183). Springer.","DOI":"10.1007\/978-3-319-91908-9_10"},{"issue":"4","key":"780_CR15","doi-asserted-by":"publisher","first-page":"680","DOI":"10.1002\/rsa.20756","volume":"52","author":"B Saha","year":"2018","unstructured":"Saha, B., & Srinivasan, A. (2018). A new approximation technique for resource-allocation problems. Random Structures & Algorithms, 52(4), 680\u2013715.","journal-title":"Random Structures & Algorithms"},{"key":"780_CR16","doi-asserted-by":"crossref","unstructured":"Sethuraman, J., & Squillante, M. S. (1999). Optimal scheduling of multiclass parallel machines (pp. 963\u2013964). SODA: In ACM-SIAM Symposium on Discrete Algorithms.","DOI":"10.1145\/301453.301483"},{"key":"780_CR17","doi-asserted-by":"publisher","first-page":"461","DOI":"10.1007\/BF01585178","volume":"62","author":"DB Shmoys","year":"1993","unstructured":"Shmoys, D. B., & Tardos, \u00c9. (1993). An approximation algorithm for the generalized assignment problem. Mathematical Programming, 62, 461\u2013474.","journal-title":"Mathematical Programming"},{"key":"780_CR18","unstructured":"Singh, M. (2016). Personal communication through Nikhil Bansal."},{"issue":"2","key":"780_CR19","doi-asserted-by":"publisher","first-page":"206","DOI":"10.1145\/375827.375840","volume":"48","author":"M Skutella","year":"2001","unstructured":"Skutella, M. (2001). Convex quadratic and semidefinite programming relaxations in scheduling. Journal of the ACM, 48(2), 206\u2013242.","journal-title":"Journal of the ACM"},{"key":"780_CR20","doi-asserted-by":"crossref","unstructured":"Skutella, M., & Woeginger, G. J. (1999). A PTAS for minimizing the weighted sum of job completion times on parallel machines (pp. 400\u2013407). STOC: In Symposium on Theory of Computing.","DOI":"10.1145\/301250.301356"},{"key":"780_CR21","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1002\/nav.3800030106","volume":"3","author":"WE Smith","year":"1956","unstructured":"Smith, W. E. (1956). Various optimizers for single-stage production. Naval Research Logistics, 3, 59\u201366.","journal-title":"Naval Research Logistics"}],"container-title":["Journal of Scheduling"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10951-023-00780-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10951-023-00780-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10951-023-00780-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,8,9]],"date-time":"2024-08-09T13:35:14Z","timestamp":1723210514000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10951-023-00780-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,3,30]]},"references-count":21,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2024,8]]}},"alternative-id":["780"],"URL":"https:\/\/doi.org\/10.1007\/s10951-023-00780-y","relation":{},"ISSN":["1094-6136","1099-1425"],"issn-type":[{"type":"print","value":"1094-6136"},{"type":"electronic","value":"1099-1425"}],"subject":[],"published":{"date-parts":[[2023,3,30]]},"assertion":[{"value":"20 February 2023","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"30 March 2023","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"Not applicable.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}