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|
|Number of pages||13|
|ISBN (Print)||0897911105, 9780897911108|
|State||Published - 1983|
All Science Journal Classification (ASJC) codes