@inproceedings{11691,
  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.},
  author       = {Goel, Ashish and Henzinger, Monika H and Plotkin, Serge and Tardos, Eva},
  booktitle    = {Proceedings of the 31st annual ACM symposium on Theory of computing},
  issn         = {0196-6774},
  keywords     = {Scheduling, Flow time},
  location     = { Atlanta, GA, United States},
  pages        = {189--197},
  publisher    = {Association for Computing Machinery},
  title        = {{Scheduling data transfers in a network and the set scheduling problem}},
  doi          = {10.1145/301250.301300},
  year         = {1999},
}