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