Dynamic facility location via exponential clocks

DOI10.1145/2928272MaRDI QIDQ4962653zbMATH OpenOpenAlexWikidataFDO

Authors Hyung-Chan An, Ashkan Norouzi-Fard, Ola Svensson

Publication date 5 November 2018

Published in ACM Transactions on Algorithms (Search for Journal in Brave)

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

zbMATH Keywords

approximation algorithmsexponential clocksfacility location problems

Mathematics Subject Classification ID

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

Abstract: The emph{dynamic facility location problem} is a generalization of the classic facility location problem proposed by Eisenstat, Mathieu, and Schabanel to model the dynamics of evolving social/infrastructure networks. The generalization lies in that the distance metric between clients and facilities changes over time. This leads to a trade-off between optimizing the classic objective function and the "stability" of the solution: there is a switching cost charged every time a client changes the facility to which it is connected. While the standard linear program (LP) relaxation for the classic problem naturally extends to this problem, traditional LP-rounding techniques do not, as they are often sensitive to small changes in the metric resulting in frequent switches. We present a new LP-rounding algorithm for facility location problems, which yields the first constant approximation algorithm for the dynamic facility location problem. Our algorithm installs competing exponential clocks on the clients and facilities, and connect every client by the path that repeatedly follows the smallest clock in the neighborhood. The use of exponential clocks gives rise to several properties that distinguish our approach from previous LP-roundings for facility location problems. In particular, we use emph{no clustering} and we allow clients to connect through paths of emph{arbitrary lengths}. In fact, the clustering-free nature of our algorithm is crucial for applying our LP-rounding approach to the dynamic problem.

Recommendations

• Dynamic facility location via exponential clocks
• Facility location in evolving metrics
• scientific article; zbMATH DE number 5811147
• Approximation algorithms for the dynamic \(k\)-level facility location problems
• Facility location with dynamic distance functions

Cited in

(18)

• Online multistage subset maximization problems
• A simple rounding scheme for multistage optimization
• Target-based computer-assisted orchestration: complexity and approximation algorithms
• Facility reallocation on the line
• LP-based algorithms for multistage minimization problems
• Multistage knapsack
• Approximation algorithms for clustering with dynamic points
• Reallocating multiple facilities on the line
• Online facility location with deletions
• scientific article; zbMATH DE number 7525448 (Why is no real title available?)
• Multistage knapsack
• scientific article; zbMATH DE number 7238962 (Why is no real title available?)
• Facility location in evolving metrics
• Dynamic facility location via exponential clocks
• Approximation algorithms for clustering with dynamic points
• A polynomial-time exact algorithm for the connected k-facility location problem on trees
• Approximation algorithm for dynamic facility location problem
• On the approximability of multistage min-sum set cover

This page was built for publication: Dynamic facility location via exponential clocks

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