Local-search based approximation algorithms for mobile facility location problems

Sara Ahmadian, Zachary Friggstad, Chaitanya Swamy

Abstract

In the Mobile Facility Location (MFL) problem, a set of facilities and clients are positioned within a common metric space. The objective is to relocate each facility to a new destination and assign each client to a facility such that the sum of facility movement costs and client assignment costs is minimized. This paper presents the first local-search based approximation algorithm for MFL, achieving a $(3 + \epsilon)$-approximation guarantee for any constant $\epsilon > 0$. This result significantly improves upon the previous best guarantee of 8 (derived from LP-rounding) and matches the best-known approximation for the related $k$-median problem. The analysis introduces a novel tree-like structure to coordinate local-search moves, providing a tight bound on the locality gap.

Introduction

Facility location problems are foundational in combinatorial optimization, typically focusing on the static placement of resources to serve a distributed set of demands. However, many real-world scenarios involve "mobile" resources—such as emergency response vehicles, mobile sensors, or modular warehouses—that can be repositioned from their initial locations to better serve clients.

The Mobile Facility Location (MFL) problem formalizes this flexibility. Unlike the standard $k$-median problem, where one simply selects $k$ locations to open, MFL requires accounting for the specific cost of moving a particular facility from its starting point to its destination. This paper by Ahmadian, Friggstad, and Swamy bridges the gap between MFL and $k$-median, showing that the two problems share the same fundamental approximability limits.

Problem Definition

In an MFL instance, we are given a metric space $G = (V, c)$, a set of facilities $F$, and a set of clients $D$. Each facility $i \in F$ starts at an initial location $s_i \in V$. The goal is to determine a destination $v_i \in V$ for each facility and an assignment $\phi: D \to F$ that minimizes the total cost:

$$\text{Cost} = \sum_{i \in F} w_i \cdot c(s_i, v_i) + \sum_{j \in D} c(j, v_{\phi(j)})$$

Here, $w_i$ represents the weight of facility $i$ (the cost per unit of distance moved). When all $w_i = 1$, the problem is unweighted. The objective function balances the "reconfiguration cost" of the infrastructure with the "service cost" provided to the clients.

The Local Search Algorithm

Previous approaches to MFL relied on complex Linear Programming (LP) rounding techniques. This work proposes a simpler, more intuitive local search strategy. The algorithm proceeds as follows:

  1. Initialization: Start with an arbitrary set of $k$ destinations for the $k$ facilities.
  2. The Swap Step: In each iteration, consider swapping a small number ($p$) of current destinations for $p$ new destinations in $V$.
  3. Optimal Rematching: Crucially, for any proposed set of $k$ destinations, the algorithm does not simply assign facilities to the nearest point. Instead, it computes a minimum-cost perfect matching to move the initial facilities to these new destinations. This step is essential because MFL is non-additive; changing one destination can shift the optimal movement path for all other facilities.
  4. Termination: If a swap exists that reduces the total cost by a sufficient margin, the algorithm updates the destinations and repeats. If no such swap is found, it has reached a local optimum.

Analysis via Recursion Trees

The primary challenge in local search is bounding the "locality gap"—the ratio between a local optimum and the global optimum. Standard analysis for facility location usually involves simple, independent swaps. However, in MFL, the movement costs create dependencies across the entire configuration.

To overcome this, the authors introduce a novel analysis technique. They define a tree-like structure that functions as a recursion tree to generate a collection of local-search moves. By exploring this tree to a constant depth, they can aggregate multiple inequalities to bound the cost of the local solution against the global optimum. This recursive approach allows the analysis to handle "interval swaps" along long relocation paths, which are common in MFL but difficult to analyze using traditional methods.

Key Results and Implications

1. Improved Approximation Guarantee

The algorithm achieves a $(3 + \epsilon)$-approximation. This is a significant leap from the previous factor of 8. Because there is an approximation-preserving reduction from the $k$-median problem to MFL, and the best-known guarantee for $k$-median is also 3, this result is effectively the best possible for this class of algorithms.

2. Tightness

The authors demonstrate that their analysis is tight. The classic example used to show the 3-approximation limit for $k$-median can be adapted to MFL, proving that no local-search algorithm using a constant number of swaps can achieve a factor better than 3.

3. Weighted Generalization

The $(3 + \epsilon)$ guarantee holds even in the weighted case, where different facilities have different movement costs. This extension is vital for practical applications where moving different types of equipment (e.g., a heavy truck vs. a light van) incurs different costs.

Conclusion

By introducing an optimal matching step into the local search and utilizing a recursive tree structure for the analysis, the authors have successfully aligned the complexity of Mobile Facility Location with the $k$-median problem. While the computational cost increases as $\epsilon$ decreases (requiring larger swap sets $p$), the algorithm provides a robust theoretical framework for resource relocation. Future research may explore the "unrelated metric" case, where movement and assignment costs are governed by different distance functions, a variation that currently lacks a constant-factor approximation.

Summary updated

Abstract

We consider the mobile facility location (MFL) problem. We are given a set of facilities and clients located in a common metric space G = (V, c). The goal is to move each facility from its initial location to a destination (in V) and assign each client to the destination of some facility so as to minimize the sum of the movement-costs of the facilities and the client-assignment costs. This abstracts facility-location settings where one has the flexibility of moving facilities from their current locations to other destinations so as to serve clients more efficiently by reducing their assignment costs.We give the first local-search based approximation algorithm for this problem and achieve the best-known approximation guarantee. Our main result is (3 + e)-approximation for this problem for any constant e > 0 using local search. The previous best guarantee for MFL was an 8-approximation algorithm due to Friggstad and Salavatipour [12] based on LP-rounding. Our guarantee matches the best-known approximation guarantee for the k-median problem. Since there is an approximation-preserving reduction from the k-median problem to MFL, any improvement of our result would imply an analogous improvement for the k-median problem. Furthermore, our analysis is tight (up to o(1) factors) since the tight example for the local-search based 3-approximation algorithm for k-median can be easily adapted to show that our local-search algorithm has a tight approximation ratio of 3. Our results extend to the weighted generalization wherein each facility i has a non-negative weight wi and the movement cost for i is wi times the distance traveled by i.In contrast to the k-median problem, the local search procedure that moves, at each step, a constant number of facilities (to chosen destinations) and assigns each client to the nearest destination, is known to have an unbounded locality gap. Our local-search algorithm is a natural and simple variant, where we only select the destinations of the facilities in each step and optimally rematch the facilities to these destinations (which might entail moving all facilities). One of the chief novelties in the analysis is that in order to generate a suitable collection of local-search moves whose resulting inequalities yield the desired bound on the cost of a local-optimum, we define a tree-like structure that (loosely speaking) functions as a recursion tree, using which we spawn off local-search moves by exploring this tree to a constant depth.
BibTeX
@inproceedings{ahmadian2013local,
  author = {Sara Ahmadian and Zachary Friggstad and Chaitanya Swamy},
  title = {{Local-search based approximation algorithms for mobile facility location problems}},
  booktitle = {SODA},
  year = {2013},
  doi = {10.1137/1.9781611973105.115},
}
Figure