Scheduling data transfers in a network and the set scheduling problem
Goel A, Henzinger MH, Plotkin S, Tardos E. 2003. Scheduling data transfers in a network and the set scheduling problem. Journal of Algorithms. 48(2), 314–332.
Download
No fulltext has been uploaded. References only!
Journal Article
| Published
| English
Scopus indexed
Author
Goel, Ashish;
Henzinger, MonikaISTA ;
Plotkin, Serge;
Tardos, Eva
Abstract
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.
Publishing Year
Date Published
2003-09-01
Journal Title
Journal of Algorithms
Volume
48
Issue
2
Page
314-332
ISSN
IST-REx-ID
Cite this
Goel A, Henzinger MH, Plotkin S, Tardos E. Scheduling data transfers in a network and the set scheduling problem. Journal of Algorithms. 2003;48(2):314-332. doi:10.1016/s0196-6774(03)00054-3
Goel, A., Henzinger, M. H., Plotkin, S., & Tardos, E. (2003). Scheduling data transfers in a network and the set scheduling problem. Journal of Algorithms. Elsevier. https://doi.org/10.1016/s0196-6774(03)00054-3
Goel, Ashish, Monika H Henzinger, Serge Plotkin, and Eva Tardos. “Scheduling Data Transfers in a Network and the Set Scheduling Problem.” Journal of Algorithms. Elsevier, 2003. https://doi.org/10.1016/s0196-6774(03)00054-3.
A. Goel, M. H. Henzinger, S. Plotkin, and E. Tardos, “Scheduling data transfers in a network and the set scheduling problem,” Journal of Algorithms, vol. 48, no. 2. Elsevier, pp. 314–332, 2003.
Goel A, Henzinger MH, Plotkin S, Tardos E. 2003. Scheduling data transfers in a network and the set scheduling problem. Journal of Algorithms. 48(2), 314–332.
Goel, Ashish, et al. “Scheduling Data Transfers in a Network and the Set Scheduling Problem.” Journal of Algorithms, vol. 48, no. 2, Elsevier, 2003, pp. 314–32, doi:10.1016/s0196-6774(03)00054-3.