Facility Location on High-Dimensional Euclidean Spaces

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 $ℱ\subseteq X$, a set of clients $𝒞\subseteq X$, as well as facility opening costs ${\{f_i\}}_{i\in ℱ}$. The goal is open a subset of centers $S\subseteq ℱ$ to minimize the sum of the opening cost $({\sum }_{i\in S}{f}_i)$ and the connection cost $({\sum }_{j\in 𝒞}{\min }_{i\in S}d(i,j))$. After intensive research efforts over the years [11, 12, 16, 15], the best approximation ratio is $1.488$ [15] and the best hardness ratio is $1.463$ [11].

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 ℱ$ is called an $({\lambda }_f,{\lambda }_c)$-approximation for some ${\lambda }_f,{\lambda }_c\ge 1$ if, for any solution $T\subseteq ℱ$, the total cost of $S$ is at most ${\lambda }_f\cdot F^{\ast }+{\lambda }_c\cdot C^{\ast }$, where $F^{\ast }$, $C^{\ast }$ 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-\epsilon )$-LMP approximation for some $\epsilon >2\cdot {10}^{-7}$ [8], and any ${\lambda }_c$-LMP approximation for UFL can be translated to $1.307\cdot {\lambda }_c$-approximation for $k$-Median [9].

Generalizing the hardness of Guha and Khuller [11], Jain, Mahdian and Saberi [12] proved that no $({\lambda }_f,{\lambda }_c)$-approximation polynomial-time algorithm exists for unless $𝐏=\mathrm{𝐍𝐏}$. (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\ge 1.6774$ [3].

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 $({ℝ}^k,\parallel .{\parallel }_2)$ for some dimension $k$. When $k=O(1)$, this problem admits a PTAS [5], while the problem remains APX-hard when $k$ is part of the input [7].¹¹1While 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 [1, 10, 4], 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$) [12], 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}-\epsilon )$ approximation for some universal constant $\epsilon >0$, which is NP-hard to do in general metrics.

By the result of Mahdian et al. [16], it implies an $(\gamma ,1+2e^{-\gamma }-\epsilon e^{-(\gamma -1.6774)})$-approximation for any $\gamma \ge 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 [15].

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 [6, 7]. We show that similar techniques extend to UFL as well, proving the APX-hardness.

Our work is based on the framework of Byrka and Aardal [3] who achieved an optimal $({\lambda }_f,1+2e^{-{\lambda }_f})$-bifactor approximation for ${\lambda }_f\ge 1.6774$ in general metrics. We first review their framework. It is based on the following standard linear programming (LP) relaxation:

The dual formulation is as follows:

A feasible solution $(x,y)$ induces the support graph, which is defined as the bipartite graph $G=((ℱ,𝒞),E)$ where nodes $i\in ℱ$ and $j\in 𝒞$ are adjacent iff the corresponding LP variable $x_{ij}>0$. Two clients $j,j^{\prime }\in 𝒞$ are considered neighbors in $G$ if they share the same facility.

Let $(x^{\ast },y^{\ast })$ be a fixed optimal solution to the primal program. The overall cost is divided into the facility cost $F^{\ast }={\sum }_{i\in ℱ}{f}_i{y}_i^{\ast }$ and the connection cost $C^{\ast }={\sum }_{i\in ℱ,j\in 𝒞}d(i,j)x_{ij}^{\ast }$. Our goal is to round this solution to obtain a solution $S$ whose total cost is at most ${\lambda }_f{F}^{\ast }+{\lambda }_c{C}^{\ast }$; it is well known that it implies the $({\lambda }_f,{\lambda }_c)$-approximation defined in the introduction by scaling [3], 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 is ${\lambda }_f{F}^{\ast }+{\lambda }_c{C}^{\ast }$.

The opening cost and connection cost for individual clients can be further divided using the optimal LP dual solution $(v^{\ast },w^{\ast })$. For each client $j\in 𝒞$, the fractional connection cost is given by $C_j^{\ast }={\sum }_{i\in ℱ}d(i,j)x_{ij}^{\ast }$, and the fractional facility cost is computed as $F_j^{\ast }=v_j^{\ast }-C_j^{\ast }$. The irregularity of the facilities surrounding $j\in 𝒞$ is defined by

Similarly,

If ${\sum }_{i\in {ℱ}^{\prime }}{y}_i^{\ast }=0$, we set $d(j,{ℱ}^{\prime })=0$. Similarly, when $F_j^{\ast }=0$, we define $r_{\gamma }(j)=0$ and $r_{\gamma }^{\prime }(j)=0$. According to the definition, the following conditions hold: the irregularity $0\le r_{\gamma }(j)\le 1$, the average distance to a close facility $C_j=d(j,{𝒞}_j)=C_j^{\ast }-r_{\gamma }^{\prime }(j)\cdot F_j^{\ast }$, and the average distance to a distant facility $D_j=d(j,{𝒟}_j)=C_j^{\ast }+r_{\gamma }(j)\cdot F_j^{\ast }$. The maximum distance to a close facility is bounded by $M_j\le D_j$.

In this section, we exploit the geometry of Euclidean spaces to prove the existence of a cluster center strictly better than the greedy choice of [3] under certain conditions (Theorem 10). We first define several concepts and introduce their motivation, including the sketch of our algorithm.

Recall that our goal is to find a cluster that satisfies (1). In all the following propositions, $\gamma$ is a fixed value in the range $\gamma \in (1.6,2)$.

With the goal (1) in mind, $N_{j^{\prime }}^{+}$ (resp. $N_{j^{\prime }}^{-}$) contains clients $j$ who meet (resp. do not meet) this goal, and $Saving(j^{\prime })$ (resp. $Spending(j^{\prime })$) indicates how much $cos{t}_{j^{\prime }}(j)$ exceeds (resp. is short of) this goal. Note that $N_{j^{\prime }}^{-}\subseteq N_{j^{\prime }}\subseteq N_{j^{\prime }}^{+}\cup N_{j^{\prime }}^{-}$ by definition; it is the best cluster for center $j^{\prime }$, which contains all its neighbors (which is required by the algorithm design) and possibly more to increase savings. Therefore, if $Saving(j^{\prime })\ge Spending(j^{\prime })$, then $j^{\prime }$ is considered a good center; otherwise, it is a bad center.

Now, we will explain some problematic situations that arise when extending the problem to the general case, i.e., without restrictions on $C_j$, $M_j$, and $D_j$’s. The first simple concern is that the choice of the center $j^{\prime }$ will no longer be solely based on $C_{j^{\prime }}+M_{j^{\prime }}$ as in Algorithm 1, which breaks the previous arguments. Therefore, to gain more flexibility in selecting a new cluster center, it is beneficial to decompose the entire support graph into several layers, where each layer only concerns clients with roughly the same $C_{j^{\prime }}+M_{j^{\prime }}$ values.

However, there are still two more scenarios where the above strategy might not hold, as illustrated in Figure 3. This means that the neighbors in $N_{j^{\prime }}^{-}$ are all bad clients, but do not create a dense region.

1. I.

   If $C_{j^{\prime }}\ll s$, the facilities in ${𝒞}_{j^{\prime }}$ are concentrated near $j^{\prime }$. In this case, since all the facilities are very close to $j^{\prime }$, the 3-hop triangle inequality is almost tight for any $j\in N_{j^{\prime }}$ regardless of where it is.

2. II.

   Recall that if ${𝒞}_j\cup {𝒟}_j$ is large enough to exclude the facilities of ${𝒞}_{j^{\prime }}$, then $cos{t}_{j^{\prime }}(j)$ might not behave as expected. In particular, a technical problem arises when two facilities from ${𝒞}_{j^{\prime }}$ that are almost antipodal with respect to $j^{\prime }$ are both contained in ${𝒞}_j\cup {𝒟}_j$, which is illustrated in Figure 3 (right).

The following definition addresses Scenario I.

The following definition addresses Scenario II. Note that $v_j^{\ast }$ is the maximum distance between $j$ and any facility in ${𝒞}_j\cup {𝒟}_j$. We are interested in the ball around $j^{\prime }$ of radius $0.998z_{j^{\prime }}(j)$ (for sake of analysis), and $j$ having a small remote arm with respect to $j^{\prime }$ means that ${𝒞}_j\cup {𝒟}_j$ cannot contain two antipodal points in our ball of interest (with some slack depending on $\alpha$). Let $z_{j^{\prime }}(j)=d(j^{\prime },{𝒞}_{j^{\prime }}\setminus ({𝒞}_j\cup {𝒟}_j))$. The right-hand side represents the square of the length of the other side of a triangle, where the lengths of the two sides are $d(j^{\prime },j)$ and $0.998z_{j^{\prime }}(j)$, and the included angle between them is $\frac{\pi }{2}-\alpha$.

In Section 3.1, we will show that these two scenarios are the only bad cases to worry about. For instance, if we assume that everything is normal and has a small remote arm, each candidate center $j^{\prime }\in 𝒞$ is either good or contains another candidate center $j^{\prime \prime }$ with $Saving(j^{\prime \prime })>Saving(j^{\prime })$ in its dense region.

How can we handle these two bad scenarios? In the following two lemmas, we prove that both the weird center and the big remote arm neighbor imply a high ratio of fractional facility cost $F_{j^{\prime }}^{\ast }$ to fractional connection cost $C_{j^{\prime }}^{\ast }$. The proof appears in the extended version of this paper [14].

Therefore, if we consider a (sub)instance that has a low facility-to-connection cost ratio, it is natural to expect to apply this argument, which ultimately leads to a (somewhat) good center. Throughout the paper, we will often express this low facility-to-connection ratio condition will be expressed as $C^{\ast }>K{F}^{\ast }$ and use the following values for $K$: $K_1=1.3025>K_2=1.3024>K_3=1.3023>K_4=1.3022>K_5=1.3021>K_6=1.302$. The following theorem is the main result of the section.