[{"_id":"11691","publication":"Proceedings of the 31st annual ACM symposium on Theory of computing","scopus_import":"1","author":[{"full_name":"Goel, Ashish","last_name":"Goel","first_name":"Ashish"},{"orcid":"0000-0002-5008-6530","full_name":"Henzinger, Monika H","first_name":"Monika H","last_name":"Henzinger","id":"540c9bbd-f2de-11ec-812d-d04a5be85630"},{"full_name":"Plotkin, Serge","last_name":"Plotkin","first_name":"Serge"},{"full_name":"Tardos, Eva","first_name":"Eva","last_name":"Tardos"}],"oa_version":"None","publication_status":"published","date_created":"2022-07-29T07:43:00Z","article_processing_charge":"No","title":"Scheduling data transfers in a network and the set scheduling problem","month":"05","page":"189-197","quality_controlled":"1","language":[{"iso":"eng"}],"keyword":["Scheduling","Flow time"],"publisher":"Association for Computing Machinery","conference":{"name":"STOC: Symposium on Theory of Computing","start_date":"1999-05-01","location":" Atlanta, GA, United States","end_date":"1999-05-04"},"date_updated":"2023-02-09T11:47:09Z","citation":{"short":"A. Goel, M.H. Henzinger, S. Plotkin, E. Tardos, in:, Proceedings of the 31st Annual ACM Symposium on Theory of Computing, Association for Computing Machinery, 1999, pp. 189–197.","mla":"Goel, Ashish, et al. “Scheduling Data Transfers in a Network and the Set Scheduling Problem.” <i>Proceedings of the 31st Annual ACM Symposium on Theory of Computing</i>, Association for Computing Machinery, 1999, pp. 189–97, doi:<a href=\"https://doi.org/10.1145/301250.301300\">10.1145/301250.301300</a>.","ista":"Goel A, Henzinger MH, Plotkin S, Tardos E. 1999. Scheduling data transfers in a network and the set scheduling problem. Proceedings of the 31st annual ACM symposium on Theory of computing. STOC: Symposium on Theory of Computing, 189–197.","ama":"Goel A, Henzinger MH, Plotkin S, Tardos E. Scheduling data transfers in a network and the set scheduling problem. In: <i>Proceedings of the 31st Annual ACM Symposium on Theory of Computing</i>. Association for Computing Machinery; 1999:189-197. doi:<a href=\"https://doi.org/10.1145/301250.301300\">10.1145/301250.301300</a>","apa":"Goel, A., Henzinger, M. H., Plotkin, S., &#38; Tardos, E. (1999). Scheduling data transfers in a network and the set scheduling problem. In <i>Proceedings of the 31st annual ACM symposium on Theory of computing</i> (pp. 189–197).  Atlanta, GA, United States: Association for Computing Machinery. <a href=\"https://doi.org/10.1145/301250.301300\">https://doi.org/10.1145/301250.301300</a>","chicago":"Goel, Ashish, Monika H Henzinger, Serge Plotkin, and Eva Tardos. “Scheduling Data Transfers in a Network and the Set Scheduling Problem.” In <i>Proceedings of the 31st Annual ACM Symposium on Theory of Computing</i>, 189–97. Association for Computing Machinery, 1999. <a href=\"https://doi.org/10.1145/301250.301300\">https://doi.org/10.1145/301250.301300</a>.","ieee":"A. Goel, M. H. Henzinger, S. Plotkin, and E. Tardos, “Scheduling data transfers in a network and the set scheduling problem,” in <i>Proceedings of the 31st annual ACM symposium on Theory of computing</i>,  Atlanta, GA, United States, 1999, pp. 189–197."},"year":"1999","date_published":"1999-05-01T00:00:00Z","type":"conference","doi":"10.1145/301250.301300","day":"01","publication_identifier":{"issn":["0196-6774"]},"abstract":[{"text":"In this paper we consider the online ftp problem. The goal is to service a sequence of file transfer requests given bandwidth constraints of the underlying communication network. The main result of the paper is a technique that leads to algorithms that optimize several natural metrics, such as max-stretch, total flow time, max flow time, and total completion time. In particular, we show how to achieve optimum total flow time and optimum max-stretch if we increase the capacity of the underlying network by a logarithmic factor. We show that the resource augmentation is necessary by proving polynomial lower bounds on the max-stretch and total flow time for the case where online and offline algorithms are using same-capacity edges. Moreover, we also give polylogarithmic lower bounds on the resource augmentation factor necessary in order to keep the total flow time and max-stretch within a constant factor of optimum.","lang":"eng"}],"extern":"1","status":"public","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87"}]