SCHEDULING FILE TRANSFERS IN A DISTRIBUTED NETWORK.

E. G. Coffman, M. R. Garey, D. S. Johnson, A. S. LaPaugh

Research output: Chapter in Book/Report/Conference proceedingConference contribution

17 Scopus citations

Abstract

We consider a problem of scheduling file transfers in a network so as to minimize overall finishing time, which we formalize as a problem of scheduling the edges of a weighted multigraph. Although the general problem is NP-complete, we identify polynomial time solvable special cases and derive good performance bounds for several natural approximation algorithms. The above results assume the existence of a central controller, but we also show how the approximation algorithms, along with their performance guarantees, can be adapted to a distributed regime.

Original languageEnglish (US)
Title of host publicationUnknown Host Publication Title
PublisherACM
Pages254-266
Number of pages13
ISBN (Print)0897911105, 9780897911108
DOIs
StatePublished - Jan 1 1983

All Science Journal Classification (ASJC) codes

  • Engineering(all)

Fingerprint Dive into the research topics of 'SCHEDULING FILE TRANSFERS IN A DISTRIBUTED NETWORK.'. Together they form a unique fingerprint.

Cite this