Scheduling File Transfers
E. G. Coffman, Michael R. Garey, David S. Johnson, Andrea S. LaPaugh · SIAM Journal on Computing · 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.