Abstract
We present a new randomized LP-rounding 1.7245-approximation algorithm for the metric Fault-Tolerant Uncapacitated Facility Location (FTFL) problem. This represents a significant improvement over the previous state-of-the-art 2.076-approximation. Our approach introduces a novel hierarchical clustering scheme and provides the first application of dependent-rounding techniques to the facility location domain. By constructing a laminar family of clusters to guide the rounding procedure, we exploit the properties of dependent rounding to achieve a tighter analysis and a superior approximation ratio.
Introduction
The Uncapacitated Facility Location (UFL) problem is a cornerstone of combinatorial optimization. However, real-world infrastructure often requires resilience against failure. The Fault-Tolerant Facility Location (FTFL) problem addresses this by requiring that each client $j$ be connected to a specific number of distinct open facilities, $r_j$. This "coverage requirement" ensures service continuity even if some facilities become unavailable.
While UFL has been extensively studied, FTFL is significantly more complex due to the varying requirements across different clients. Prior to this work, the best-known approximation ratio for FTFL was 2.076, established by Swamy and Shmoys. This paper bridges the gap further toward the theoretical lower bound of approximately 1.463 by introducing a 1.7245-approximation algorithm.
The FTFL Problem and LP Relaxation
In the metric FTFL problem, we are given a set of potential facilities and a set of clients in a metric space. Each facility $i$ has an opening cost $f_i$, and each client $j$ has a connection requirement $r_j$ and a connection cost $d(j, i)$ to facility $i$. The goal is to minimize the sum of facility opening costs and connection costs while ensuring each client $j$ is served by $r_j$ unique facilities.
The algorithm begins with a Linear Programming (LP) relaxation of the problem. The challenge lies in rounding the fractional solutions of the LP into an integer solution (where facilities are either fully open or closed) without excessively increasing the total cost.
Methodological Innovations
1. Hierarchical (Laminar) Clustering
Traditional LP-rounding for facility location typically involves partitioning facilities into disjoint clusters. In such schemes, the algorithm ensures that at least one facility is opened per cluster. However, this approach struggles with the multi-facility requirements of FTFL.
The authors propose a hierarchical clustering scheme that constructs a laminar family of clusters. In this structure, clusters can be nested within one another, forming a forest or tree-like hierarchy. This allows the algorithm to satisfy high $r_j$ requirements by ensuring that multiple facilities are opened within the nested layers of clusters surrounding a client, effectively managing the "fault-tolerance" demand without redundant costs.
2. Dependent LP-Rounding
This work marks the first application of dependent rounding to facility location. In independent rounding, each facility is opened based on its fractional LP value via an independent coin flip. This often leads to high variance and may fail to satisfy the hard constraint of opening exactly $r_j$ facilities near a client.
Dependent rounding couples these probabilities. By rounding variables in a way that preserves the sum of fractional values within the laminar clusters, the algorithm provides a deterministic guarantee on the number of facilities opened in specific regions. This coupling reduces the expected connection cost while maintaining the feasibility of the solution.
Key Theoretical Insights
A major contribution of this research is the proof of a new mathematical property for dependent rounding. The authors demonstrate that for any set of facilities, the expected value of the connection cost under dependent rounding is at most the expected value under independent rounding. Specifically, they show that for a set of variables $X$ and a requirement $k$, the expectation $E[\min\{k, X\}]$ is optimized by the dependent rounding approach. This allows the use of independent variable analysis (which is mathematically simpler) to provide a conservative upper bound on the performance of the more efficient dependent rounding process.
Results and Conclusion
The resulting algorithm achieves an approximation ratio of 1.7245, a substantial improvement over the previous 2.076. This result demonstrates that hierarchical clustering combined with dependent rounding is a powerful framework for solving complex network design problems.
While the 1.7245 ratio is a major step forward, a gap remains between this upper bound and the 1.463 lower bound. The authors suggest that the true threshold for FTFL may match the UFL lower bound, and they advocate for the application of these dependent rounding techniques to other variations of facility location and broader network design challenges.
Summary updated