The topology aware file distribution problem

Shawn T. O’Neil (), Amitabh Chaudhary (), Danny Z. Chen () and Haitao Wang ()
Additional contact information
Shawn T. O’Neil: University of Notre Dame
Amitabh Chaudhary: University of Notre Dame
Danny Z. Chen: University of Notre Dame
Haitao Wang: University of Notre Dame

Journal of Combinatorial Optimization, 2013, vol. 26, issue 4, No 1, 635 pages

Abstract: Abstract We present theoretical results for large-file distribution on general networks of known topology (known link bandwidths and router locations). We show that the problem of distributing a file in minimum time is NP-hard in this model, and we give an O(logn) approximation algorithm, where n is the number of workstations that require the file. We also characterize our method as optimal amongst the class of “no-link-sharing” algorithms.

Keywords: Network; File distribution; Approximation (search for similar items in EconPapers)
Date: 2013
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-011-9430-2 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:26:y:2013:i:4:d:10.1007_s10878-011-9430-2

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-011-9430-2

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().