Coffman, E. G. jun.; Garey, M. R.; Johnson, D. S.; Lapaugh, A. S. Scheduling file transfers. (English) Zbl 0604.68039 SIAM J. Comput. 14, 744-780 (1985). 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. Cited in 4 ReviewsCited in 37 Documents 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 Keywords:edge coloring; protocols; NP-completeness; distributed processing; approximation algorithms; central controller PDFBibTeX XMLCite \textit{E. G. Coffman jun.} et al., SIAM J. Comput. 14, 744--780 (1985; Zbl 0604.68039) Full Text: DOI