Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Conferences, Workshops, Symposiums, and Seminars
  4. Fault-Tolerant Facility Location: a randomized dependent LP-rounding algorithm
 
conference paper

Fault-Tolerant Facility Location: a randomized dependent LP-rounding algorithm

Byrka, Jaroslaw
•
Srinivasan, Aravind
•
Swamy, Chaitanya
2010
Integer Programming and Combinatorial Optimization. IPCO 2010
14th Conference on Integer Programming and Combinatorial Optimization

We give a new randomized LP-rounding 1.725-approximation algorithm for the metric Fault- Tolerant Uncapacitated Facility Location problem. This improves on the previously best known 2.076-approximation algorithm of Swamy & Shmoys. To the best of our knowledge, our work provides the first application of a dependent-rounding technique in the domain of facility location. The analysis of our algorithm benefits from, and extends, methods developed for Uncapacitated Facility Location; it also helps uncover new properties of the dependent-rounding approach. An important concept that we develop is a novel, hierarchical clustering scheme. Typically, LP-rounding approximation algorithms for facility location problems are based on partitioning facilities into disjoint clusters and opening at least one facility in each cluster. We extend this approach and construct a laminar family of clusters, which then guides the rounding procedure. It allows to exploit properties of dependent rounding, and provides a quite tight analysis resulting in the improved approximation ratio.

  • Details
  • Metrics
Type
conference paper
DOI
10.1007/978-3-642-13036-6_19
Web of Science ID

WOS:000279619300019

Author(s)
Byrka, Jaroslaw
Srinivasan, Aravind
Swamy, Chaitanya
Date Issued

2010

Publisher

Springer-Verlag

Publisher place

New York

Published in
Integer Programming and Combinatorial Optimization. IPCO 2010
Series title/Series vol.

Lecture Notes in Computer Science; 6080

Start page

244

End page

257

Subjects

facility location

•

fault-tolerant

•

approximation

•

dependent randomized rounding

URL

URL

http://ipco.epfl.ch/
Editorial or Peer reviewed

REVIEWED

Written at

EPFL

EPFL units
DISOPT  
Event nameEvent placeEvent date
14th Conference on Integer Programming and Combinatorial Optimization

Lausanne

June 9-11, 2010

Available on Infoscience
February 2, 2010
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/46374
Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés