Skip to Main content Skip to Navigation
Conference papers

Decentralized Approximation Algorithm for Data Placement Problem in Content Delivery Networks

Abstract : Recent advancements in Internet technology research, as well as the widespread of commercial content delivery networks, motivates the need for optimization algorithms designed to work in decentralized manner. In this paper we formulate data placement problem, a special case of universal facility location problem with quadratic terms in objective function. The considered combinatorial optimization problem is NP-hard. A randomized algorithm is presented that approximates the solution within factor O(log n) in decentralized environment, assuming asynchronous message passing of bounded sizes.
Document type :
Conference papers
Complete list of metadata

Cited literature [12 references]  Display  Hide  Download

https://hal.inria.fr/hal-01365572
Contributor : Hal Ifip <>
Submitted on : Tuesday, September 13, 2016 - 3:20:33 PM
Last modification on : Tuesday, September 13, 2016 - 5:06:06 PM
Long-term archiving on: : Wednesday, December 14, 2016 - 2:08:24 PM

File

978-3-642-28255-3_10_Chapter.p...
Files produced by the author(s)

Licence


Distributed under a Creative Commons Attribution 4.0 International License

Identifiers

Citation

Maciej Drwal, Jerzy Józefczyk. Decentralized Approximation Algorithm for Data Placement Problem in Content Delivery Networks. 3rd Doctoral Conference on Computing, Electrical and Industrial Systems (DoCEIS), Feb 2012, Costa de Caparica, Portugal. pp.85-92, ⟨10.1007/978-3-642-28255-3_10⟩. ⟨hal-01365572⟩

Share

Metrics

Record views

89

Files downloads

175