Facility Location on High-dimensional Euclidean Spaces
Euiwoong Lee, Kijun Shin · 2025
Read Facility Location on High-dimensional Euclidean Spaces by Euiwoong Lee, Kijun Shin (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2501-18105.txt.
Introduction
Placing facilities to serve scattered customers cheaply is a classic optimisation problem, and its geometry changes the answer. Euiwoong Lee and Kijun Shin study uncapacitated facility location in high-dimensional Euclidean space, where distances obey the rules of ordinary geometry. They prove an approximation algorithm that beats what is possible in general distance spaces, crossing a known hardness threshold for the general case.
That crossing is the headline: the first proven separation between Euclidean and general versions for this family of problems. A second algorithm improves on the best-known guarantee for the problem itself, shaving a small but real margin off a famous constant near one point four nine. Better guarantees mean planners can trust their near-optimal networks a little more.
Catalog record
| CREATOR | Euiwoong Lee, Kijun Shin |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 89 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2501-18105
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Facility Location on High-dimensional Euclidean Spaces Thanks: Supported by organization NSF CCF-2236669 and a gift from Google. Euiwoong Lee, Kijun Shin Abstract Recent years have seen great progress in the approximability of fundamental clustering and facility location problems on high-dimensional Euclidean spaces, including k k -Means and k k -Median. While they admit strictly better approximation ratios than their general metric versions, their approximation ratios are still higher than the hardness ratios for general metrics, leaving the possibility that the ultimate optimal approximation ratios will be the same between Euclidean and general metrics. Moreover, such an improved algorithm for Euclidean spaces is not known for Uncapaciated Facility Location (UFL), another fundamental problem in the area. In this paper, we prove that for any γ ≥ 1.6774 \gamma\geq 1.6774 there exists ε > 0 \varepsilon>0 such that Euclidean UFL admits a ( γ , 1 + 2 e − γ − ε ) (\gamma,1+2e^{-\gamma}-\varepsilon) -bifactor approximation algorithm, improving the result of Byrka and Aardal [ BA10 ] . Together with the ( γ , 1 + 2 e − γ ) (\gamma,1+2e^{-\gamma}) NP-hardness in general metrics, it shows the first separation between general and Euclidean metrics for the aforementioned basic problems. We also present an ( α Li − ε ) (\alpha_{\mathrm{Li}}-\varepsilon) -(unifactor) approximation algorithm for UFL for some ε > 0 \varepsilon>0 in Euclidean spaces, where α Li ≈ 1.488 \alpha_{\mathrm{Li}}\approx 1.488 is the best-known approximation ratio for UFL by Li [ Li13 ] . 1 Introduction The (metric) Uncapacitated Facility Location (UFL) is one of the most fundamental problems in computer science and operations research. The input of the problem consists of a metric space (X,d) , a set of facility locations \mathcal{F}\subseteq X , a set of clients \mathcal{C}\subseteq X , as well as facility opening costs \{f_{i}\}_{i\in\mathcal{F}} . The goal is open a subset of centers S\subseteq\mathcal{F} to minimize the sum of the opening cost (\sum_{i\in S}f_{i}) and the connection cost (\sum_{j\in\mathcal{C}}\min_{i\in S}d(i,j)) . After intensive research efforts over the years [ GK99 , JMS02 , MYZ02 , Li13 ] , the best approximation ratio is 1.488 [ Li13 ] and the best hardness ratio is 1.463 [ GK99 ] . As the objective function is the sum of two heterogeneous terms of the opening cost and the connection cost, the natural notion of bifactor approximation has been actively studied as well. Formally, given an instance of UFL, a solution S\subseteq\mathcal{F} is called an (\lambda_{f},\lambda_{c}) -approximation for some \lambda_{f},\lambda_{c}\geq 1 if, for any solution T\subseteq\mathcal{F} , the total cost of S is at most \lambda_{f}\cdot F^{*}+\lambda_{c}\cdot C^{*} , where F^{*} , C^{*} denote the opening and connection cost of T respectively. In particular, the case \lambda_{f}=1 , also known as a \lambda_{c} - Lagrangian Multiplier Preserving (LMP) approximation, has been actively studied due to its connection to another fundamental clustering problem of k -Median. There is a (2-\varepsilon) -LMP approximation for some \varepsilon>2\cdot 10^{-7} [ CAVGLS23 ] , and any \lambda_{c} -LMP approximation for UFL can be translated to 1.307\cdot\lambda_{c} -approximation for k -Median [ GPST23 ] . Generalizing the hardness of Guha and Khuller [ GK99 ] , Jain, Mahdian and Saberi [ JMS02 ] proved that no (\lambda_{f},\lambda_{c}) -approximation polynomial-time algorithm exists for \lambda_{c}<1+2e^{-\lambda_{f}} unless \mathbf{P}=\mathbf{NP} . (Guha-Khuller’s hardness ratio \gamma\approx 1.463 is exactly the solution of \gamma=1+2e^{-\gamma} .) While the optimal value for \lambda_{c} is not known for small values of \lambda_{f} , Byrka and Aardal gave an algorithm that achieves an (\lambda_{f},1+2e^{-\lambda_{f}}) -approximation for any \lambda_{f}\geq 1.6774 [ BA10 ] . Euclidean spaces are arguably the most natural metric spaces for facility location and clustering problems. Formally, Euclidean UFL is a special case of UFL where the underlying metric is (\mathbb{R}^{k},\|.\|_{2}) for some dimension k . When k=O(1) , this problem admits a PTAS [ CAFS21 ] , while the problem remains APX-hard when k is part of the input [ CASL22 ] . 1 1 1 While the cited paper only studies k -Median and k -Means, the soundness analysis in their Theorem 4.1 (of the arXiv version) can be directly extended to any number of open facilities k , implying APX-hardness of Euclidean UFL. Recent years have seen active studies on related k -Means and k -Median on high-dimensional Euclidean spaces [ ANFSW19 , GOR+22 , CAEMN22 ] , so that the best-known approximation ratios for them are 5.912 and 2.406 respectively. While they are strictly lower than the best-known approximation ratios for general metric spaces (which are 9 and 2.613 ), they are still larger than the best-known hardness ratios for general metrics (which are 1+8/e\approx 3.943 and 1+2/e\approx 1.73 ) [ JMS02 ] , which means that it is still plausible that the optimal approximation ratios for k -Median and k -Means are the same between Euclidean metrics and general metrics. Our first result is the first strict separation between Euclidean and general metric spaces for UFL. In particular, we show that Euclidean UFL admits a (1.6774,1+2e^{-1.6774}-\varepsilon) approximation for some universal constant \varepsilon>0 , which is NP-hard to do in general metrics. Theorem 1.1 . There exists a (1.6774,1+2e^{-1.6774}-\varepsilon) -approximation algorithm for Euclidean UFL for some \varepsilon\geq 3\cdot 10^{-42} . By the result of Mahdian et al. [ MYZ02 ] , it implies an (\gamma,1+2e^{-\gamma}-\varepsilon e^{-(\gamma-1.6774)}) -approximation for any \gamma\geq 1.6774 . Using this result, we are able to slightly improve the approximation ratio for the best-known (\alpha_{\mathrm{Li}}\approx 1.488) -unifactor approximation of Li [ Li13 ] . Theorem 1.2 . There exists a (\alpha_{\mathrm{Li}}-\varepsilon) -approximation algorithm for Euclidean UFL for some \varepsilon\geq 2\cdot 10^{-45} . Recent years also have seen great progress on hardness of approximation for clustering problems in high-dimensional Euclidean spaces, including Euclidean k -Means and k -Median [ CAK19 , CASL22 ] . We show that similar techniques extend to UFL as well, proving the APX-hardness. Theorem 1.3 . Euclidean UFL is APX-hard. 2 High-level Plan Our work is based on the framework of Byrka and Aardal [ BA10 ] who achieved an optimal (\lambda_{f},1+2e^{-\lambda_{f}}) -bifactor approximation for \lambda_{f}\geq 1.6774 in general metrics. We first review their framework. It is based on the following standard linear programming (LP) relaxation: Minimize \displaystyle\sum\limits_{i\in\mathcal{F},j\in\mathcal{C}}d(i,j)x_{ij}+\sum\limits_{i\in\mathcal{F}}f_{i}y_{i} subject to \displaystyle\sum\limits_{i\in\mathcal{F}}x_{ij}=1 \displaystyle\forall j\in\mathcal{C}, \displaystyle x_{ij}\leq y_{i} \displaystyle\forall i\in\mathcal{F},j\in\mathcal{C}, \displaystyle x_{ij},y_{i}\in[0,1] \displaystyle\forall i\in\mathcal{F},j\in\mathcal{C}. The dual formulation is as follows: Maximize \displaystyle\sum\limits_{j\in\mathcal{C}}v_{j} subject to \displaystyle\sum\limits_{j\in\mathcal{C}}w_{ij}\leq f_{i} \displaystyle\forall i\in\mathcal{F}, \displaystyle v_{j}\leq w_{ij} \displaystyle\forall i\in\mathcal{F},j\in\mathcal{C}, \displaystyle w_{ij}\geq 0 \displaystyle\forall i\in\mathcal{F},j\in\mathcal{C}. A feasible solution (x,y) induces the support graph , which is defined as the bipartite graph G=((\mathcal{F},\mathcal{C}),E) where nodes i\in\mathcal{F} and j\in\mathcal{C} are adjacent iff the corresponding LP variable x_{ij}>0 . Two clients j,j^{\prime}\in\mathcal{C} are considered neighbors in G if they share the same facility. Let (x^{*},y^{*}) be a fixed optimal solution to the primal program. The overall cost is divided into the facility cost F^{*}=\sum_{i\in\mathcal{F}}f_{i}y^{*}_{i} and the connection cost C^{*}=\sum_{i\in\mathcal{F},j\in\mathcal{C}}d(i,j)x^{*}_{ij} . Our goal is to round this solution to obtain a solution S whose total cost is at most \lambda_{f}F^{*}+\lambda_{c}C^{*} ; it is well known that it implies the (\lambda_{f},\lambda_{c}) -approximation defined in the introduction by scaling [ BA10 ] , so let us redefine the (\lambda_{f},\lambda_{c}) -approximation for the rest of the paper so that S is (\lambda_{f},\lambda_{c}) -approximate if its total cost