Robust Fault Tolerant uncapacitated facility location

Abstract : In the uncapacitated facility location problem, given a graph, a set of demands and opening costs, it is required to find a set of facilities R, so as to minimize the sum of the cost of opening the facilities in R and the cost of assigning all node demands to open facilities. This paper concerns the robust fault-tolerant version of the uncapacitated facility location problem (RFTFL). In this problem, one or more facilities might fail, and each demand should be supplied by the closest open facility that did not fail. It is required to find a set of facilities R, so as to minimize the sum of the cost of opening the facilities in R and the cost of assigning all node demands to open facilities that did not fail, after the failure of up to \alpha facilities. We present a polynomial time algorithm that yields a 6.5-approximation for this problem with at most one failure and a 1.5 + 7.5\alpha-approximation for the problem with at most \alpha > 1 failures. We also show that the RFTFL problem is NP-hard even on trees, and even in the case of a single failure.
Type de document :
Communication dans un congrès
Jean-Yves Marion and Thomas Schwentick. 27th International Symposium on Theoretical Aspects of Computer Science - STACS 2010, Mar 2010, Nancy, France. pp.191-202, 2010, Proceedings of the 27th Annual Symposium on the Theoretical Aspects of Computer Science. 〈http://arxiv.org/abs/0912.3188〉
Liste complète des métadonnées

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

https://hal.inria.fr/inria-00456122
Contributeur : Publications Loria <>
Soumis le : vendredi 12 février 2010 - 10:14:52
Dernière modification le : vendredi 12 février 2010 - 16:50:47
Document(s) archivé(s) le : vendredi 18 juin 2010 - 20:20:21

Fichier

chechik.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00456122, version 1

Collections

Citation

Shiri Chechik, David Peleg. Robust Fault Tolerant uncapacitated facility location. Jean-Yves Marion and Thomas Schwentick. 27th International Symposium on Theoretical Aspects of Computer Science - STACS 2010, Mar 2010, Nancy, France. pp.191-202, 2010, Proceedings of the 27th Annual Symposium on the Theoretical Aspects of Computer Science. 〈http://arxiv.org/abs/0912.3188〉. 〈inria-00456122〉

Partager

Métriques

Consultations de la notice

174

Téléchargements de fichiers

104