SCHEDULING FILE TRANSFERS IN A DISTRIBUTED NETWORK.

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

doi:10.1145/800221.806726

SCHEDULING FILE TRANSFERS IN A DISTRIBUTED NETWORK.

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

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

19 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 language	English (US)
Title of host publication	Unknown Host Publication Title
Publisher	ACM
Pages	254-266
Number of pages	13
ISBN (Print)	0897911105, 9780897911108
DOIs	https://doi.org/10.1145/800221.806726
State	Published - 1983

All Science Journal Classification (ASJC) codes

General Engineering

Access to Document

10.1145/800221.806726

Cite this

@inproceedings{0663bd5728e64bb9bce9708e68ee8753,

title = "SCHEDULING FILE TRANSFERS IN A DISTRIBUTED NETWORK.",

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.",

author = "Coffman, {E. G.} and Garey, {M. R.} and Johnson, {D. S.} and LaPaugh, {A. S.}",

year = "1983",

doi = "10.1145/800221.806726",

language = "English (US)",

isbn = "0897911105",

publisher = "ACM",

pages = "254--266",

booktitle = "Unknown Host Publication Title",

}

TY - GEN

T1 - SCHEDULING FILE TRANSFERS IN A DISTRIBUTED NETWORK.

AU - Coffman, E. G.

AU - Garey, M. R.

AU - Johnson, D. S.

AU - LaPaugh, A. S.

PY - 1983

Y1 - 1983

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=0020977522&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0020977522&partnerID=8YFLogxK

U2 - 10.1145/800221.806726

DO - 10.1145/800221.806726

M3 - Conference contribution

AN - SCOPUS:0020977522

SN - 0897911105

SN - 9780897911108

SP - 254

EP - 266

BT - Unknown Host Publication Title

PB - ACM

ER -

SCHEDULING FILE TRANSFERS IN A DISTRIBUTED NETWORK.

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this