[{"status":"public","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","extern":"1","type":"conference","date_published":"1999-05-01T00:00:00Z","year":"1999","citation":{"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>.","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.","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."},"date_updated":"2023-02-09T11:47:09Z","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"}],"publication_identifier":{"issn":["0196-6774"]},"day":"01","doi":"10.1145/301250.301300","keyword":["Scheduling","Flow time"],"language":[{"iso":"eng"}],"quality_controlled":"1","page":"189-197","conference":{"end_date":"1999-05-04","location":" Atlanta, GA, United States","name":"STOC: Symposium on Theory of Computing","start_date":"1999-05-01"},"publisher":"Association for Computing Machinery","author":[{"last_name":"Goel","first_name":"Ashish","full_name":"Goel, Ashish"},{"first_name":"Monika H","last_name":"Henzinger","orcid":"0000-0002-5008-6530","full_name":"Henzinger, Monika H","id":"540c9bbd-f2de-11ec-812d-d04a5be85630"},{"last_name":"Plotkin","first_name":"Serge","full_name":"Plotkin, Serge"},{"full_name":"Tardos, Eva","last_name":"Tardos","first_name":"Eva"}],"scopus_import":"1","_id":"11691","publication":"Proceedings of the 31st annual ACM symposium on Theory of computing","title":"Scheduling data transfers in a network and the set scheduling problem","month":"05","article_processing_charge":"No","date_created":"2022-07-29T07:43:00Z","oa_version":"None","publication_status":"published"}]