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.
Type de document :
Communication dans un congrès
Luis M. Camarinha-Matos; Ehsan Shahamatnia; Gonçalo Nunes. 3rd Doctoral Conference on Computing, Electrical and Industrial Systems (DoCEIS), Feb 2012, Costa de Caparica, Portugal. Springer, IFIP Advances in Information and Communication Technology, AICT-372, pp.85-92, 2012, Technological Innovation for Value Creation. 〈10.1007/978-3-642-28255-3_10〉
Liste complète des métadonnées

Littérature citée [12 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01365572
Contributeur : Hal Ifip <>
Soumis le : mardi 13 septembre 2016 - 15:20:33
Dernière modification le : mardi 13 septembre 2016 - 17:06:06
Document(s) archivé(s) le : mercredi 14 décembre 2016 - 14:08:24

Fichier

978-3-642-28255-3_10_Chapter.p...
Fichiers produits par l'(les) auteur(s)

Licence


Distributed under a Creative Commons Paternité 4.0 International License

Identifiants

Citation

Maciej Drwal, Jerzy Józefczyk. Decentralized Approximation Algorithm for Data Placement Problem in Content Delivery Networks. Luis M. Camarinha-Matos; Ehsan Shahamatnia; Gonçalo Nunes. 3rd Doctoral Conference on Computing, Electrical and Industrial Systems (DoCEIS), Feb 2012, Costa de Caparica, Portugal. Springer, IFIP Advances in Information and Communication Technology, AICT-372, pp.85-92, 2012, Technological Innovation for Value Creation. 〈10.1007/978-3-642-28255-3_10〉. 〈hal-01365572〉

Partager

Métriques

Consultations de la notice

37

Téléchargements de fichiers

24