{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,13]],"date-time":"2026-06-13T10:15:39Z","timestamp":1781345739266,"version":"3.54.1"},"reference-count":22,"publisher":"Springer Science and Business Media LLC","issue":"12","license":[{"start":{"date-parts":[[2020,7,15]],"date-time":"2020-07-15T00:00:00Z","timestamp":1594771200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2020,7,15]],"date-time":"2020-07-15T00:00:00Z","timestamp":1594771200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/100000144","name":"Division of Computer and Network Systems","doi-asserted-by":"publisher","award":["156019"],"award-info":[{"award-number":["156019"]}],"id":[{"id":"10.13039\/100000144","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000143","name":"Division of Computing and Communication Foundations","doi-asserted-by":"publisher","award":["1655073 (Eager)"],"award-info":[{"award-number":["1655073 (Eager)"]}],"id":[{"id":"10.13039\/100000143","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100016443","name":"Amazon","doi-asserted-by":"crossref","id":[{"id":"10.13039\/100016443","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2020,12]]},"DOI":"10.1007\/s00453-020-00741-3","type":"journal-article","created":{"date-parts":[[2020,7,15]],"date-time":"2020-07-15T20:03:33Z","timestamp":1594843413000},"page":"3604-3629","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":16,"title":["On Scheduling Coflows"],"prefix":"10.1007","volume":"82","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-1046-9940","authenticated-orcid":false,"given":"Saba","family":"Ahmadi","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Samir","family":"Khuller","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Manish","family":"Purohit","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Sheng","family":"Yang","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2020,7,15]]},"reference":[{"key":"741_CR1","unstructured":"Apache Software Foundation: Hadoop. https:\/\/hadoop.apache.org"},{"key":"741_CR2","doi-asserted-by":"crossref","unstructured":"Bansal, N., Khot, S.: Inapproximability of hypergraph vertex cover and applications to scheduling problems. In: International Colloquium on Automata, Languages and Programming, pp. 250\u2013261. Springer (2010)","DOI":"10.1007\/978-3-642-14165-2_22"},{"issue":"6","key":"741_CR3","doi-asserted-by":"crossref","first-page":"1072","DOI":"10.1287\/opre.1070.0412","volume":"55","author":"ZL Chen","year":"2007","unstructured":"Chen, Z.L., Hall, N.G.: Supply chain scheduling: conflict and cooperation in assembly systems. Oper. Res. 55(6), 1072\u20131089 (2007)","journal-title":"Oper. Res."},{"key":"741_CR4","doi-asserted-by":"crossref","unstructured":"Chowdhury, M., Stoica, I.: Coflow: A networking abstraction for cluster applications. In: ACM Workshop on Hot Topics in Networks, pp. 31\u201336. ACM (2012)","DOI":"10.1145\/2390231.2390237"},{"key":"741_CR5","doi-asserted-by":"crossref","unstructured":"Chowdhury, M., Stoica, I.: Efficient coflow scheduling without prior knowledge. In: SIGCOMM, pp. 393\u2013406. ACM (2015)","DOI":"10.1145\/2829988.2787480"},{"key":"741_CR6","doi-asserted-by":"crossref","unstructured":"Chowdhury, M., Zhong, Y., Stoica, I.: Efficient coflow scheduling with varys. In: SIGCOMM, SIGCOMM \u201914, pp. 443\u2013454. ACM, New York, NY, USA (2014)","DOI":"10.1145\/2740070.2626315"},{"issue":"2","key":"741_CR7","doi-asserted-by":"crossref","first-page":"121","DOI":"10.1016\/j.orl.2012.12.001","volume":"41","author":"JM Davis","year":"2013","unstructured":"Davis, J.M., Gandhi, R., Kothari, V.H.: Combinatorial algorithms for minimizing the weighted sum of completion times on a single machine. Oper. Res. Lett. 41(2), 121\u2013125 (2013)","journal-title":"Oper. Res. Lett."},{"issue":"1","key":"741_CR8","doi-asserted-by":"crossref","first-page":"107","DOI":"10.1145\/1327452.1327492","volume":"51","author":"J Dean","year":"2008","unstructured":"Dean, J., Ghemawat, S.: Mapreduce: simplified data processing on large clusters. Commun. ACM 51(1), 107\u2013113 (2008)","journal-title":"Commun. ACM"},{"key":"741_CR9","doi-asserted-by":"crossref","unstructured":"Garg, N., Kumar, A., Pandit, V.: Order scheduling models: Hardness and algorithms. In: FSTTCS, pp. 96\u2013107. Springer (2007)","DOI":"10.1007\/978-3-540-77050-3_8"},{"key":"741_CR10","unstructured":"Im, S., Moseley, B., Pruhs, K., Purohit, M.: Matroid coflow scheduling. In: International Colloquium on Automata, Languages and Programming (2019)"},{"key":"741_CR11","doi-asserted-by":"crossref","first-page":"420","DOI":"10.1016\/j.tcs.2019.07.026","volume":"795","author":"S Khuller","year":"2019","unstructured":"Khuller, S., Li, J., Sturmfels, P., Sun, K., Venkat, P.: Select and permute: an improved online framework for scheduling to minimize weighted completion time. Theor. Comput. Sci. 795, 420\u2013431 (2019)","journal-title":"Theor. Comput. Sci."},{"key":"741_CR12","doi-asserted-by":"crossref","unstructured":"Khuller, S., Purohit, M.: Brief announcement: Improved approximation algorithms for scheduling co-flows. In: Proceedings of the 28th ACM Symposium on Parallelism in Algorithms and Architectures, pp. 239\u2013240. ACM, New York, NY, USA (2016)","DOI":"10.1145\/2935764.2935809"},{"issue":"8","key":"741_CR13","doi-asserted-by":"crossref","first-page":"945","DOI":"10.1016\/j.dam.2006.09.012","volume":"155","author":"JYT Leung","year":"2007","unstructured":"Leung, J.Y.T., Li, H., Pinedo, M.: Scheduling orders for multiple product types to minimize total weighted completion time. Discrete Appl. Math. 155(8), 945\u2013970 (2007)","journal-title":"Discrete Appl. Math."},{"issue":"11","key":"741_CR14","doi-asserted-by":"crossref","first-page":"3366","DOI":"10.1109\/TPDS.2016.2525767","volume":"27","author":"S Luo","year":"2016","unstructured":"Luo, S., Yu, H., Zhao, Y., Wang, S., Yu, S., Li, L.: Towards practical and near-optimal coflow scheduling for data center networks. IEEE Trans. Parallel Distrib. Syst. 27(11), 3366\u20133380 (2016)","journal-title":"IEEE Trans. Parallel Distrib. Syst."},{"issue":"5","key":"741_CR15","doi-asserted-by":"crossref","first-page":"390","DOI":"10.1016\/j.orl.2010.04.011","volume":"38","author":"M Mastrolilli","year":"2010","unstructured":"Mastrolilli, M., Queyranne, M., Schulz, A.S., Svensson, O., Uhan, N.A.: Minimizing the sum of weighted completion times in a concurrent open shop. Oper. Res. Lett. 38(5), 390\u2013395 (2010)","journal-title":"Oper. Res. Lett."},{"key":"741_CR16","doi-asserted-by":"crossref","unstructured":"Qiu, Z., Stein, C., Zhong, Y.: Minimizing the total weighted completion time of coflows in datacenter networks. In: ACM Symposium on Parallelism in Algorithms and Architectures, pp. 294\u2013303. ACM, New York, NY, USA (2015)","DOI":"10.1145\/2755573.2755592"},{"issue":"1\u20133","key":"741_CR17","doi-asserted-by":"crossref","first-page":"263","DOI":"10.1007\/BF01581271","volume":"58","author":"M Queyranne","year":"1993","unstructured":"Queyranne, M.: Structure of a simple scheduling polyhedron. Math. Program. 58(1\u20133), 263\u2013285 (1993)","journal-title":"Math. Program."},{"key":"741_CR18","doi-asserted-by":"crossref","unstructured":"Sachdeva, S., Saket, R.: Optimal inapproximability for scheduling problems via structural hardness for hypergraph vertex cover. In: IEEE Conference on Computational Complexity, pp. 219\u2013229. IEEE (2013)","DOI":"10.1109\/CCC.2013.30"},{"issue":"4","key":"741_CR19","doi-asserted-by":"crossref","first-page":"1674","DOI":"10.1109\/TNET.2018.2845852","volume":"26","author":"M Shafiee","year":"2018","unstructured":"Shafiee, M., Ghaderi, J.: An improved bound for minimizing the total weighted completion time of coflows in datacenters. IEEE\/ACM Trans. Netw. 26(4), 1674\u20131687 (2018)","journal-title":"IEEE\/ACM Trans. Netw."},{"issue":"5","key":"741_CR20","doi-asserted-by":"crossref","first-page":"623","DOI":"10.1016\/j.omega.2005.09.007","volume":"35","author":"G Wang","year":"2007","unstructured":"Wang, G., Cheng, T.E.: Customer order scheduling to minimize total weighted completion time. Omega 35(5), 623\u2013626 (2007)","journal-title":"Omega"},{"key":"741_CR21","first-page":"10","volume":"10","author":"M Zaharia","year":"2010","unstructured":"Zaharia, M., Chowdhury, M., Franklin, M.J., Shenker, S., Stoica, I.: Spark: cluster computing with working sets. HotCloud 10, 10\u201310 (2010)","journal-title":"HotCloud"},{"key":"741_CR22","doi-asserted-by":"crossref","unstructured":"Zhao, Y., Chen, K., Bai, W., Yu, M., Tian, C., Geng, Y., Zhang, Y., Li, D., Wang, S.: Rapier: Integrating routing and scheduling for coflow-aware data center networks. In: IEEE International Conference on Computer Communications, pp. 424\u2013432. IEEE (2015)","DOI":"10.1109\/INFOCOM.2015.7218408"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-020-00741-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-020-00741-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-020-00741-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,7,14]],"date-time":"2021-07-14T23:58:56Z","timestamp":1626307136000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-020-00741-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,7,15]]},"references-count":22,"journal-issue":{"issue":"12","published-print":{"date-parts":[[2020,12]]}},"alternative-id":["741"],"URL":"https:\/\/doi.org\/10.1007\/s00453-020-00741-3","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,7,15]]},"assertion":[{"value":"5 October 2017","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"18 June 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"15 July 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}