LP-rounding algorithms for the fault-tolerant facility placement problem

DOI10.1016/J.JDA.2015.03.004MaRDI QIDQ491622zbMATH OpenOpenAlexFDO

Authors Marek Chrobak, Li Yan

Publication date 18 August 2015

Published in Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1205.1281

zbMATH Keywords

approximation algorithmsfacility location

Mathematics Subject Classification ID

Approximation algorithms (68W25) Discrete location and assignment (90B80)

Abstract: The Fault-Tolerant Facility Placement problem (FTFP) is a generalization of the classic Uncapacitated Facility Location Problem (UFL). In FTFP we are given a set of facility sites and a set of clients. Opening a facility at site $i$ costs $f_i$ and connecting client $j$ to a facility at site $i$ costs $d_{ij}$. We assume that the connection costs (distances) $d_{ij}$ satisfy the triangle inequality. Multiple facilities can be opened at any site. Each client $j$ has a demand $r_j$, which means that it needs to be connected to $r_j$ different facilities (some of which could be located on the same site). The goal is to minimize the sum of facility opening cost and connection cost. The main result of this paper is a 1.575-approximation algorithm for FTFP, based on LP-rounding. The algorithm first reduces the demands to values polynomial in the number of sites. Then it uses a technique that we call adaptive partitioning, which partitions the instance by splitting clients into unit demands and creating a number of (not yet opened) facilities at each site. It also partitions the optimal fractional solution to produce a fractional solution for this new instance. The partitioned instance satisfies a number of properties that allow us to exploit existing LP-rounding methods for UFL to round our partitioned solution to an integral solution, preserving the approximation ratio. In particular, our 1.575-approximation algorithm is based on the ideas from the 1.575-approximation algorithm for UFL by Byrka et al., with changes necessary to satisfy the fault-tolerance requirement.

Recommendations

• LP-rounding algorithms for the fault-tolerant facility placement problem (extended abstract)
• Improved approximation algorithm for fault-tolerant facility placement
• Approximation algorithms for the fault-tolerant facility placement problem
• Fault-tolerant facility location
• Fault-tolerant facility location: a randomized dependent LP-rounding algorithm

Cites work

• scientific article; zbMATH DE number 1303608 (Why is no real title available?)
• scientific article; zbMATH DE number 1559542 (Why is no real title available?)
• scientific article; zbMATH DE number 2086926 (Why is no real title available?)
• A 1.488 Approximation Algorithm for the Uncapacitated Facility Location Problem
• A Constant Factor Approximation Algorithm for Fault-Tolerant k-Median
• An approximation algorithm for the fault tolerant metric facility location problem
• An optimal bifactor approximation algorithm for the metric uncapacitated facility location problem
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• Approximation algorithms for the fault-tolerant facility placement problem
• Fault-tolerant facility location
• Fault-tolerant facility location: a randomized dependent LP-rounding algorithm
• Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP
• Improved Approximation Algorithms for the Uncapacitated Facility Location Problem
• Improved algorithms for fault tolerant facility location
• Improved approximation algorithm for fault-tolerant facility placement
• Improved approximation algorithms for constrained fault-tolerant resource allocation (extended abstract)
• Local Search Heuristics for k-Median and Facility Location Problems
• The fault-tolerant facility allocation problem
• Unconstrained and constrained fault-tolerant resource allocation

Cited in

(10)

• Improved approximation algorithms for constrained fault-tolerant resource allocation
• Constant approximation for fault-tolerant median problems via iterative rounding
• Fault-tolerant facility location: a randomized dependent LP-rounding algorithm
• Approximation algorithms for the fault-tolerant facility location problem with penalties
• LP-rounding algorithms for the fault-tolerant facility placement problem (extended abstract)
• Approximation algorithms for the fault-tolerant facility placement problem
• LP-rounding approximation algorithms for two-stage stochastic fault-tolerant facility location problem
• Approximation algorithms for fault tolerant facility allocation
• Approximation algorithm for the fault-tolerant facility placement problem with penalties
• Improved approximation algorithm for fault-tolerant facility placement

This page was built for publication: LP-rounding algorithms for the fault-tolerant facility placement problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q491622)