License: Creative Commons Attribution-NoDerivs 3.0 Unported license (CC BY-ND 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2010.2454
URN: urn:nbn:de:0030-drops-24547
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2010/2454/
Go to the corresponding LIPIcs Volume Portal

Chechik, Shiri ; Peleg, David

Robust Fault Tolerant Uncapacitated Facility Location

pdf-format:
1001.CheckShiri.2454.pdf (0.3 MB)

Abstract

In the {\em 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 {\em 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.

BibTeX - Entry

@InProceedings{chechik_et_al:LIPIcs:2010:2454,
  author =	{Shiri Chechik and David Peleg},
  title =	{{Robust Fault Tolerant Uncapacitated Facility Location}},
  booktitle =	{27th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{191--202},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-16-3},
  ISSN =	{1868-8969},
  year =	{2010},
  volume =	{5},
  editor =	{Jean-Yves Marion and Thomas Schwentick},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2010/2454},
  URN =		{urn:nbn:de:0030-drops-24547},
  doi =		{10.4230/LIPIcs.STACS.2010.2454},
  annote =	{Keywords: Facility location, approximation algorithms, fault-tolerance}
}

Keywords: Facility location, approximation algorithms, fault-tolerance
Collection: 27th International Symposium on Theoretical Aspects of Computer Science
Issue Date: 2010
Date of publication: 09.03.2010

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI