×

Scheduling file transfers. (English) Zbl 0604.68039

We consider a problem of scheduling file transfers in a network so as to minimize overall finishing time. Although the general problem is NP- complete, we identify polynomial time solvable special cases and derive good performance bounds for several natural approximation algorithms, assuming the existence of a central controller. We also show how these bounds can be maintained in a distributed regime.

MSC:

68M20 Performance evaluation, queueing, and scheduling in the context of computer systems
68Q25 Analysis of algorithms and problem complexity
68R10 Graph theory (including graph drawing) in computer science
PDFBibTeX XMLCite
Full Text: DOI