1 Introduction↩︎

Given a collection \(D\) of \(n\) points, a clustering is a partition of the points into (typically) disjoint subsets (the clusters) such that points in the same cluster are similar and points in different clusters are dissimilar. One of the classical and best-studied clustering problems is \(k\)-median (see also Table 1). Here, in addition to the set \(D\) (points are also called clients in this framework), we are given an integer parameter \(k>0\) and a set \(F\)⁶ (the facilities or centers), with metric distances \(d(a,b)\) for \(a,b\in D\cup F\). Our goal is to select \(k\) centers \(S\subseteq F\) (open centers) so as to minimize the sum of the distances from each client to the closest open center. In other words, the goal is to minimize the following objective function \[\text{cost}(S):=\sum_{j\in D} \min_{i\in S}d(i,j).\] The \(k\)-clustering induced by \(S\) is obtained by considering, for each \(c\in S\), the subset of points that have \(c\) as a closest center in \(S\) (breaking ties arbitrarily). We use \(\text{opt}_k\) to denote the optimal cost, and simply use \(\text{opt}\) when \(k\) is clear from the context.

For most clustering variants, it is NP-hard to compute an optimal clustering and metric \(k\)-median is no exception. For this reason a lot of effort was devoted to the design of (polynomial-time) approximation algorithms for this problem, i.e., algorithms that compute a feasible solution \(S\) whose cost is provably within some factor \(\alpha>1\) of \(\text{opt}\) (the approximation factor or approximation ratio/guarantee).

Most of the best-known approximation algorithms for \(k\)-median, including the current-best one [1], [2], are based on the following high-level approach (see Section 1.2 for alternative approaches in the literature). One considers the associated facility location problem, where instead of \(k\) we are given a (uniform) facility opening cost \(f\). In this problem a feasible solution \(S\) can contain an arbitrary number of centers/facilities (rather than \(k\)), however in the objective function, besides the connection cost \(cost(S)\), one has to pay also the opening cost \(f|S|\). Then one uses a Lagrangian Multiplier Preserving (LMP) \(\alpha_{LMP}\)-approximation for the problem (formal definition in Section 1.3) to construct a bi-point solution for \(k\)-median, i.e., a convex combination of a solution \(S_1\) (opening fewer than \(k\) centers) and a solution \(S_2\) (opening more than \(k\) centers), that opens exactly \(k\) centers in a fractional sense. In particular, sampling one of the two solutions according to the respective coefficients would give a solution of expected cost \(\alpha_{LMP}\cdot \text{opt}\) that opens \(k\) centers in expectation. Finally, a bi-point rounding algorithm is used to derive a feasible \(k\)-median solution, while losing another factor \(\alpha_{BPR}\) in the approximation. The product \(\alpha_{LMP}\cdot \alpha_{BPR}\) gives the overall approximation factor. We remark that the state of the art leaves a significant gap between the approximation factor for a solution with \(k\) centers in expectation and a true \(k\)-median solution.

In more detail, for the LMP stage, [7] gave a \(3\)-approximation algorithm which was subsequently improved to \(2\) by [8], [9], and then to \(2-\eta\) for some \(\eta > 2.25\cdot 10^{-7}\) by [1]. [7] also presented a factor \(2\) algorithm for the bi-point rounding stage. \(\cite{LiS16}\) subsequently improved this to a factor \(\frac{1+\sqrt{3}}{2} \approx 1.366\) when allowing to use \(k+O(1)\) many centers⁷, and also gave a polynomial-time algorithm for obtaining a proper \(k\)-median clustering from a \(k+O(1)\) clustering essentially without any loss in the approximation ratio. This approach was further refined by [11] who gave a \(1.337\)-approximate bi-point rounding algorithm and also showed that no LP-based rounding algorithm can do better than \(\frac{1+\sqrt{2}}{2}\). The state of the art for rounding methods is due to [2] who gave a \(1.306\)-approximation algorithm, while showing that no algorithm can do better than \(\sqrt{\phi} \approx 1.272\), where \(\phi = \frac{1+\sqrt{5}}{2}\) is the golden ratio.

Unfortunately, there is an inherent limitation to this approach. No approximation algorithm for the LMP stage can do better than \(1+2/e\) [8], [9], and using the lower bound for bi-point rounding algorithms by [2], the best possible analysis cannot yield an approximation factor better than \((1+2/e)\sqrt{\phi}\approx 2.207\). This leaves a significant gap to the inapproximability lower bound of \((1+2/e)\approx 1.735\) [8], [9], and even to the best-known approximation algorithm that opens \(k\)-centers in expectation [1], which achieves an approximation guarantee of \(2-\eta\) for some small \(\eta>0\).

1.1 Our Results↩︎

Our main result is stated as follows. (As commonly done, we use "with high probability" to mean that an event occurs with probability at least \(1 - 1/\text{poly}(n)\).)

The algorithm in our main theorem combines two novel algorithms. First, we address the limitations of the bi-point rounding method by introducing a non-trivial variant of the classic Greedy algorithm [8], [9]. The Greedy algorithm can be highly adaptive in that tiny changes to the opening cost \(f\) may lead to vastly different solutions \(S\) and \(S'\), where \(|S| < k\) and \(|S'| > k\), forcing previous bi-point rounding approaches to incur a large additional factor in the approximation guarantee. We resolve this high-adaptivity by presenting a low-adaptivity version, which makes adaptive decisions in only \(O(\log(n)/\varepsilon^2)\) phases. This modification intuitively renders the algorithm less adaptive than the original, where each choice depends heavily on previous ones. We then introduce a novel walk-between-solutions algorithm that enables us to return a solution with at most \(k + O(\log(n)/\varepsilon^2)\) centers, with no additional loss in the approximation factor (up to \(1 + \epsilon\)). Specifically, we achieve the following result.

Theorem [thm:pseudo-approx] is proved in Section 3, and an overview of the main ideas is given in Section 2.1. Combining this result with the [10] reduction from \(k\)-median pseudo-solutions to true \(k\)-median solutions already yields a \((2+\varepsilon)\)-approximation in quasi-polynomial time. In order to improve this to a polynomial time algorithm, we use a completely different algorithm. We say that an instance is \(\beta\)-stable if \(\text{opt}_{k-1} \geq (1+\beta)\cdot \text{opt}_{k}\). Our result is as follows.

The algorithm for stable instances is inspired by a recent fixed-parameter-tractable approach that essentially identifies, by enumeration, small-radius balls guaranteed to contain the optimal centers and then solves the problem by maximizing a submodular function subject to a partition matroid constraint. However, there are two major challenges: first, the running time of [12] is not polynomial even when \(k = O(\log n)\); and second, because \(k\) may be large (potentially polynomial in \(n\)), we need to identify almost all clusters of the optimal solution before proceeding with any guessing/enumeration steps. We address these challenges through several novel ideas, including a sampling approach based on the \(k\)-means++ algorithm. The proof of Theorem [thm:mainadditivecenters] is presented in Section 4, with an overview of the techniques provided in Section 2.2.

Let us see why Theorems [thm:pseudo-approx] and [thm:mainadditivecenters] combine to yield Theorem 1. We compute a few feasible solutions. Let \(\Delta\) be the surplus number of centers used in Theorem [thm:pseudo-approx]. Let \(k'=\max\{1,k-\Delta\}\). One solution is obtained by computing the optimum solution with one center for \(k'=1\), and otherwise by running the algorithm from Theorem [thm:pseudo-approx] with the number of centers being \(k' = k-\Delta\). If \(\text{opt}_{k'} \leq \text{opt}_k\cdot (1+\varepsilon)\), this is a good enough approximation. Then we run the algorithm from Theorem [thm:mainadditivecenters] for every \(k'' \in (k',k]\). If the solution with \(k'\) centers computed before is not good enough, then there exists some \(k'' \in (k',k]\) such that \(\text{opt}_{k''-1} \geq (1+\beta)\cdot \text{opt}_{k''}\) with \(\beta \in \Omega(\varepsilon/\Delta) = \Omega(\varepsilon^3/\log n)\) and \(\text{opt}_{k''}\leq (1+\varepsilon)\cdot \text{opt}_{k}\). In this case, Theorem [thm:mainadditivecenters] yields the desired result for a proper choice of the parameters. Outputting the best of all computed solutions yields Theorem 1.

For Euclidean spaces, the set of candidate centers is infinite. By a standard reduction, we can find a polynomial-sized set \(F\subset \mathbb{R}^d\) in polynomial time such that the cost of any constant factor approximate solution is approximated by a set of centers obtained from \(F\), see for example Lemma 5.3 of [13]. Thus we also obtain a \((2+\varepsilon)\)-approximation in Euclidean spaces, improving on \(2.406\) [14].

Finally, let us remark that Theorem 1 essentially closes the gap between the approximation guarantee of the best-known algorithm that opens \(k\) centers in expectation [1] and algorithms that consistently open at most \(k\) centers. However, a major open problem remains: obtaining a tight approximation result for \(k\)-median, as it is only known that it is hard to approximate the problem within a factor less than \((1 + 2/e)\) [8]. Building on this work, a natural next step would be to resolve this question or to significantly improve the approximation guarantee, even in the setting where \(k\) centers are opened in expectation.

1.2 Related Work↩︎

We already reviewed the LMP-based approximation algorithms earlier. But there are several other important results for \(k\)-median and closely related problems which we cover here.

There also exist other approaches for designing approximation algorithms for metric \(k\)-median, most notably local search [3], [15]–[17], combinatorial algorithms [18], metric embeddings [4], [5], [19], or other LP-based rounding approaches [20]–[22]. There has also been a lot of work for the related problems \(k\)-means and \(k\)-center, which minimize the sum of squared distances and the maximum distance, respectively. Specifically for \(k\)-center, [23], [24] gave a \(2\)-approximation which is optimal unless \(P\neq NP\). \(k\)-means admits a \((9+\varepsilon)\)-approximation in general metrics [25]. In addition, both \(k\)-median and \(k\)-means have been studied in \(d\)-dimensional Euclidean spaces, where a PTAS is possible when either \(d\) or \(k\) are fixed [13], [26]–[28]. If neither \(d\) nor \(k\) are fixed, the approximation factors for Euclidean \(k\)-median and \(k\)-means are also better than their general metric counterparts [25], [29], with the best known approximation ratio being \(5.913\) for \(k\)-means and, prior to our work, being \(2.406\) for \(k\)-median by [14]. Both in high dimensional Euclidean spaces as well as general metrics, all of these aforementioned problems are APX hard [8], [30]–[34].

LMP-based approaches are also very relevant for the related facility location problem. Mahdian et al. [35] showed that an LMP \((1+2/e)\)-approximation yields a \((\gamma_{GK} \approx 1.463)\)-approximation for UFL, which matches the hardness result of Guha and Khuller [36] where \(\gamma_{GK}\) is the solution of \(\gamma = 1 + 2e^{-\gamma}\). Nevertheless, most improvements do not rely on an LMP approach. Following a long line of research [8], [9], [35], [37]–[41], Li presented an algorithm with the currently best known approximation ratio of roughly \(1.488\) [42].

1.3 Preliminaries↩︎

We are given a set of \(n\) clients \(D\) and set of \(m\) potential centers or facilities \(F\). Given a set \(S\subseteq F\), we use \(d(j,S)=\min_{i\in S} d(j,i)\), where \(d\) is the underlying distance function. \(\tilde{O}(x)\) suppresses \(\text{polylog}(x)\) factors, and \(O_\varepsilon(x)\) suppresses polynomial factors in \(\varepsilon\). We use \([a]^+ = \max(a,0)\). We already defined the \(k\)-median problem. The uncapacitated facility location problem \((UFL)\) with uniform opening costs is given a non-negative number \(f\) and asks to find a set \(S\subseteq F\) minimizing \[\text{cost}_{UFL}(S)=\sum_{j\in D}d(j,S) + f\cdot |S|.\] We refer to \(\sum_{j\in D} d(j,S)\) as the connection cost and \(f\cdot |S|\) as the opening cost. Let \(x_{i,j}\) denote in the indicator variable for serving client \(j\) with facility \(i\) and let \(y_i\) be the indicator variable for opening facility \(i\). Relaxing these to continuous variables in \([0,1]\), the LP relaxation to \(k\)-median and UFL are given by the following equations:

The constraint \(\sum_{i\in F}x_{i,j}\geq 1\) ensures that every client is served by some facility and the constraint \(y_i-x_{i,j}\geq 0\) ensures that a client \(j\) can only be served by facility \(i\) if \(i\) is open. Moreover, the dual for the facility location LP relaxation is given by the equations: \[\begin{align} \max & \sum_{j\in D}\alpha_j & (DP_{UFL}(f))\\ s.t. & \sum_{j\in D} [\alpha_j - d(i,j)]^+ \leq f & \forall i\in F \\ & \alpha \geq 0 \end{align}\] The usual interpretation of the \(\alpha_j\) is that they are the budgets for each client, accounting for both connecting the client to a facility, as well as opening a facility. The opening contribution dual variables \(\beta_{i,j}\) obtained from the \(y_i-x_{i,j}\geq 0\) constraints, as well as the dual constraints \(\alpha_j - \beta_{i,j}\leq d(i,j)\) are removed here, as we can always set \(\beta_{i,j} = [\alpha_j-d(i,j)]^+\). Recall that \(\text{opt}=\text{opt}_k\) is the cost of an optimal \(k\)-median clustering. We use \(\text{opt}_{LP}\) and \(\text{opt}_{LP}(f)\) to denote the cost of an optimal solution to \(LP_{km}\) and \(LP_{UFL}(f)\), resp. Trivially \(\text{opt}\geq\text{opt}_{LP}\). Since any feasible solution for \(LP_{km}\) is also feasible for \(LP_{UFL}(f)\), one has \(\text{opt}_{LP}\geq \text{opt}_{LP}(f)-kf\). We will use the fact that, by weak duality, any feasible solution to \(DP_{UFL}(f)\) induces a lower bound on \(\text{opt}_{LP}(f)\). In particular, for any feasible solution \(\alpha\) to \(DP_{UFL}(f)\), we have \(\text{opt}\geq \text{opt}_{LP}(f) - kf\geq \sum_{j\in D} \alpha_j - kf\).

We say that an algorithm is a Lagrangian Multiplier Preserving (LMP) \(\alpha\)-approximation algorithm for UFL if it returns a solution \(S\) with \[\text{cost}(S)\leq \alpha\cdot (\text{opt}_{LP}(f)-f|S|).\]

Finally, we will make the assumption that the distances are integers in \([1,n^3/\varepsilon]\). The justification is given by the following standard reduction.

2 Technical Overview↩︎

In this section, we give an overview of our result. Section 2.1 introduces ideas behind Theorem [thm:pseudo-approx] that achieves a \((2+\varepsilon)\)-approximation while opening \(k + O(\log n / \varepsilon^2)\) centers, and Section 2.2 discusses Theorem [thm:mainadditivecenters] for stable instances.

2.1 \((2+\varepsilon)\)-Approximation with \(O_{\varepsilon}(\log n)\) Extra Centers↩︎

Let us motivate our high-level plan by revisiting the previous framework. The previous best approximation algorithms [1], [2], [11], lis13? for \(k\)-median start by the following initialization step: starting from two LMP approximate solutions for UFL \(S, S' \subseteq F\) with the respective facility costs \(f, f'\) such that \(|S| < k, |S'| > k\)⁸ and \(f\) possibly much larger than \(f'\), the algorithm uses binary search to obtain two new solutions \((S, f), (S', f')\) such that \(|S| < k, |S'| > k\) and \(|f - f'| \leq 2^{-n}\). This step can be already viewed as a merging step that takes two solutions whose number of facilities sandwich \(k\) and makes them (specifically the facility cost) closer. Then, the natural question is can we merge \(S\) and \(S'\) into the (almost) same set of open facilities so that both open (almost) exactly \(k\) facilities?

One naive implementation of this idea might be the following (from now on, let us assume \(f = f'\)). Just like binary search, suppose that we find an LMP approximate solution \(S''\) which is strictly between \(S\) and \(S'\) in some formal sense. If \(|S''| > k\), we will let \(S' \leftarrow S''\) and otherwise \(S \leftarrow S''\). Then the invariant \(|S| < k\), \(|S'| > k\) is maintained while the two solutions got strictly closer. So we can continue this process until they become the same!

Of course, the main question is whether one can find such \(S''\) given \(S\) and \(S'\). Just like \(S\) and \(S'\), \(S''\) must be an outcome of the LMP approximation algorithm, or at least close to such an outcome in some formal sense. Since being a valid outcome of an algorithm is a highly complex property, especially when the algorithm has a large number of adaptive steps whose action depends on the previous actions, this task remains challenging for a general LMP approximation algorithm.

However, there is an example of success for Jain and Vazirani’s primal-dual [7] algorithm, which gives a LMP \(3\)-approximation. At a high level, this algorithm consists of two phases, where the first phase yields a set \(T\) of tentative open facilities, and the second phase is allowed to choose an arbitrary \(S \subseteq T\) that forms a maximal independent set in an auxiliary graph, so there is a freedom in choosing the independent set. Ahmadian et al. [25] used this freedom to give a walking procedure that finds a maximal independent set in the auxiliary graph of cardinality exactly \(k\), which led to an improved approximation ratio for Euclidean \(k\)-means/\(k\)-median and metric \(k\)-means.

However, the Greedy algorithm [8], [9] with dual-fitting analysis, which guarantees a better \(2\)-LMP approximation, is more adaptive; in fact, it can be a completely deterministic algorithm without leaving any freedom. Therefore, in order to implement our idea, it would be better to find a low-adaptive version of the Greedy algorithm, where the algorithm runs in a small (\(O_{\varepsilon}(\log n)\) in our case) number of phases, and each phase presents some freedom of choices for the algorithm.

2.1.0.1 The Greedy Algorithm.

Let us recall the Greedy algorithm [8], [9]. The algorithm maintains the set \(A\) of active clients and the set \(S\) of open facilities. Initially, all clients are active, i.e., \(A = D\), and no facilities are opened, i.e., \(S = \emptyset\). Additionally, the algorithm maintains dual variables \((\alpha_j)_{j \in D}\), initialized to \(0\).

While there is at least one active client, the algorithm uniformly increases the \(\alpha\)-values of the active clients until there is a facility \(i\) whose "bids" are sufficient to open it (or an active client becomes “close” to an already opened facility). The bids from a client \(j\) to a facility \(i\) depend on whether \(j\) is active or not. If \(j \in A\), then a portion of its budget \(\alpha_j\), specifically \(d(i,j)\), is allocated to cover the connection cost, and the remainder, \(\alpha_j - d(i,j)\), is used to bid towards the facility’s opening cost \(\hat{f} := 2f\). For a client \(j \notin A\), which is already connected to an open facility at a distance \(d(j,S)\), the bid towards \(i\) is the difference in distance, i.e., \(d(j,S) - d(i,j)\) (or \(0\) if \(i\) is farther). Finally, the algorithm marks any client \(j\) with \(\alpha_j \geq d(j,S)\) as inactive, ensuring that at any point in time, active clients \(j\) satisfy \(\alpha_j \leq d(j,S)\).

In order to prove that the algorithm yields an LMP \(2\)-approximation, let \((\alpha^*_j)_{j\in D}\) be the final \(\alpha\) values and \(S^*\) be the set of opened facilities. The design of the algorithm guarantees that the \(\alpha^*\) values pay for both the opening costs of the facilities in \(S^*\) and the connection costs of the clients, leading to \(\sum_{j\in D} \alpha^*_j = \sum_{j\in D} d(j,S^*) + \hat{f} \cdot |S^*|\).

The more interesting part of the analysis is to show that \(\alpha^*/2\) is a dual feasible solution for the dual facility location LP with facility cost \(f\), namely \(\sum_{j \in D}[ \alpha^*_j - 2d(i,j)]^+ \leq \hat{f}\) for every facility \(i\). The dual feasibility follows from two key properties that, at any point in time, (a) \(\alpha_j \leq d(j, S)\) for every \(j \in A\) and (b) for every \(i \in F\), no facility is overbid: \[\sum_{j\in A} [\alpha_j - d(i,j)]^+ + \sum_{j\in D \setminus A} [d(j,S) - d(j,i)]^+ \leq \hat{f}\,. \label{eq:no-overbid-overview}\tag{1}\]

2.1.1 Logarithmic Adaptivity↩︎

As stated, the Greedy is a highly adaptive algorithm; for instance, consider the case when two facilities \(i\) and \(i'\) both become paid for at the same time \(\theta\). Whether we open \(i\) or \(i'\) can dramatically change the bids to future facilities and completely change the trace of the algorithm.

To reduce such high adaptivity, we limit the number of time steps where such decisions are made. Specifically, our high-level goal is to only consider the time steps of the form \((1+\varepsilon^2)^0, (1+\varepsilon^2)^1, (1+\varepsilon^2)^2, \ldots\). Then, as the minimum nonzero distance is \(1\) and the maximum distance is \(\mathrm{poly}(n)\), the total number of time steps that we need to consider is \(O(\log n /\varepsilon^2)\), and this is what we refer to as \(O(\log n)\) adaptivity.

The main difficulty in implementing this idea is to ensure 1 . Consider the situation where all active clients have \(\alpha\) value \(\theta = (1+\varepsilon^2)^t\). If their \(\alpha\) values jump from \(\theta\) to \((1+\varepsilon^2)\theta\), it is possible that a previously underbid facility becomes strictly overbid.

We fix this issue in two steps. The first easy fix is to scale down the metric by a factor of \((1-\delta)\) where \(\delta = O(\varepsilon)\); that is, we consider a facility \(i\) paid for if \[\sum_{j\in A} [\alpha_j - (1-\delta) d(i,j)]^+ + (1-\delta) \sum_{j\in D \setminus A} [d(j,S) - d(j,i)]^+ \geq \hat{f}\,. \label{eq:paid-overview}\tag{2}\] At the cost of losing a factor \(1/(1-\delta)\) in the approximation guarantee, this has the following benefit. If \(i\) is not paid according to 2 when all active clients have \(\alpha_j = \theta\), then even when \(\alpha_j\)’s are increased to \((1+\varepsilon^2)\theta\), for a client \(j\) with \(d(j, i) \geq \varepsilon\theta\), its contribution \([(1+\varepsilon^2)^{t+1} - d(i,j)]^+\) to 1 is at most its previous contribution \([(1+\varepsilon^2)^{t} - (1-\delta) d(i,j)]^+\) to 2 , which makes 1 unlikely to be violated.

Then our second fix deals with active clients close to co-located with \(i\). We do so by allowing the clients \(j\) in the ball \(B(i, \varepsilon\theta)\) to increase their bids for \(i\) up to \(\min((1+\varepsilon^2)\theta, (1-\delta)d(j,S))\), so that if \(i\) could not be opened even with increased bids from nearby clients, then increasing active clients’ \(\alpha\) values from \(\theta\) to \((1+\varepsilon^2)\theta\) should not make \(i\) overbid. These increased bids bring other considerations (e.g., ensuring dual feasibility of other facilities), leading to the following definition of openable facilities, which can be efficiently checked by a linear program.

Given this definition of openability, Section 3.2 presents our modified Greedy algorithm with \(O(\log n)\) phases, LogAdaptive, which is restated here as Algorithm 1. Here a phase is defined to be the run of the algorithm for a fixed value of \(\theta = 1, (1+\varepsilon^2), (1+\varepsilon^2)^2, \dots\), which is broken down to two stages according to the description of Algorithm 1. Note that at least in the beginning, stage 1 allows opening of any openable facility, providing the desired freedom to walk between two solutions within the phase. While stage 1 still presents some adaptivity as an opening of a facility might impact the openability of another, it is sufficient for the merging procedure described in Section 2.1.2.

For the analysis, in Section 3.3, we prove that LogAdaptive yields an LMP \((2+O(\varepsilon))\)-approximate solution for UFL. It is a nontrivial extension of the dual-fitting analysis of the Greedy algorithm for our definition of openability and design of the algorithm.

2.1.2 Merging Two Solutions↩︎

We describe our final algorithm MergeSolutions that maintains two LMP approximate solutions whose number of facilities sandwich \(k\) and gradually merges them until one of them opens almost exactly \(k\) facilities.

2.1.2.1 Setup.

Based on the discussion about LogAdaptive, we will describe a solution \(\mathcal{H}\) as \((H_1, \dots, H_L)\) with \(L = O(\log n / \varepsilon^2)\), where \(H_i\) is a valid execution of stage 1 of phase \(i\) (i.e., when \(\theta = (1+\varepsilon^2)^{i-1}\)), which is formally represented as a sequence of opened facilities. \(H_i\)’s validity also requires maximality, meaning that no openable facility remains in the phase. In order to facilitate the merging, given a phase, we extend the notion of a valid execution to include the following actions.

• We allow opening a free facility, at most three times per phase. A free facility \(\tilde{i}\) is based on a regular facility \(i \in F\), and when it is created, we can choose the distance parameter \(u(\tilde{i}) = d(\tilde{i}, i)\). All other distances \(d(\tilde{i}, x)\) are defined to be \(u(\tilde{i}) + d(i, x)\).

• We slightly relax the notion of openability so that one can open a facility \(i\) by paying \(\hat{f} - n \eta\) instead of \(\hat{f}\) for parameter \(\eta := 2^{-n}\) (in the third bullet of Definition 1).

Call \(\mathcal{H}= (H_1, \dots, H_L)\) a solution of \(\eta\)-valid sequences if \(H_i\) is a valid execution (i.e., an \(\eta\)-valid sequence) of the \(i\)th phase in the above relaxed notion given \(H_1, \dots, H_{i-1}\). We extend the analysis of LogAdaptive in Appendix 5 to show that such \(\mathcal{H}\) in the above sense still yields an LMP \((2+O(\varepsilon+ n\eta))\)-approximation, if we do not count the opening cost of the free facilities (while using the connections they provide). Therefore, a solution of \(\eta\)-valid sequences that opens exactly \(k\) regular facilities, and at most \(3\) free facilities per phase, is a \((2+O(\varepsilon+ n\eta))\)-approximation to \(k\)-median that opens at most \(O(L) = O(\log n/\varepsilon^2)\) extra facilities.

Initially, by the standard binary search on the facility cost and running LogAdaptive, we start with two solutions \(\mathcal{H}= (H_1, \dots, H_L)\) and \(\mathcal{H}' = (H'_1, \dots, H'_L)\) with facility costs \(f\) and \(f'\) such that \(|f - f'| \leq \eta\) and their numbers of opened facilities sandwich \(k\). (We will associate parameters \((f, u)\) for \(\mathcal{H}\) and \((f', u')\) for \(\mathcal{H}'\). Also, note that every facility in \(\mathcal{H}\) (resp. \(\mathcal{H}'\)) has cost \(f\) (resp. \(f'\)).) Throughout the algorithm, we will maintain the invariants that (1) \(\mathcal{H}\) and \(\mathcal{H}'\) open the same set of free facilities (so that \(u\) and \(u'\) are defined on the same set), (2) their number of opened regular facilities sandwich \(k\), and (3) \((f, u) = (f', u')\) except for one parameter \(f\) or \(u(\tilde{i})\) for one free \(\tilde{i}\), whose values in the two solutions differ by at most \(\eta\). Call such a parameter the difference parameter.

For each \(i = 1, \dots, L\), we will outline a procedure that, given that the prefixes \((H_1, \dots, H_{p-1})\) and \((H'_1, \dots, H'_{p-1})\) are identical, modifies the suffixes \((H_p, \dots, H_L)\) and \((H'_p, \dots, H'_L)\) such that \(H_p\) and \(H'_p\) become identical while satisfying the above invariants, unless we already find a solution that opens exactly \(k\) regular facilities. This will allow us to gradually merge the solution until one of them opens exactly \(k\) regular facilities (and at most \(O(L)\) free facilities).

2.1.2.2 How to walk in each phase.

Finally, we focus on phase \(p\) and introduce ideas behind ensuring \(H_p = H'_p\). Our first step is to change the difference parameter value of \(\mathcal{H}'\) to that of \(\mathcal{H}\); formally, we let \(\mathcal{H}'' = \mathrm{\small CompleteSolution}_{(f, u)} (H'_1, \dots, H'_p)\), which is the solution resulting from running LogAdaptive from a given partial solution \((H'_1, \dots, H'_p)\) with parameters \((f, u)\) instead of \((f', u')\). Such a change of the difference parameter is the reason for introducing the \(n\eta\) slack for \(\eta\)-valid sequences; for instance, if \(H_i\) was the exact execution with parameters \((f' ,u')\), our Claim 2 shows that it is still \(\eta\)-valid with respect to \((f, u)\).

If \(\mathcal{H}''\) opens \(k\) regular facilities we are done. Also, if the number of open regular facilities of \(\mathcal{H}''\) and \(\mathcal{H}'\) sandwich \(k\), then we already made progress as they now coincide on the \(p\)th phase while still having one difference parameter. Therefore, we only need to handle the case where \(\mathcal{H}''\) and \(\mathcal{H}\) sandwich \(k\), where the difference parameters already became identical but \(H_p\) and \(H'_p\) are different. Let us rename \(\mathcal{H}''\) to \(\mathcal{H}'\).

Now our goal is to gradually change \(H'_p\) to \(H_p\) (i.e., walk from \(H'_p\) to \(H_p\)). Instead of describing the full procedure, which is outlined in Section 3.5, we illustrate the procedure on a particular example. Suppose that \(H_p = \langle i_1 \rangle\), \(H'_p = \langle i_2, \dots, i_{6} \rangle\) where one can open at most one between \(i_1\) and \(i_j\) for any \(j \in \{2, \dots, 6 \}\); this constraint can be expressed as a star graph with \(i_1\) as the center vertex and \(i_2, \dots, i_6\) are only connected to \(i_1\), and a valid solution (i.e., \(\eta\)-valid sequence) here means a maximal independent set. (Suppose that this is the only constraint on openings, so \(H_p\) and \(H'_p\) can be thought of as sets instead of sequences.)

In this example, \(H_p\) and \(H'_p\) are the only two maximal independent sets, so it is impossible to smoothly walk from \(H'_p\) to \(H_p\). Here is where the notion of a free facility becomes useful because we can assume that having a free facility helps maximality while not hurting independence. Then, from \(H'_p\), by (Step 1) adding a free copy of \(i_1\) called \(\tilde{i}_1\) with \(u(\tilde{i}_1) = 0\), (Step 2) removing \(i_2, \dots, i_6\) one-by-one, and (Step 3) converting \(\tilde{i}_1\) to a regular \(i_1\), we obtain a sequence of maximal independent sets where a consecutive pair of independent sets differ by at most one facility. Figure 2 illustrates this process.

For each intermediate \(H'_p\), we consider its completion (i.e., \(\mathrm{\small CompleteSolution}_{(f, u)} (H'_1, \dots, H'_p)\)) and see how many regular facilities it opens. Since the completions from the initial \(H'_p\) and \(H_p\) sandwich \(k\), there must be a consecutive pair in the above sequence of independent sets (say \(H^{a}_p\) and \(H^b_p\)) that sandwich \(k\), and they differ by only one facility \(i_q\) (say \(H^{a}_p\) contains \(i_q\) while \(H^b_p\) does not). For future execution of the algorithm, \(H^{a}_p\) and \(H^{b}_p\) are the same as the solutions that have the free copy \(\tilde{i}_q\) (instead of \(i_q\)) with the \(u(\tilde{i}_q)\) value \(0\) (for \(H^{a}_p\)) and \(\infty\) (or sufficiently large number, for \(H^{b}_p\)). Therefore, by performing binary search on the \(u(\tilde{i}_q)\), just like we do on the facility cost \(f\), we yield two solutions that are now identical up to phase \(p\) except the \(\eta\) difference on the only one different parameter \(u(\tilde{i}_q)\), which archives our goal of merging two solutions at phase \(p\)! In general, the fact that \(H_p\) and \(H'_p\) are not just sets but sequences of opened facilities requires more technical consideration. However, the full procedure is still an extension of this idea, trying to increase the length of the common prefix between \(H_p\) and \(H'_p\) by walking from \(H'_p\) to \(H_p\) by one coordinate at a time, until two consecutive solutions are sandwiching \(k\).

2.2 \((2+\varepsilon)\)-Approximation for \(O_\varepsilon(\frac{1}{\log n})\)-Stable Instances↩︎

The other component of our algorithm is an improved approximation to \(k\)-median assuming that the instance has a weak version of a structural property known as stability, initially formulated by [43]. Recall that an instance is \(\beta\)-stable if \(\text{opt}_{k-1}\geq (1+\beta)\text{opt}_k\). For any \(\beta\)-stable instance, [44], [45] showed how to obtain a PTAS for the problem in time \(n^{\beta^{-1}\varepsilon^{-O(1)}}\) and [44] left as an open question as whether one could obtain a PTAS with running time \(f(\beta,\varepsilon)n^{O_{\varepsilon}(1)}\) for any computable function \(f\) for general metrics (they show it is possible for Euclidean metrics). We would indeed like to have an algorithm running in time \(2^{\text{poly}(\beta, \varepsilon)} n^{O_{\varepsilon}(1)}\) to solve our \((\varepsilon/ \log n)\)-stable instances.

Unfortunately, since any \(k\)-median instance is \(\Omega(1/k)\)-stable, obtaining a PTAS with the above running time would violate Gap-ETH [12]: The \(k\)-median problem cannot be approximated better than \(1+2/e\) in time \(f(k,\varepsilon) n^{O_\varepsilon(1)}\) assuming Gap-ETH.

The saving grace here is that we are not after a \((1+\varepsilon)\)-approximation algorithm but we can use any \((2+O(\varepsilon))\)-approximation with the above running time. Since a connection between \(\beta\)-stable and FPT algorithm exists (as explained in the above discussion), it is tempting to make the journey from FPT algorithms back to \(\beta\)-stable instances and use the state-of-the-art approximation algorithm of [12] to solve \(\beta\)-stable instances. Unfortunately the algorithm presented in [12] runs in time \((\log n)^{\tilde{O}(k/\varepsilon)} n^{O(1)}\) and so importing the techniques directly would result in a running time of the form \((\log n)^{\tilde{O}((\beta/\varepsilon)^{-1})} n^{O(1)}\) and not to a polynomial running time for our setting. We must thus go beyond the state-of-the-art techniques for FPT and \(\beta\)-stable \(k\)-median instances.

2.2.1 Local Optima and Stability↩︎

One particularly important tool when dealing with stable solutions are properties of local optima. The local search procedure starts with any feasible solution \(S\), and searches for an alternative solution \(S'\) such that \(|S\triangle S'|= 2\) (i.e., \(S\) and \(S'\) differ by one center) and \(\text{cost}(S')< \text{cost}(S)\). If such an \(S'\) exists, \(S\) is replaced by \(S'\) and the process is iterated. At the end of the procedure we say that \(S\) is locally optimal. The running time of this procedure is polynomial, where we exploit the assumption that distances are polynomially bounded integers (by Lemma 1).

We first introduce a bit of notation. Suppose we are given a locally optimal solution \(S\). We say that a cluster \(C^*\) of the optimal solution \(\text{OPT}\) is pure with respect to \(S\), if there exists a cluster \(C'\) induced by \(S\) such that both clusters agree on all but \(O(\varepsilon)\cdot \min(|C^*|,|C'|)\) of the points. We begin by examining structural properties for \(\beta\)-stable solutions, summarized by in Section 4.1.

• For any given constant-factor approximation \(S\), at most \(O_\varepsilon(\beta^{-1})\) many clusters are not pure, see Lemma 10.

• In any locally optimal solution \(S\), we have \[\sum_{p\in C^*,~C^* \text{ pure}} d(p,S) \leq \sum_{p\in C^*,~ C^* \text{ pure}} d(p,\text{OPT}) + O(\varepsilon)\cdot \text{opt},\] that is the cost of the clients in pure clusters is well approximated.

More precisely, in the second bullet we show that all the points in each pure cluster \(C^*\) with center \(c^*\) can be assigned to the same center \(t(c^*)\) in \(S\) (i.e., the center \(c'\) of \(C'\)) with a moderate increase of their cost (see Lemma 11).

The first property relies on the fact that for every non-pure cluster, \(S\) must merge at least two clusters of the optimum. If \(S\) is a constant-factor approximation, this cannot happen more than \(O_{\varepsilon}(\beta^{-1})\) many times before the approximation guarantee no longer holds. The second property is implied by the local optimality of \(S\). Specifically, swapping out the center \(c'\in S\) serving \(C'\) for the center \(c^*\) of the pure cluster \(C^*\) cannot change the cost by much as these two clusters agree on most of their points.

In a nutshell, a locally optimal solution \(S\) approximates all but \(O_{\varepsilon}(\beta^{-1})\) many clusters of the optimal solution very well. In what follows, we will describe how we may extend \(S\) to a \((2+\varepsilon)\)-approximation overall.

2.2.2 Identifying the Non-Pure Clusters↩︎

To find a good approximation for the non-pure clusters, we would like to identify these clusters. By the above discussion, we may assume that we have a locally optimal solution \(S\) for which all but \(O_\varepsilon(\beta^{-1}) = O_\varepsilon(\log n)\) many clusters are well approximated. Immediate ideas, such as determining the badly approximated clusters by brute force, will not improve over the quasi-polynomial running time. Instead, we look towards fixed parameter tractable (FPT) approaches, parameterized by the number of centers. In fact, we would like an FPT approximation algorithm parameterized by the number of non-pure clusters. Starting point is an FPT algorithm based on submodular maximization, initially due to [12], which we first review. However, recall that the running time of this algorithm is \((\log k)^{\tilde{O}(k\varepsilon^{-1})}\) and so will not be enough for our purpose. We thus introduce new ideas to speed things up.

2.2.2.1 Review of the FPT approximation algorithm of [12].

Suppose \(c^*\) is a center of cluster \(C^*\) in an optimal solution \(\text{OPT}\). [12] introduce the notion of a leader client \(\ell\in C^*\) which minimizes the distance to \(c^*\). Using coresets to first reduce the number of clients to \(\tilde{O}(k\log n/\varepsilon^{2})\), the leaders of all clusters, as well as the distances \(d(\ell,c^*)\) can be identified in FPT-time, i.e. in time \((\log n)^{\tilde{O}(k \varepsilon^{-1})} \cdot n^{O(1)}\). A solution \(S\) obtained by simply selecting an arbitrary facility within distance \(d(\ell,c^*)\) from \(\ell\) yields a \(3\)-approximation. [12] improve upon this by showing that for any two candidate sets of centers \(S'\) and \(\Lambda\) \[\text{cost}(\Lambda)-\text{cost}(\Lambda\cup S')\] is a monotone submodular function.

The first part which consists in guessing the leaders is the computational bottleneck since optimizing a monotone submodular function can be done in polynomial time.

We next describe how we deal with the clusters that are not well approximated. Recall that we first compute a locally optimal solution \(S\). By the properties of local optima, \(S\) is already a sufficiently good solution for the pure clusters. For the remaining \(O_\varepsilon(\log n)\) non-pure clusters, we only have coarser approximation bounds.

2.2.2.2 Leader Identification in Polynomial Time via \(D^2\)-Sampling – Sections 4.2 and 4.3.

Our next high-level goal is to find leaders of the non-pure clusters and guess their (approximate) distances to the respective optimum centers in time \(2^{\beta^{-1}\varepsilon^{-O(1)}} n^{O(1)}\) for \(\beta\)-stable instances.

[12] identify leaders in time \({k\log n \choose k}\) by sparsifying the instance via coresets and then determining the distance of leaders to the optimal solution in time \((\log n)^k\). Our overall approach significantly speeds up these two steps by way of distance sampling similar to \(k\)-means++ [46].

To identify the leaders faster, we lift the stringent requirement that the leader of cluster \(C^*\) is the client closest to the center \(c^*\) in the optimal solution. Instead, we consider any client among the \(\varepsilon\cdot |C^*|\) closest points to \(c^*\) as a valid leader with \(\text{avg}_{C^*, \text{OPT}}\) being the maximum distance of any leader of \(C^*\) to \(c^*\). We later show that this only induces a minor cost increase in the total approximation bound.

The second relaxation is that we only aim to target clusters that are sufficiently expensive in our locally stable solution \(S\). More precisely, a non-pure cluster \(C^*\) with center \(c^*\) is basic-cheap if (a) the total cost of its leaders in \(S\) is at most \(\varepsilon^{O(1)}\cdot\beta \cdot \text{opt}= \frac{\varepsilon^{O(1)}}{\log n} \cdot \text{opt}\) or (b) \(d(c^*,S)\leq (1+\varepsilon)\text{avg}_{C^*, \text{OPT}} +\frac{\varepsilon}{|C^*|} \cdot \sum_{p\in C^*}(d(p,c^*)+d(p,S))\). Then we can show that \(S\) is already an almost \(2\)-approximation for these clusters modulo some additive slack, namely \[\sum_{p\in C^*,~C^* \text{ basic-cheap}} d(p, S) \leq 2 \sum_{p\in C^*,~C^* \text{ basic-cheap}} d(p, \text{OPT}) + O(\varepsilon\cdot \text{opt}).\] More precisely, similarly to the case of pure clusters, we can show that all the points of a basic-cheap cluster can be reassigned to the center \(t(c^*)\in S\) which is closest to \(c^*\) with an increase of the cost of the above type (see Lemma 13). Indeed, by triangle inequality \(d(p, S) \leq d(p, c^*) + d(c^*, S)\) for any \(p\). If \(C^*\) is basic-cheap by condition (b), one directly obtains the desired upper bound on \(d(c^*, S)\). Otherwise, i.e. if \(C^*\) is basic-cheap by condition (a), we use the fact that the number of basic-cheap clusters (which is at most the number of non-pure clusters) is \(\frac{\log n}{\varepsilon^{O(1)}}\) so the sum of their costs in \(S\) is \(O(\varepsilon\cdot \text{opt})\). This essentially allows us to focus only on non-pure and non-basic-cheap clusters.

We use these two relaxations as follows. Let \(W\) be a sample of clients picked independently and proportionately to \(\frac{d(p,S)}{\text{cost}(S)}\). With probability \(\varepsilon^{O(1)}/\log n\), we are picking a leader from a given non-pure, non-basic cheap cluster: in this case we say that \(C^*\) is hit by the sample. Thus, when picking \(O_\varepsilon(\log n)\) samples, we have picked a leader from all but a small fraction of non-pure, non-basic cheap clusters. Thereafter, we can show that with good probability, we can assign all the points of a non-pure non-basic-cheap non-hit cluster \(C^*\), with center \(c^*\), to the center \(t(c^*)\in S\) which is closest to \(c^*\) with a small cost (see Lemma 12 in Section 4.2). We next call expensive the non-pure non-basic-cheap clusters which are hit, and cheap the non-pure clusters which are either basic-cheap or non-basic-cheap and non-hit. Thus the clusters are partitioned into pure, cheap and expensive ones. Since we have sampled \(O_\varepsilon(\log n)\) clients, we can enumerate all the subsets in polynomial time and focus on a subset that contains exactly one leader of each expensive cluster.

Using a constant number of potential guesses per leader, we then show how to get a sufficiently good approximation of the distance \(\rho\) from each leader to its closest optimum center, see Lemma 15 in Section 4.3. Intuitively, the cost of the leader in solution \(S\) is a rough approximation of \(\rho\), so we can interpolate around it.

2.2.2.3 Existence of a Good Solution.

We now use \(W\) from last section to identify a modified solution from \(S\) that is \((2+O(\varepsilon))\)-approximate. Let \(\hat{OPT}\) denote the set of centers of expensive clusters. The cost of all the other optimal clusters, i.e., the pure and cheap ones, is within a factor roughly \(2\) from the optimum. We thus wish to add to \(S\) the optimal centers of \(\hat{\text{OPT}}\) and remove an equally sized set \(S_0\subseteq S\). An important constraint on \(S_0\) is that it contains no center \(t(c^*)\), where \(c^*\) is the center of an optimal cluster which is pure or cheap. Intuitively, such centers \(t(c^*)\in S\) guarantee that the cost of points in pure and cheap clusters is within a factor roughly \(2\) from the optimum. More precisely, in Lemma 16 we show that such an \(S_0\) exists so that \(M_O := S - S_0 \cup \hat{\text{OPT}}\) is a \((2+O(\varepsilon))\)-approximation: If a cluster of \(\text{OPT}\) is pure or cheap, there is one center \(t(c^*)\) in \(S-S_0\) serving their clients up to a \(2+O(\varepsilon)\) factor; for the remaining ones, we would have their optimum center (in \(\hat{\text{OPT}}\)).

So our goal from now on is to approximate the solution \(M_O\), where \(|S_0| = \hat{\text{OPT}} = O_{\varepsilon}(\log n)\), and this final goal has two key components: (1) removing some existing centers from \(S\) and (2) adding the centers from \(\hat{\text{OPT}}\). The issue is that stated as such this seems as hard as solving the \(k\)-median problem. We first address (1), and we will address (2) by making use of the leaders we have correctly guessed for the centers in \(\hat{\text{OPT}}\) at the previous steps.

2.2.2.4 Center Removal.

Let us first try to address (1). Remember we start with solution \(S\), and the leader and radii guesses from the previous steps. The key issue with (1) is that the clients in some of the clusters we would like to remove (i.e., served by \(S_0\) in solution \(S\)) are actually served by a center in \(\hat{\text{OPT}}\), but we do not know which are these centers yet! We will thus make use of some approximate loose bound on their cost in solution \(S - S_0 \cup \hat{\text{OPT}}\) by introducing dummy centers \(\Lambda\). For each leader \(\ell\) and guessed distance/radii \(\rho\), we will introduce a dummy center at distance \(\rho\) from \(\ell\) and at distance \(d(p, \ell) + \rho\) from any other vertex \(p\).

If we promise to open a center in the ball of radii \(\rho\) around \(\ell\) – which solution \(S - S_0 \cup \hat{\text{OPT}}\) does – then we will guarantee that there will be a center not further away than the dummy centers in the final solution. We now work with this solution \(S \cup \Lambda\) which provides a worst-case fall back on where the centers in \(\hat{\text{OPT}}\) could be. We can show that \(M_D := S \cup \Lambda- S_0\) is a \((3+O(\varepsilon))\)-approximate solution.

Equipped with this we proceed to our 3-step center removal. We know that we have at most \(|S_0| = O_{\varepsilon}(\log n)\) centers we need to remove. Our first procedure (see Section 4.4) aims at removing the centers of clusters of high cost in \(S_0\). Start with solution \(S \cup \Lambda\). For \(O_{\varepsilon}(\log n)\) times, we sample a center \(c\in S\) proportionally to the cost of its cluster in solution \(S \cup \Lambda\), remove \(c\) from \(S\) with probability \(1/2\), and repeat on the resulting solution. Let \(\mathcal{Q}\) be the centers removed from \(S\). Then with probability at least \(2^{-O_{\varepsilon}(\log n)}\) the procedure succeeds by either obtaining \(\mathcal{Q}=S_0\) or ensuring that the total cost of the clusters of \(S_0-\mathcal{Q}\) in the solution is at most \(O(\varepsilon\cdot \text{opt})\). This indeed follows from the fact that, if we only removed centers \(\mathcal{Q}\subseteq S_0\) up to a certain step, the solution is never more than a \((3+O(\varepsilon))\)-approximation (since \(S \cup \Lambda- S_0\) is a \((3+O(\varepsilon))\)-approximation) and so the probability of sampling a new center of \(S_0-\mathcal{Q}\) is \(\Omega(\varepsilon)\), unless the total cost of the clusters of \(S_0-\mathcal{Q}\) is small. Therefore, repeating the process \(n^{O_\varepsilon(1)}\) times, we have that one of the runs succeeds with high probability.

Thus, after this step, we have removed a set \(\mathcal{Q}\) of centers of \(S_0\) and the total cost of the clusters of \(S_0-\mathcal{Q}\) is \(O(\varepsilon\cdot \text{opt})\). Following this procedure, we only have to remove inexpensive clusters. While here it is not possible to identify the correct ones, making a mistake is not too costly. For any \(c\in S_0-\mathcal{Q}\), we can now think of its whole cluster as being assigned entirely to a unique center in \(S - S_0 \cup \hat{\text{OPT}}\) since by triangle inequality this would only increase its cost by \(O(\varepsilon\cdot \text{opt})\) in total. We can thus think of the remaining centers \(S_0-\mathcal{Q}\) as either being assigned to \(\hat{\text{OPT}}\) (we call this set \(\mathcal{R}\)), or to a center in \(S - S_0\) (we call this set \(\mathcal{U}\)). Suppose we know how many centers fall into these two types, a figure we determine by trying all possibilities. The next step would be ideally to remove \(\mathcal{U}\). We instead remove a proxy \(\widetilde{\mathcal{U}}\) of \(\mathcal{U}\), \(|\widetilde{\mathcal{U}}|=|\mathcal{U}|\)(see Section 4.5). A natural starting point to find a center for reassignment is to do so by greedily removing the center \(c\) for which the reassignment cost is minimized. However, we must be careful. First, the reassignment costs are dynamic, that is when removing a center, it affects reassignment costs of subsequently removed ones. Second, if a center \(c\) was used to bound the reassigment cost of an deleted center, we cannot delete it later in order to prevent the error from adding up. We design a procedure that produces a \(\widetilde{\mathcal{U}}\) satisfying all these constraints (see Lemma 20). We remark that \(\widetilde{\mathcal{U}}\cap \mathcal{R}=\emptyset\), hence removing \(\mathcal{R}\) is still a valid option in the later stages.

Thus, for the purpose of analysis (the algorithm does not know \(\mathcal{R}\)), we obtain the solutions \(M_D' = S- (\mathcal{Q}\cup \widetilde{\mathcal{U}}\cup \mathcal{R}) \cup \Lambda\) and \(M_O' = S- (\mathcal{Q}\cup \widetilde{\mathcal{U}}\cup \mathcal{R}) \cup \hat{\text{OPT}}\). Moreover, the costs satisfy \(\text{cost}(M_O')+\text{cost}(M_D')\leq (4+O(\varepsilon))\text{OPT}\), which is the same as summed up costs of \(M_O\) and \(M_D\), see Lemma 19 and Claim 7.

2.2.2.5 Improvement via Submodular Maximization.

We can now use submodular maximization techniques (specifically algorithms to maximize a submodular function over a partition matroid constraint) in a similar but more general setting as in the work of [12]. In more detail, we wish to find the best \(|\hat{\text{OPT}}|\) centers \(X\) to open (instead of the dummy centers \(\Lambda\)), one at the prescribed distance from each leader, to improve the cost of \(M_D'\) as much as possible. This is almost identical to the work of [12] except that we also need to close \(|\mathcal{R}|\) other centers \(\widetilde{\mathcal{R}}\) in \(S-\mathcal{Q}-\widetilde{\mathcal{U}}\). Ideally, we would like to open \(\hat{\text{OPT}}\) and close \(\mathcal{R}\). We show that selecting a good enough pair \((X,\widetilde{\mathcal{R}})\) can be reduced to a submodular maximization problem under a partition matroid constraint. In particular, we carefully define our submodular function so that its value, for a given subset \(X\) of centers, is calculated by optimally selecting the set \(\widetilde{\mathcal{R}}\) to close (for the choice \(X\)). Then we can use state-of-the-art algorithms to optimize this and simultaneously approximate the centers \(\hat{\text{OPT}}\) to open and the set \(\mathcal{R}\) to close.

3 \((2+\varepsilon)\)-Approximation with \(O(\log n /\varepsilon^2)\) Extra Centers↩︎

In this section, we present a polynomial-time algorithm that opens \(k+ O(\log n/\varepsilon^2)\) many centers and returns a solution of cost at most \((2+\varepsilon)\text{opt}\). We restate the theorem for convenience of the reader.

Our algorithm is a non-trivial extension of the Greedy algorithm with dual fitting analysis [8], [9], next called Greedy, so as to guarantee that we only open \(k+ O(\log n/\varepsilon^2)\) centers instead of only doing so in expectation. We first recall the basics of Greedy  in Section 3.1. Section 3.2 presents a modified algorithm LogAdaptive that runs in \(O(\log n / \varepsilon^2)\) adaptive steps (that we call phases) and Section 3.3 analyzes the latter algorithm.

Finally, building on additional setups in Section 3.4, Section 3.5 presents our final algorithm MergeSolutions achieving the guarantee of Theorem [thm:pseudo-approx]. It is an extension of LogAdaptive maintaining two solutions that open at least and at most \(k\) centers respectively, while opening at most three free centers per phase; this replaces the bipoint rounding [2], [7], [10], [11] and directly returns a \((2+\varepsilon)\) approximation that opens at most \(k + O(\log n /\varepsilon^2)\) centers. Its analysis, which is an extension of the analysis of Section 3.3, is presented in Appendix 5.

3.1 Review of the Greedy Algorithm↩︎

In this section, we provide a brief overview of the classic \(2\)-approximate LMP algorithm from [8], [9]. Our algorithms are derived by modifying this procedure, and these modifications become more intuitive when we revisit the basic concepts of the original algorithm. We present it in Algorithm 3 as a primal-dual algorithm to emphasize the changes we introduce.

The algorithm maintains the set \(A\) of active clients and the set \(S\) of opened facilities. Initially, all clients are active, i.e., \(A = D\), and no facility is open, i.e., \(S = \emptyset\). Additionally, the algorithm maintains an approximately feasible dual solution \(\alpha\), where each client \(j \in D\) has a corresponding value \(\alpha_j\). These values are initialized to \(0\).

While there is at least one active client, the algorithm uniformly increases the \(\alpha\)-values of the active clients until there is a facility \(i\) whose "bids" are sufficient to open it or an active client “gets connected” to an already opened facility. The bids from a client \(j\) to a facility \(i\) depend on whether \(j\) is active or not. If \(j \in A\), then a portion of its budget \(\alpha_j\), specifically \(d(i,j)\), is allocated to cover the connection cost of \(j\), and the remainder, \(\alpha_j - d(i,j)\), is used to bid towards the facility’s opening cost \(\hat{f}:=2f\). For a client \(j \notin A\), which is already connected to an open facility at a distance \(d(j,S)\), the bid towards \(i\) is the difference in distance, i.e., \(d(j,S) - d(i,j)\) (or \(0\) if \(i\) is farther away from \(j\) than \(S\)).

Finally, the algorithm marks any client \(j\) with \(\alpha_j \geq d(j,S)\) as inactive, ensuring that at any point in time, active clients \(j\) satisfy \(\alpha_j \leq d(j,S)\).

An overview of the analysis of Greedy is as follows. We consider the final \(\alpha\)-values denoted by \((\alpha^*_j)_{j\in A}\), and the final set \(S^*\) of opened facilities. The definition of the bids is to guarantee that the \(\alpha^*\)-values pay for both the opening costs of the facilities in \(S^*\) and the connection costs of the clients:

This is complemented by showing that \(\alpha^*/2\) is a feasible dual solution.

To prove dual-feasibility, two key properties are used:

No overbidding:

At any point in time, for every \(i\in F\), \[\begin{gather} \sum_{j\in A} [\alpha_j - d(i,j)]^+ + \sum_{j\in D - A} [d(j,S) - d(j,i)]^+ \leq \hat{f}\,. \end{gather}\]

No active clients bid on open facilities:

At any point in time, \(\alpha_j \leq d(j, S)\) for \(j\in A\).

Specifically, if we give a total order of the clients so that \(j\leq \ell\) if \(\alpha^*_j \leq \alpha^*_\ell\), the above two properties are used to prove the following technical lemma; intuitively, at time right before \(\alpha^*_{\ell}\), client \(j \in D-A\) satisfies \(d(j, S) + d(j, i) + d(i, \ell) \geq \alpha^*_{\ell}\), which implies \(d(j, S) - d(j, i) \geq \alpha^*_{\ell} - 2d(i, j) - d(i, \ell)\).

Lemma 3 then follows by summing up the above inequality for all \(\ell\in D\). Let \(\text{opt}_{\text{LP}}(f)\) be the value of an optimal solution to the linear programming relaxation when opening costs are \(f\). Then, we get the following theorem by combining Lemma 2 and Lemma 3.

Recall that \(\text{opt}_{\text{LP}}(f) - f\cdot k\) is a lower bound on the optimal solution to the \(k\)-median problem (see Section 1.3). Hence, if Greedy outputs a solution \(S^*\) such that \(|S^*| = k\), then it is a 2-approximate solution to \(k\)-median. Moreover, we can always set \(f\) high enough so that any good solution opens at most \(k\) facilities and \(f\) low enough so that any good solution opens at least \(k\) facilities. Thus, a simple binary search can find values \(f\) and \(f'\) such that running Greedy with opening costs \(f\) opens \(k_1 \geq k\) facilities, while running it with opening costs \(f'\) opens \(k_2 \leq k\) facilities. However, even though we can ensure that \(|f - f'|\) is exponentially small, say \(1/2^n\), it turns out that Greedy is quite unstable, and we may have \(k_1 \ll k\) and \(k_2 \gg k\), which does not directly imply anything useful for \(k\)-median. In other works, this has been addressed through an additional rounding algorithm called bi-point rounding, which introduces an extra factor into the approximation guarantee. In contrast, we modify Greedy into a similar algorithm that is “smoother” and less adaptive in its selection of facilities to open.

3.2 LogAdaptive↩︎

It is natural to think of the Greedy as increasing the \(\alpha\)-values of active clients with a time \(\theta\). That is, we always have \(\alpha_j = \theta\) for \(j\in A\). A difficulty in ensuring that Greedy opens \(k\) facilities is that it is a very adaptive algorithm. To see this, consider the case when two facilities \(i\) and \(i'\) both become paid for at the same time \(\theta\). Whether we open \(i\) or \(i'\) can dramatically change the bids to future facilities and completely change the trace and what facilities are opened by the algorithm. Our idea to overcome this difficulty is to limit the number of time steps where such decisions are made, thus lowering the adaptivity of the algorithm. Specifically, our high-level goal is to only consider the time steps of the form \((1+\varepsilon^2)^0, (1+\varepsilon^2)^1, (1+\varepsilon^2)^2, \ldots\). Then, as the minimum nonzero distance is \(1\) and the maximum distance is \(\mathrm{poly}(n)\), the standard arguments (formalized in Section 3.5) imply that the total number of time steps that we need to consider is \(O(\log(n)/\varepsilon^2)\), and this is what we refer to as \(O(\log n)\) adaptivity.

The difficulty in only considering those time steps is that we easily lose the property that we never overbid a facility \(i\), which is crucial in the analysis of Greedy. Indeed, consider a time step \(\theta = (1+\varepsilon^2)^t\) and let \(A\) and \(I\) be the current active and inactive clients, respectively. Now, suppose that there is a facility \(i\) whose bids \[\begin{gather} \sum_{j\in A} [\alpha_j - d(i,j)]^+ + \sum_{j\in I} [d(j,S) - d(j,i)]^+ \end{gather}\] are just barely below \(\hat{f}\). However, in that case, increasing the \(\alpha\)-value of active clients by a factor \(1+\varepsilon^2\) may cause the bids to be strictly above \(\hat{f}\), leading to difficulties in the analysis. (Specifically, in the proof that \(\alpha^*/2\) is dual feasible.) We intuitively change Greedy in two ways to handle this. First, we open centers if the bids pay for them in the metric scaled down by a factor of \((1-\delta)\). That is, we consider a facility \(i\) paid for if \[\begin{gather} \sum_{j\in A} [\alpha_j - (1-\delta) d(i,j)]^+ + (1-\delta) \sum_{j\in I} [d(j,S) - d(j,i)]^+ \geq \hat{f}\,. \end{gather}\] As we scale down the metric (i.e., the connection cost) by a factor \(1-\delta\), this loses a factor \(1/(1-\delta)\) in the approximation guarantee. However, the benefit is the following. Let \(X = \{j\in A \mid \alpha_j \geq (1-\delta) d(j,i)\}\) be the active clients that bid for \(i\). Then \[\sum_{j\in X} \left(\alpha_j - (1-\delta) d(i,j) \right) \geq \sum_{j\in X} \left((1+\varepsilon^2) \alpha_j - d(i,j) \right)\] assuming that \(\sum_{j\in X} \varepsilon^2 \alpha_j = \varepsilon^2 \theta |X|\) is smaller than \(\delta \sum_{j\in X} d(i,j)\). We will select \(\delta = 3\varepsilon\) and so this means that it is safe to increase the \(\alpha\)-values of active clients by a factor \((1+\varepsilon^2)\) as long as the average distance from bidding active clients is at least \(\varepsilon^2 \theta/\delta = \varepsilon\theta/3\). Our second change deals with the remaining case when the clients in \(X\) are close to co-located with \(i\). We do so by allowing the clients \(j\) in the ball \(B(i, \varepsilon\theta)\) to increase their bids for \(i\) up to \(\min((1+\varepsilon^2)\theta, (1-\delta)d(j,S))\). These changes are captured in the following definition of openable facilities. The bids \((\tau_j)_{j\in A}\) from active clients are only allowed to increase for nearby clients (the first two properties). A facility is considered paid for with respect to the scaled down metric (the third property). Finally, for the proof of dual feasibility even after increasing the bids of nearby clients, we need a technical fourth condition in the definition. We remark that we use \((\alpha, S, A, \theta)\) to denote the algorithm’s state, where \(\alpha\) is the approximate feasible dual solution, \(S\) the set of open facilities, \(A\) the set of active clients (which determines \(I = D \setminus A\)), and \(\theta\) the time. Both Greedy and LogAdaptive(that we describe below) satisfy \(\alpha_j = \theta\) for all \(j\in A\).

We note that when the state of the algorithm is clear from the context, we simply say that "\(i\) is openable" without explicitly specifying the state.

The following lemma follows from that we can write the selection of the bids as a linear program. Indeed, given the state \((\alpha, S, A, \theta)\) of the algorithm, each of the four conditions on the bids \((\tau_j)_{j\in A}\) can be formulated as linear inequalities.

The description of LogAdaptive is given in Algorithm 4.

It takes a parameter \(\varepsilon\in [0, 1/6]\) and \(\delta = 3\varepsilon\). The time \(\theta\) is now increased in steps by a multiplicative factor of \((1+\varepsilon^2)\). This is done in each iteration of the outermost loop, "Repeat the following while \(A \neq \emptyset\)," which we refer to as a phase of the algorithm. Inside a phase, we refer to the two points as stages, so stage 1 corresponds to the while-loop where we open openable facilities, and stage 2 corresponds to the increase of \(\alpha\)-values of the active clients \(A\). At any point in time, the state of the algorithm is described, as aforementioned, by the tuple \((\alpha, S, A, \theta)\). The careful reader may observe that \(A\) is redundant because the active clients \(A\) are determined by \(S\). Indeed, the same holds for the set of inactive clients \(I = D- A = \{j\in D: \alpha_j < (1-\delta) d(j,S) \}\). However, it will be notationally convenient to explicitly keep track of \(A\) in the algorithm’s state.

The parameter \(\varepsilon>0\) regulates the number of phases the algorithm will make. Indeed, all active clients have the same \(\alpha\)-value, and after the completion of \(p\) phases, the \(\alpha\)-value of active clients equals \((1+\varepsilon^2)^p\). This ensures that the number of phases until the algorithm terminates is \(O(\log(n)/\varepsilon^2)\). Hence, the increase of \(\alpha\)-values only depends on \(O(\log(n)/\varepsilon^2)\) states of the algorithm, the states before the second stage in each of the phases. This is why we refer to the algorithm to be of logarithmic adaptivity.

Apart from impacting the number of phases, the choice of \(\varepsilon\) also impacts the approximation guarantee. Specifically, we prove the following theorem in the subsequent section. (Recall that \(\delta = 3\varepsilon\).)

3.3 Analysis of LogAdaptive↩︎

An atomic step refers to the set of operations in the indented paragraphs in LogAdaptive that change the state \((\alpha, S, A, \theta)\). (I.e., an atomic step happens when a new facility \(i\) is opened and at the end of each phase.) By “at any point of the algorithm”, we mean any point in the algorithm’s execution that is not in the middle of an atomic step. Throughout the analysis, we let \(\alpha^*_j\) be the final \(\alpha\)-value of a client \(j\in D\), and we let \(S^*\) be the set of opened facilities. We start by analyzing the approximation guarantee of the algorithm with respect to \(\alpha^*\), and we then prove that \(\alpha^*/2\) is a feasible solution to the dual.

3.3.1 Approximation Guarantee.↩︎

In the following lemma, we prove that \(\sum_{j\in D} \alpha^*_j\) pays for the opening costs of the facilities in \(S^*\) and the connection cost of the clients scaled by a factor \((1-\delta)\).

In the next subsection, we prove the following lemma showing that \(\alpha^*/2\) is a feasible dual solution.

These two lemmas imply \[\text{opt}_{\text{LP}}(f) \geq \sum_{j\in D} \frac{\alpha^*_j}{2} \geq \frac{1-\delta}{2}\sum_{j\in D} d(j, S^*) + f\,|S^*|,\] where we used that \(\hat{f} = 2 \cdot f\). Therefore, we have an LMP \(2/(1-\delta)\)-approximation: the connection cost of the output solution \(S^*\) satisfies \[\begin{gather} \sum_{j\in D} d(j,S^*) \leq \frac{2}{1-\delta} \left( \text{opt}_{\text{LP}}(f) - f\,|S^*| \right)\,. \end{gather}\] In other words, Lemma 6 and Lemma [lemma:dual95feasibility] imply Theorem 3.

We proceed to prove Lemma 6 (and prove Lemma [lemma:dual95feasibility] in the next subsection).

3.3.2 Dual Feasibility↩︎

We start by showing that we never overbid a facility \(i\). This is rather immediate in the analysis of Greedy that we outlined in Section 3.1. While we prove this remains true for LogAdaptive, proving it requires more work, especially because of the discrete increase of \(\alpha\)-values in the second stage of a phase.

Having proved that LogAdaptive as Greedy maintains the invariant that there is no overbidding, we are ready to prove the dual-feasibility of \(\alpha^*/2\). (This corresponds to Lemma 3 in the analysis of Greedy.)

We remark that this implies dual feasibility of \(\alpha^*/2\) by dividing both sides by \(2\) (recall \(\hat{f} = 2 \cdot f\)).

The rest of the section is devoted to the proof of Lemma [lemma:dual95feasibility], and from now on, we focus on an arbitrary but fixed facility \(i\in F\). Let \(D^* = \{ j \in D : \alpha^*_j > 2d(i, j) \}\) be those clients that contribute to the left-hand side of the inequality in the claim. Further, order the clients in \(D^*\) according to \(\alpha^*\) values by the time they are removed from \(A\) (in the algorithm) and break ties according to \(\alpha^*\) values (in increasing order). We will use \(j, \ell\) to denote clients in \(D^*\), and let us slightly abuse notation and use \(j \leq \ell\) with respect to this ordering. In other words, we have \(j\leq \ell\) if \(j\) was removed from \(A\) in an atomic step before \(\ell\) was removed, or \(j\) and \(\ell\) were removed during the same atomic step and \(\alpha^*_j \leq \alpha^*_\ell\). We also use the terminology that a facility \(i_0\) freezes \(i\) if \(i_0\) becomes open when \(i\) is not, and \(d(i, i_0) \leq (1+3\varepsilon)\theta/2\). (Of course, \(i\) freezes itself when it is open.) This notion is important as for a facility \(i\), its \(D^*\) and their \(\alpha^*\) values do not change after it is frozen.

The following lemma, analogous to Lemma 4 in the analysis of Greedy, is key to proving dual feasibility.

Equipped with the above lemma, we are ready to complete the proof of dual feasibility.

3.4 Walking Between Two Solutions: Setup↩︎

Given the description of the LogAdaptive, we present our final algorithm MergeSolutions, resulting in a solution that opens \(k+O_{\varepsilon}(\log n)\) centers by maintaining two partial solutions that lead to opening at least \(k\) and at most \(k\) centers respectively and gradually merge them into a single solution that opens exactly \(k+O_{\varepsilon}(\log n)\) facilities, exploiting the \(O_{\varepsilon}(\log n)\) adaptivity of LogAdaptive.

Before detailing the merging procedure, which we call MergeSolutions, it is helpful to observe that we may generalize the analysis to make it more “robust”. We introduce this more robust analysis in this subsection, where we also define the notation that will be used later to describe MergeSolutions in Section 3.5.

Starting from the two solutions obtained in the standard way whose facility costs differ by at most \(\eta := 2^{-n}\), the two solutions we maintain will have an exponentially small difference \(\eta\) in one of their parameters. (These parameters will be either the facility cost \(f\) or some distance related to a free facility that will be introduced later.) For this reason, when we merge the two solutions, it may occur that some facilities in one solution are almost completely paid for, rather than fully paid for. To address this, we generalize the definition of "openable" to "\(\eta\)-openable," where the only difference is in the third condition: we now require each facility that is opened to be paid \(\hat{f} - \eta n\) instead of \(\hat{f}\) (as in Definition 2). We also note that being openable only depends on the time \(\theta\) and the set \(S\) of open facilities so far. This is because \(\alpha_j = \theta\) for \(j\in A\), \(I = \{j\in D: \theta \geq (1-\delta)d(j,S)\}\) and \(A = D- I\). This allows us to simplify notation and we have the following generalization of Definition 2.

We also introduce the concept of free facilities. During the process of merging the two solutions, we introduce free facilities, whose opening costs are not necessarily paid. While we will introduce at most \(O(\log n)\) such free facilities, we do not restrict the number of free copies a regular facility may have. Let \(S_{\mathsf{free}}\subseteq S\) denote the multiset of free facilities that have been opened.

Moreover, for each free copy \(\tilde{i} \in S_{\mathsf{free}}\) of \(i \in F\), we define a parameter \(u(\tilde{i})\), which represents the distance between the freely opened facility \(\tilde{i}\) and its original copy \(i\). So for any point \(x\) in the metric space (either a facility or a client), the distance is given by \(d(\tilde{i}, x) = u(\tilde{i}) + d(i, x)\).

We further introduce the following terminology: as mentioned, we refer to the facilities in \(S_{\mathsf{free}}\) as free facilities, the facilities in \(F\) and \(S_{\mathsf{reg}}= S - S_{\mathsf{free}}\) as regular facilities, and when we simply mention "facilities," we are referring to their union.

Finally, we will use the letters \(i\) and \(h\) to denote facilities. Specifically, we use \(i \in F\) to denote a regular facility and use \(\tilde{i}\) to denote a free copy of \(i\). When referring to a facility that can be either free or regular, we use the letter \(h\).

We now introduce the definition of valid sequences, which aims to capture the sequence of facilities that are opened during the while-loop of stage 1 in LogAdaptive.

We remark that LogAdaptive generates \(0\)-valid sequences in each phase. Specifically, it generates sequences \(\mathcal{H}= (H_1, H_2, \ldots, H_L)\), where each \(H_p\) is \(0\)-valid (with respect to \(\theta = (1+\varepsilon^2)^{p-1}\) and \(S = \cup_{i \in [p-1]} H_i\)) and contains only regular facilities. The set \(S\) of opened facilities is such that \(A = \emptyset\) at the final time \(\theta\).

For a general sequence of sequences \(\mathcal{H}= (H_1, H_2, \ldots, H_L)\), let us say it consists of \(\eta\)-valid sequences if, for every \(p \in [L]\), \(H_p\) is an \(\eta\)-valid sequence with respect to \(\theta = (1+\varepsilon^2)^{p - 1}\) and \(S = \cup_{q \in [p-1]} H_q\). (Here we abuse notation and treat \(H_q\) as a set of facilities.) Furthermore, we say that \(\mathcal{H}\) is a solution if the set \(S\) of opened facilities ensures that \(A = \emptyset\) at the end, meaning that at the time \(\theta = (1+\varepsilon^2)^L\) of the \((L+1)\)st phase, the set of inactive clients \(I = \{ j \mid \theta \geq (1-\delta) d(j,S) \}\) equals all clients in \(D\). Otherwise, we say that \(\mathcal{H}\) is a partial solution.

Theorem 3 can thus be stated as: if \(\mathcal{H}\) is a solution of \(0\)-valid sequences consisting of regular facilities then the set \(S\) of opened facilities satisfies \[\sum_{j\in D} d(j, S) \leq \frac{2}{1-\delta} \cdot \left( \text{opt}_{\text{LP}}(f) - f \cdot |S| \right)\,.\] We now allow to open regular facilities by paying at least \(\hat{f}- \eta n\) (instead of \(\hat{f}\)) and incorporate the notion free facilities, which leads to the following generalization of the analysis, proved in Appendix 5.

It will be useful to use similar terminology as we did in Section 3.3, let us consider the execution of the solution \(\mathcal{H}\) where for \(p = 1, \dots, L\), we run the \(p\)-th phase according to the sequence \(H_p\); in Stage 1, each facility in the sequence becomes open one by one with the corresponding \((\tau_j)_j\) values, and in Stage 2 at the end of the phase, \(\theta \leftarrow \theta(1+\varepsilon^2)\).

Then an atomic step can still be defined in the same way as in LogAdaptive; it corresponds to opening a facility in Stage 1 (and updating \(\alpha, S, A\) accordingly) or increasing \(\alpha\) values in Stage 2 simultaneously (and updating \(S\) accordingly). By “at any point of the algorithm”, we mean any point in the algorithm’s execution that is not in the middle of an atomic step.

With this notation, we have the following generalization of Claim 1:

At any point of the algorithm, for every facility \(i\), \[\sum_{j \in A} [\alpha_j - d(i,j)]^+ + \sum_{j \in I} [(1 - \delta)d(j, S) - d(j, i)]^+ \leq \hat{f}. \label{eq:dual-feasible-local-robust}\tag{9}\]

This is formally proved in Claim 10 in Appendix 5, and the proof is essentially the same as that of Claim 1. We use it to prove Lemma 8, which we will use in the merging procedure to ensure maximality. At a point of the execution, we say that a facility \(i\) is payable if it is openable (with \(\eta = 0\)) except that the dual feasibility condition is not necessarily satisfied. The payable notion is thus a weaker notion than openable, and a facility \(i\) may be payable but not openable. However, we have the following lemma that says that if there is a payable facility, there is also an openable facility. We remark that it does not guarantee that a payable facility is also openable but it does guarantee that if there exists a payable facility, there is also an openable facility, which is sufficient for our arguments.

In the next subsection we will merge two solutions into one with \(|S_{\mathsf{reg}}| =k\) and \(S_{\mathsf{free}}=O(\log n/\varepsilon^2)\). To our help, we will have two basic routines \(\mathrm{\small CompleteSolution}\) and \(\mathrm{\small CompleteSequence}\):

• \(\mathrm{\small CompleteSolution}_{f,u}(\mathcal{H})\) takes a partial solution \(\mathcal{H}\) as input and returns a solution by running the while-loop of stage 1 in LogAdaptive using the opening cost \(f\) and the distances \(u\) for free facilities already opened.

• \(\mathrm{\small CompleteSequence}_{f,u}(\mathcal{H}= (H_1, \ldots, H_{p-1}), H_p = \langle h_1, \ldots, h_\ell\rangle )\) where \(\mathcal{H}\) is partial solution and \(H_p\) is an \(\eta\)-valid sequence except that it may not be maximal. \(\mathrm{\small CompleteSequence}\) then runs the while-loop of stage \(1\) in LogAdaptive starting with \(H_p\) to return a maximal sequence whose prefix is \(H_p\) (with respect to opening cost \(f\) and distances \(u\)).

We note that all facilities added by CompleteSolution and CompleteSequence are \(0\)-openable and regular. Additionally, for intuition, observe that, with the above notation, the set of facilities opened by \(\mathrm{\small CompleteSolution}_{f,u}(\emptyset)\) is equivalent to that opened by LogAdaptive. (There is no free facility so \(u\) is meaningless here.) To simplify notation, we only use \(\mathrm{\small CompleteSequence}\) when the partial solution \(\mathcal{H}\) is clear from the context, so we simply write \(\mathrm{\small CompleteSequence}_{(f,u)}(\langle h_1, \ldots, h_\ell \rangle)\). Furthermore, we omit \((f,u)\) when the parameters are clear from the context.

3.5 MergeSolutions↩︎

We now present our procedure MergeSolutions that walks between two solutions. We will maintain two solutions \((\mathcal{H}, f, u)\) and \((\mathcal{H}', f', u')\) whose numbers of open regular facilities sandwich \(k\). (Formally, let us say \(a\) and \(b\) sandwich \(k\) if \(a<k<b\) or \(b<k<a\).) We will gradually make them closer until one of them opens exactly \(k\) regular facilities. We start from the two initial solutions obtained using the standard method. Note that the minimum nonzero distance is \(1\) and the maximum distance is \(M= \mathrm{poly}(n)\), which implies that \(\text{opt}\leq nM\).

3.5.0.1 Initialization.

We consider executions of \(\mathrm{\small CompleteSolution}_{f, u}(\emptyset)\) with empty \(u\). When \(f = 1/n^2\), every client \(j \in D\) satisfies \(d(j, S) = 0\) if \(d(j, F) = 0\) and \(d(j, S) \leq d(j, F) + 2/n^2\) otherwise, as each client can open its closest facility by itself when \(\alpha _j = d(j, F) + 2/n^2\). If this solution opens at most \(k\) centers, then it is already an \((1+2/n)\)-approximation and we return it. On the other hand, when \(f = 4nM\), the algorithm will open exactly one facility, since the first facility is open when \(\theta \geq 2M\), so every client becomes immediately inactive when it is open. We then perform a binary search in the interval \([1/n^2, 4nM]\) of values of \(f\), keeping the invariant that for the current research interval \([f,f']\) the corresponding two solutions \((\mathcal{H}, f, u)\) and \((\mathcal{H}', f', u)\) are such that \((\mathcal{H}, f, u)\) opens less than \(k\) facilities and \((\mathcal{H}', f', u)\) opens more than \(k\) facilities. We halt the process when \(f \leq f' \leq f + \eta\).

3.5.0.2 General Step.

MergeSolutions works on phase \(p = 1, 2, \dots\) iteratively, and ensures that the two solutions are identical up to the \(p\)-th phase. Formally, MergeSolutions takes two solutions \((\mathcal{H}, f, u)\) and \((\mathcal{H}', f', u')\) as well as the current phase \(p\) as input. The following promises on them will be satisfied whenever we call MergeSolutions.

• Both solutions consist of \(\eta\)-valid sequences.

• The numbers of open regular facilities by the two solutions sandwich \(k\).

• Exactly one parameter, which we call the difference parameter, differs by at most \(\eta\) between the two solutions, i.e, if \(f\neq f'\) then \(|f-f'| \leq \eta\) and \(u(\tilde{i}) = u'(\tilde{i})\) for every \(\tilde{i} \in F_{\mathsf{free}}\); otherwise if \(f=f'\) there is exactly one free facility \(\tilde{i}\in F_{\mathsf{free}}\) so that \(u(\tilde{i}) \neq u'(\tilde{i})\) and \(|u(\tilde{i}) - u'(\tilde{i})| \leq \eta\).

• \(\mathcal{H}= (H_1, H_2, \ldots, H_L)\) and \(\mathcal{H}' = (H'_1, H'_2, \ldots, H'_{L'})\) have a common prefix of length \(p-1\), i.e., \(H_i = H'_i\) for \(i=1,2, \ldots, p-1\). Furthermore, the remaining sequences \(H_p, \ldots, H_L\) and \(H'_p,\ldots, H'_{L'}\) only contain regular facilities and are \(0\)-valid with respect to the parameters \(f, u\) and \(f', u'\), respectively. (This implies that \(\mathcal{H}\) and \(\mathcal{H}'\) open the same set of free facilities.)

Given the promises, the goal of MergeSolutions is to

• either find a solution of \(\eta\)-valid sequences that opens exactly \(k\) regular facilities and \(O_{\varepsilon}(\log n)\) free facilities, or

• produce two new solutions that satisfy the above promises for phase \(p + 1\).

Since the maximum distance between any two points is \(M\leq \mathrm{poly}(n)\) and \(f \leq 4nM\), before \(\theta\) reaches \(6M\), at least one facility will open and every client will become inactive. Therefore, for some threshold \(p^* = O(\log n / \varepsilon^2)\), once \(\mathcal{H}\) and \(\mathcal{H}'\) agree on the first \(p^*\) phases, they open exactly the same set of facilities which violates the promise that the numbers of open regular facilities sandwich \(k\). Therefore, case (1) must happen for some \(p \leq p^*\), which yields a solution of \(\eta\)-valid sequences that opens exactly \(k\) regular facilities and \(O(\log n)\) free facilities. Combined with Theorem 4, this proves Theorem [thm:pseudo-approx]. Indeed, we then have a solution consisting of open centers \(S\) with \(|S| = k + O(\log(n)/\varepsilon^2)\) such that, by Theorem 4, \[\begin{align} \sum_{j\in D} d(j, S) & \leq \frac{2}{1-\delta} \cdot \left( \text{opt}_{\text{LP}}(f) - (f-\eta n) \cdot k \right) \leq (2+O(\varepsilon)) \text{opt}\,, \end{align}\] where, for the last inequality, we used that \(\eta = 2^{-n}\) and \(\text{opt}\geq 1\) (since any distance is at least \(1\)). Theorem [thm:pseudo-approx] then follows by scaling \(\varepsilon\) appropriately.

In the remainder of this section, we present MergeSolutions for two solutions and a given phase \(p\). It consists of three subroutines, presented in Section 3.5.1 3.5.2, and 3.5.3 respectively. Each subroutine achieves (1) or (2) above (which ends the whole procedure or lets us move on to the next phase), or sets up the stage for the next subroutine. The final third subroutine always achieves (1) or (2).

3.5.1 Making Parameters Identical↩︎

In this subsection, we try to make the parameters of the two solutions exactly identical. By renaming, we assume that if \(f\neq f'\) is the difference parameter then \(f' < f\), and if the difference parameter is \(u(\tilde{i}) \neq u'(\tilde{i})\) then \(u(\tilde{i}) < u'(\tilde{i})\).

3.5.1.1 Outcome of this section of MergeSolutions.

Let \[\mathcal{H}'' = \mathrm{\small CompleteSolution}_{(f,u)}(H'_1, \ldots, H'_p)\,,\] which is a valid call by Claim 2. If \(\mathcal{H}''\) opens \(k\) regular facilities, we return this solution. Otherwise, as \((\mathcal{H}, f,u)\) and \((\mathcal{H}', f', u')\) sandwich \(k\), we must have that either \((\mathcal{H}, f, u)\) and \((\mathcal{H}'', f, u)\), or \((\mathcal{H}'', f, u)\) and \((\mathcal{H}', f', u')\) sandwich \(k\). On the one hand, if \((\mathcal{H}'', f, u)\) and \((\mathcal{H}', f',u')\) sandwich \(k\), then we made progress in that we now have two solutions with a common prefix of length \(p\) (instead of \(p-1\)) and only one parameter differs by at most \(\eta\). In this case, we are done with phase \(p\) and can continue MergeSolutions with these two solutions and phase \(p+1\).

On the other hand, if \((\mathcal{H}, f,u)\) and \((\mathcal{H}'', f, u)\) sandwich \(k\), then these two solutions have the same parameters and their first \(\eta\)-valid sequences that differ are \(H_p\) and \(H'_p\). In this case, we rename \(\mathcal{H}''\) to \(\mathcal{H}'\) and proceed to the next step.

3.5.2 Maximize Common Prefix of \(H_p\) and \(H'_p\)↩︎

We are given two solutions \((\mathcal{H}, f,u)\) and \((\mathcal{H}', f, u)\) on the same parameters \(f,u\) that sandwich \(k\). Moreover, if we let \(\mathcal{H}= (H_1, \ldots, H_L)\) and \(\mathcal{H}' = (H'_1, \ldots, H'_{L'})\), then \(H_i = H'_i\) for \(i= 1, \ldots, p-1\) and \(H_p \neq H'_p\). In addition \(H_p\) and \(H'_p\) only contain regular facilities.

In this step of MergeSolutions, we increase the common prefix of \(H_p\) and \(H'_p\) by “slowly” modifying \(H'_p\). Recall that \(H_p\) only contains regular facilities: let \(H_p = \langle i_1, i_2, \ldots, i_\ell \rangle\). Moreover, as the parameters \((f,u)\) are clear from the context, we omit them in the following when, e.g., calling the procedures CompleteSolution and CompleteSequence.

3.5.2.1 Transforming \(H'_p\) step-by-step so that \(H_p\) becomes a prefix of \(H'_p\).

Repeat the following until all of \(H_p\) becomes a prefix of \(H'_p\).

• Let \(q\) be the largest index so that \(H'_p = \langle i_1, i_2, \ldots, i_q, h'_{q+1}, \ldots, h'_{\ell_1}\rangle\), i.e., \(q\) equals the length of the common prefix \(i_1, i_2, \ldots, i_q\) of \(H_p\) and \(H'_p\).

• Update \(H'_p\) by inserting a free copy of \(i_{q+1}\), \(\tilde{i}_{q+1}\), at the end of \(H'_p\) with \(u(\tilde{i}_{q+1}) = 0\). That is, we get the sequence \[\begin{gather} H'_p = \langle i_1, i_2, \ldots, i_q, h'_{q+1}, \ldots, h'_{\ell_1}, \tilde{i}_{q+1} \rangle,. \end{gather}\]

• For \(t = q+1 , \ldots, \ell_1\),

  • Update \(H'_p\) by first removing \(h'_t\) and then completing the sequence by a call to CompleteSequence. More explicitly, if \[\begin{align} H'_p = & \langle i_1, \ldots, i_q, h'_t, h'_{t+1} \ldots, h'_{\ell_1}, \tilde{i}_{q+1}, h'_{\ell_1+1}, \ldots, h'_{\ell_2}\rangle \\ \intertext{then we delete h'_t to obtain} H''_p = & \langle i_1, \ldots, i_q, h'_{t+1} \ldots, h'_{\ell_1}, \tilde{i}_{q+1}, h'_{\ell_1+1}, \ldots, h'_{\ell_2}\rangle \\ \intertext{and finally update H'_p = \mathrm{\small CompleteSequence}(H''_p) which will be of the form} & \langle i_1, \ldots, i_q, h'_{t+1}, \ldots, h'_{\ell_1}, \tilde{i}_{q+1}, h'_{\ell_1+1}, \ldots, h'_{\ell_2}, \ldots, h'_{\ell_3}\rangle\,, \end{align}\] where \(h'_{\ell_2+1},\ldots, h'_{\ell_3}\) are the facilities added by CompleteSequence(which could be empty).

• After removing \(h'_{q+1}, \ldots, h'_{\ell_1}\), we have \[\begin{align} H'_p & = \langle i_1, i_2, \ldots, i_q, \tilde{i}_{q+1}, h'_{x}, \ldots, h'_{y}\rangle\,. \\ \intertext{We update H'_p by replacing \tilde{i}_{q+1} with its regular copy i_{q+1}, i.e., we obtain} H'_p & = \langle i_1, i_2, \ldots, i_q, {i}_{q+1}, h'_{x}, \ldots, h'_{y}\rangle\,. \end{align}\]

We have the following claims.

3.5.2.2 Outcome of this section of MergeSolutions.

We distinguish three cases.

3.5.2.3 Case 1.

If at some point \(H'_p\) is such that \(\mathrm{\small CompleteSolution}(H'_1, H'_2, \ldots, H'_p)\) opens exactly \(k\) regular facilities, then we return that solution.

3.5.2.4 Case 2.

Otherwise, suppose there is an update to \(H'_p\) so that if we let \(H^{\text{before}}_p\) and \(H^{\text{after}}_p\) denote \(H'_p\) before and after this update, respectively, then CompleteSolution\((H_1, H_2, \ldots, H^{\text{before}}_p)\) and CompleteSolution\((H_1, H_2, \ldots, H^{\text{after}}_p)\) sandwich \(k\). There are three kinds of updates to \(H'_p\). However, note that the update where \(\tilde{i}_{q+1}\) is replaced by its regular copy \(i_{q+1}\) cannot satisfy the conditions of this case. Indeed, as \(u(\tilde{i}_{q+1}) = 0\), we have \[\mathrm{\small CompleteSolution}(H_1, \ldots, H^{\text{before}}_p) = \mathrm{\small CompleteSolution}(H_1, \ldots, H^{\text{after}}_p)\] in this case, which contradicts that they sandwich \(k\).

We proceed to analyze the two other kind of updates. If the update to \(H'_p\) is to insert a free facility \(\tilde{i}_{q+1}\) with \(u(\tilde{i}_{q+1}) = 0\). Then \[\begin{align} H^{\text{before}}_p& = \langle i_1, i_2, \ldots, i_q, h'_{q+1}, \ldots, h'_{\ell_1} \rangle \\ H^{\text{after}}_p& = \langle i_1, i_2, \ldots, i_q, h'_{q+1}, \ldots, h'_{\ell_1}, \tilde{i}_{q+1} \rangle \end{align}\] Note that the solution CompleteSolution\((H_1, H_2, \ldots, H^{\text{before}}_p)\) is equivalent to CompleteSolution\((H_1, H_2, \ldots, H^{\text{after}}_p)\) if we set \(u(\tilde{i}_{q+1}) = 10M\) (except for the free facility \(\tilde{i}_{q+1}\)). We can thus do binary search on \(u(\tilde{i}_{q+1})\) to find two values \(u'(\tilde{i}_{q+1})\) and \(u(\tilde{i}_{q+1})\) with \(|u'(\tilde{i}_{q+1}) - u(\tilde{i}_{q+1})| \leq \eta\) so that the solutions \(\mathrm{\small CompleteSolution}_{(f,u')}(H_1, \ldots, H^{\text{after}}_p)\) and \(\mathrm{\small CompleteSolution}_{(f,u)}(H_1, \ldots, H^{\text{after}}_p)\) sandwich \(k\) (where \(u\) and \(u'\) are identical except for \(\tilde{i}_{q+1}\)). We have thus finished phase \(p\), and we can restart MergeSolutions with the two solutions and phase \(p+1\), since they have the first \(p\), instead of \(p-1\), \(\eta\)-valid sequences in common and exactly one difference parameter. Their maximality follows from that of \(H^{\text{before}}_p\).

Finally, consider when the update to \(H'_p\) is of the second type, i.e., \(u(\tilde{i}_{q+1}) = 0\) and \[\begin{align} H^{\text{before}}_p= & \langle i_1, \ldots, i_q, h'_t, h'_{t+1} \ldots, h'_{\ell_1}, \tilde{i}_{q+1}, h'_{\ell_1+1}, \ldots, h'_{\ell_2}\rangle \\ H^{\text{after}}_p= & \langle i_1, \ldots, i_q, h'_{t+1}, \ldots, h'_{\ell_1}, \tilde{i}_{q+1}, h'_{\ell_1+1}, \ldots, h'_{\ell_2}, \ldots, h'_{\ell_3}\rangle \end{align}\] In this case, \(\mathrm{\small CompleteSolution}(H_1, \ldots, H^{\text{before}}_p)\) and \(\mathrm{\small CompleteSolution}(H_1, \ldots, H^{\text{after}}_p)\) are two solutions with the same parameters \(f, u\), that sandwich \(k\) and we proceed to the next step with the following properties of \(H^{\text{before}}_p\) and \(H^{\text{after}}_p\):

• Both sequences contain one free facility, \(\tilde{i}_{q+1}\).

• \(H^{\text{before}}_p\) and \(H^{\text{after}}_p\) are identical except that (1) \(H^{\text{before}}_p\) contains a regular facility \(h'_t\) not present in \(H^{\text{after}}_p\), and (2) \(H^{\text{after}}_p\) contains a (potentially empty) suffix of regular facilities not present in \(H^{\text{before}}_p\).

3.5.2.5 Case 3.

None of the previous cases apply. Then, completing the solution with the initial \(H'_p\) and the final \(H'_p\) cannot sandwich \(k\). Since then (assuming the first case does not apply) there must be an update to \(H'_p\) that results in two solutions that sandwich \(k\): this happens because the completion of \(H_p\) and the completion of the initial \(H'_p\) sandwich \(k\). The above implies that if we let \(H^{\text{before}}_p= H_p\) and \(H^{\text{after}}_p\) equal the final \(H'_p\) then CompleteSolution\((H_1, \ldots, H^{\text{before}}_p)\) and CompleteSolution\((H_1, \ldots, H^{\text{after}}_p)\) sandwich \(k\). Further note that, since \(H^{\text{after}}_p\) equals \(H'_p\) after the final updates, \(H^{\text{before}}_p\) appears as a prefix of \(H^{\text{after}}_p\) and both sequences only contain regular facilities. To summarize, in this case, CompleteSolution\((H_1, \ldots, H^{\text{before}}_p)\) and \(\mathrm{\small CompleteSolution}(H_1, \ldots, H^{\text{after}}_p)\) are two solutions with the same parameters \(f, u\), that sandwich \(k\) and we proceed to the next step with the following properties of \(H^{\text{before}}_p\) and \(H^{\text{after}}_p\):

• Both sequences contain no free facilities.

• \(H^{\text{before}}_p\) and \(H^{\text{after}}_p\) are identical except that \(H^{\text{after}}_p\) contains a suffix of regular facilities not present in \(H^{\text{before}}_p\).

3.5.3 Removing Extra Facilities↩︎

The input to this step consists of two solutions \(\mathrm{\small CompleteSolution}(H_1, \ldots, H^{\text{before}}_p)\) and CompleteSolution\((H_1,\ldots, H^{\text{after}}_p)\) that have the same parameters \(f, u\) and sandwich \(k\). Moreover, \(H^{\text{before}}_p\) and \(H^{\text{after}}_p\) both contain at most one free facility and they are identical except for potentially two differences:

• \(H^{\text{before}}_p\) may contain a facility not present in \(H^{\text{after}}_p\);

• \(H^{\text{after}}_p\) contains a suffix of regular facilities (which may be empty) that is not present in \(H^{\text{before}}_p\).

To simplify the notation in this section, we let \(i_*\) denote the regular facility in \(H^{\text{before}}_p\) that is not present in \(H^{\text{after}}_p\) if it exists (so \(i_*\) corresponds to \(h'_t\) in the previous section). We further let \(h_1, \ldots, h_\ell\) denote the suffix of \(H^{\text{after}}_p\) not present in \(H^{\text{before}}_p\).

We now transform \(H^{\text{after}}_p\) into \(H^{\text{before}}_p\) one change at a time:

3.5.3.1 Generation of \(\eta\)-valid sequences from \(H^{\text{after}}_p\) to \(H^{\text{before}}_p\).

• If \(H^{\text{before}}_p\) contains the regular facility \(i_*\) not present in \(H^{\text{after}}_p\), then let \(\tilde{i}_*\) be a free copy of \(i_*\) with \(u(\tilde{i}_*) =0\) and obtain \(H^{0}_p\) from \(H^{\text{after}}_p\) by adding \(\tilde{i}_*\) at the end. Otherwise, we let \(H^0_p\) equal \(H^{\text{after}}_p\).

• For \(r= 1, \ldots, \ell\), obtain \(H^r_p\) from \(H^{r-1}_p\) by removing \(h_r\).

We remark that \(H^\ell_p\) is identical to \(H^{\text{before}}_p\) since we removed the whole suffix \(h_1, \ldots h_\ell\) present in \(H^{\text{after}}_p\), except for potentially the facility \(i_*\). That is, the only difference in \(H^{\text{before}}_p\) and \(H^\ell_p\) may be the placement of \(\tilde{i}_*\) in the sequence and the fact that \(\tilde{i}_*\) is a free copy of the regular facility \(i_*\) present in \(H^{\text{before}}_p\). However, since \(u(\tilde{i}_*) = 0\), we have that the two sequences \(H^{\text{before}}_p\) and \(H^\ell_p\) have an identical impact on CompleteSolution, which is a fact we will use in the proof of Claim 5.

3.5.3.2 Outcome of this section of MergeSolutions.

We distinguish three cases based on the first bullet point that is true in Claim 5.

3.5.3.3 Case 1.

If one of the sequences \(H^r_p\) is such that \(\mathrm{\small CompleteSolution}(H_1, H_2, \ldots, H^r_p)\) opens \(k\) regular facilities, then we return that solution.

3.5.3.4 Case 2.

Otherwise, if the solutions \(\mathrm{\small CompleteSolution}(H_1, H_2, \ldots, H^{\text{after}}_p)\) and CompleteSolution\((H_1, H_2, \ldots, H^{0}_p)\) sandwich \(k\), then \(H^0_p\) is equal to \(H^{\text{after}}_p\) except that \(\tilde{i}_p\) was added in the end of \(H^{\text{after}}_p\) with \(u(\tilde{i}_p) = 0\). Note that the solution CompleteSolution\((H_1, H_2, \ldots, H^{\text{after}}_p)\) is equivalent to CompleteSolution\((H_1, H_2, \ldots, H^0_p)\) if we set \(u(\tilde{i}_{q+1}) = 10M\) (except the presence of \(\tilde{i}_*\)). We can thus do binary search on \(u(\tilde{i}_*)\) to find two values \(u'(\tilde{i}_*)\) and \(u(\tilde{i}_*)\) with \(|u'(\tilde{i}_*) - u(\tilde{i}_*)| \leq \eta\) so that the two solutions \(\mathrm{\small CompleteSolution}_{(f,u')}(H_1, \ldots, H^0_p)\) and \(\mathrm{\small CompleteSolution}_{(f,u)}(H_1, \ldots, H^0_p)\) sandwich \(k\) (where \(u\) and \(u'\) are identical except for \(\tilde{i}_{q+1}\)). We have thus finished phase \(p\), and we can restart MergeSolutions with the two solutions and phase \(p+1\), since they have the first \(p\), instead of \(p-1\), \(\eta\)-valid sequences in common and exactly one difference parameter.

3.5.3.5 Case 3.

Finally, consider the case when none of the above cases apply and thus (by Claim 5) there is an \(r\in \{0, 1, \ldots, \ell-1\}\) so that CompleteSolution\((H_1, H_2, \ldots, H^r_p)\) and
CompleteSolution\((H_1, H_2, \ldots, H^{r+1}_p)\) sandwich \(k\). The only difference between \(H^r_p\) and \(H^{r+1}_p\) is that \(H^r_p\) contains \(h_{r+1}\) which is not present in \(H^{r+1}\). Let \(H_p\) be the sequence obtained by adding a free copy \(\tilde{i}_{r+1}\) of \(h_{r+1}\) at the end of \(H^{r+1}\) (which clearly maintains that is \(\eta\)-valid), then \[\begin{align} \mathrm{\small CompleteSolution}(H_1, H_2, \ldots, H_p) & = \mathrm{\small CompleteSolution}(H_1, H_2, \ldots, H^r_p)if u(\tilde{i}_{r+1}) = 0 \\ \intertext{and} \mathrm{\small CompleteSolution}(H_1, H_2, \ldots, H_p) & = \mathrm{\small CompleteSolution}(H_1, H_2, \ldots, H^{r+1}_p)if u(\tilde{i}_{r+1}) = 10M. \end{align}\] Hence, doing a binary search on \(u(\tilde{i}_{r+1})\) as in the previous case finishes phase \(p\). We can restart MergeSolutions with the two solutions and phase \(p+1\), since they have the first \(p\), instead of \(p-1\), \(\eta\)-valid sequences in common and exactly one difference parameter.

4 \((2+\varepsilon)\)-Approximation for \((\frac{\zeta}{\log n})\)-Stable Instances↩︎

In this section, we give a \((2+\varepsilon)\)-approximation algorithm for \((\frac{\zeta}{\log n})\)-stable \(k\)-median instances. The proof of the theorem is presented in Section 4.7. We restate the theorem for the reader’s convenience.

To simplify notation, we let \(\varepsilon\) be the minimum of \(\varepsilon\) and \(\zeta\) in the above theorem and further assume that \(\varepsilon<1/12\) is sufficiently small. With this notation, we present a \((2+O(\varepsilon))\)-approximation algorithm for \(\varepsilon/\log(n)\)-stable instances. This implies the above theorem as any \(\zeta/\log(n)\)-stable instance is also \(\zeta'/\log(n)\)-stable with \(\zeta' \leq \zeta\).

The algorithm and the proof of the above theorem follow several steps where we iteratively simplify the instance by adding more structure. Finally, we obtain enough structure to solve the problem by maximizing a submodular function subject to a matroid partition constraint. We have not optimized constants in favor of simplifying the description, and throughout this section we let \(O_\varepsilon(\log n)\) denote \(O(\log(n)/\varepsilon^{O(1)})\). An overview of this section and the algorithm is as follows:

4.0.0.1 Overview of \(2\)-Approximation for \(k\)-median on \((\varepsilon/\log n)\)- Stable Instance \(k, D, F, d\).

1. We start, in Section 4.1, by running a standard Local Search on \((k, D, F, d)\) to obtain a set of centers \(S\). It is well-known that \(S\) is a constant-factor approximation. Moreover, for a stable instance, we show that \(S\) “correctly” implicitly identifies all but \(O_\varepsilon(\log n)\) centers of \(\text{OPT}\). Specifically, this ensures that all but \(O_\varepsilon(\log n)\) clusters have the same cost as in \(\text{OPT}\) up to a \((1+O(\varepsilon))\) factor.

2. In Section 4.2, we use a technique inspired from the classic \(k\)-means++ algorithm and its so called \(D^2\)-sampling procedure to sample clients proportional to their cost in solution \(S\), and we show that if we take \(O_\varepsilon(\log n)\) samples \(W\) then with good probability we “hit” all but an insignificant fraction of clusters of high cost in \(S\).

3. In Section 4.3, we then, guess a subset of the sampled clients \(W\) so that each hit cluster has exactly one client, which we refer to as the leader of that cluster. In addition, for each client \(\ell\) that is a leader, we guess the (approximate) distance from \(\ell\) to the optimal center in the optimal cluster it hits. This defines a set \(\mathcal{B}\) of balls with the guarantee that the optimal solution opens one center in each of these balls. Moreover, if we let \(\hat{\text{OPT}}\) be the optimal centers corresponding to these balls, we prove in Section 4.3.1 that there is a swap of centers \(M_O = S-S_0 \cup \hat{\text{OPT}}\) that removes \(S_0\) and adds the optimal centers \(\hat{\text{OPT}}\) so that the cost of the solution \(M_O\) is good and in particular a \(2+O(\varepsilon)\)-approximation.

4. The remaining steps are then focused on approximating this swap, i.e., intuitively to that of finding \(S_0\) and \(\hat{\text{OPT}}\):

   1. We first find the set \(\mathcal{Q}\) of expensive centers of \(S_0\) so that the centers \(S_0-\mathcal{Q}\) has total cost \(O(\varepsilon\text{opt})\) in Section 4.4. This allows us to think of the centers in \(S_0 - \mathcal{Q}\) as contracted, i.e., as single weighted points, and in particular, that all clients of these clusters are assigned to the same center when their center in \(S_0\) is removed. We then, in Section 4.4.1, use this structure to partition \(S_0 - \mathcal{Q}\) into two sets \(\mathcal{U}\) and \(\mathcal{R}\) where \(\mathcal{U}\) are those centers that are reassigned to other centers in \(S - S_0\) and \(\mathcal{R}\) are those centers that are assigned to \(\hat{\text{OPT}}\).

   2. The set \(\mathcal{U}\) is then approximated with a set \(\widetilde{\mathcal{U}}\) (with close to identical properties) in Section 4.5.

   3. At this stage, we have thus “guessed” all centers \(\mathcal{Q}\cup \widetilde{\mathcal{U}}\) to remove from \(S\) except for those in \(\mathcal{R}\). This is achieved in Section 4.6 where we reduce the problem of both finding \(\mathcal{R}\) and an approximate version of \(\hat{\text{OPT}}\) to that of submodular function optimization subject to a partition matroid (since we should open one center per ball in \(\mathcal{B}\)).

We remark that in each of Steps 3, 4a, 4b, and 4c, we will make guesses by enumerating polynomially \(n^{\varepsilon^{-O(1)}}\) many potential choices. In the following, we describe the algorithm and its analysis by presenting each of these steps. When presenting the next step, we analyze the branch of the algorithm that took the successful guesses up to that point. The algorithm outputs the solution of the smallest cost among the \(n^{\varepsilon^{-O(1)}}\) constructed solutions obtained by enumerating all possible guesses (see Section 4.7 for a more formal treatment where we put everything together). In particular, the final solution will have cost at most the solution that is output in the analyzed branch of “correct” guesses.

We end this section by introducing basic definitions and concepts, followed by the definition of matroids and submodular functions. We also state the known result, an \((1-1/e)\)-approximation algorithm for maximizing monotone submodular functions subject to a matroid constraint, that we use in the last step (Section 4.6).

4.0.0.2 Definitions of leaders.

We use the following definitions throughout this section. Given a set of centers \(A\subseteq F\), we let \(\text{cost}(A):=\sum_{p\in D}d(p,A)\) denote the cost of the corresponding clustering (where each client \(p\) is assigned to the closest center in \(A\) and pays the corresponding distance). Sometimes we will consider a (possibly suboptimal) assignment \(\mu:D\rightarrow A\) of clients to centers in \(A\), and let \(\text{cost}(A,\mu):=\sum_{p\in D}d(p,\mu(p))\) be the corresponding cost. Let \(\text{OPT}\) be a fixed optimum solution for the \(k\)-median instance, and let \(\text{opt}= \text{cost}(\text{OPT})\) be its cost. For a client \(p\in D\), let \(\text{OPT}_p:=d(p,\text{OPT})\) be the cost paid by \(p\) in \(\text{OPT}\).

Let \(C^*\) be an \(\text{OPT}\) cluster with center \(c^*\in \text{OPT}\). We let \(\text{avg}_{C^*, \text{OPT}}\) be the distance from \(c^*\) to the \(\varepsilon|C^*|\)th closest client of \(C^*\) to \(c^*\). We further let \(C^*_\text{avg}\) be the set of clients of \(C^*\) at a distance at most \(\text{avg}_{C^*, \text{OPT}}\) from \(c^*\), we refer to these clients as leaders for \(C^*\). So \(\text{avg}_{C^*, \text{OPT}}\) is the maximum distance from a leader to its center \(c^*\). Also note that we have, \(|C^*_{avg}|\geq {\varepsilon}|C^*|\). We thus have that \(\text{avg}_{C^*, \text{OPT}}\) is upper bounded by \(\frac{1}{1-\varepsilon}\) times the average cost \(\frac{1}{|C^*|} \sum_{p\in C^*} d(p, c^*)\), and at the same time \(C^*_{avg}\) contains a constant fraction of the clients.

4.0.0.3 Partition matroids.

In Section 4.6, we formulate a submodular function that we then maximize over a partition matroid using known results. We define those concepts and also state the result that we will use. First, recall the definition of a matroid and partition matroid. A matroid is a tuple \((E, \mathcal{I})\) defined on a ground set \(E\) with a family of independent sets \(\mathcal{I}\) that satisfy: (1) if \(A \in \mathcal{I}\) and \(A' \subseteq A\), then \(A' \in \mathcal{I}\); and (2) if \(A, B \in \mathcal{I}\) and \(|A| < |B|\), then there exists an element \(e \in B - A\) such that \(A \cup \{e\} \in \mathcal{I}\). In the special case of a partition matroid, the ground set \(E\) is partitioned into disjoint subsets \(E_1, E_2, \dots, E_k\), and there are non-negative integers \(r_1, r_2, \dots, r_k\) such that:

• A subset \(I \subseteq E\) is independent if and only if \(|I \cap E_i| \leq r_i\) for each \(i = 1, 2, \dots, k\).

In other words, each subset \(E_i\) has a capacity limit \(r_i\), and an independent set \(I\) cannot contain more than \(r_i\) elements from \(E_i\). To work with matroids (to get a running time that is polynomial in the size of the ground set \(E\)), we often use independence queries, which allow us to determine if a given subset \(A \subseteq E\) is independent (i.e., whether \(A \in \mathcal{I}\)). Specifically, an independence query on a subset \(A\) returns true if \(A\) is independent and false otherwise.

4.0.0.4 Submodular functions.

Having defined matroids, we proceed to define non-negative monotone submodular functions. For a finite ground set \(E\), a set function \(f: 2^E \to \mathbb{R}\) is submodular if it satisfies the diminishing returns property: for every pair of sets \(A \subseteq B \subseteq E\) and any element \(e \in E - B\), it holds that \[f(A \cup \{e\}) - f(A) \geq f(B \cup \{e\}) - f(B).\] Intuitively, this means that adding an element \(e\) to a smaller set \(A\) provides at least as much additional value as adding \(e\) to a larger set \(B\). In addition, \(f\) is called monotone if for any pair of sets \(A \subseteq B \subseteq E\), we have \(f(A) \leq f(B)\). In other words, adding elements to a set does not decrease the function value. Finally, \(f\) is non-negative if \(f(A) \geq 0\) for all \(A \subseteq E\).

A celebrated result [47] gives a polynomial-time \((1-1/e)\)-approximation algorithm for the problem of maximizing a non-negative monotone submodular function over a matroid constraint. While the original result was a randomized algorithm, a recent striking result [48], building upon the work of [49], gives a deterministic algorithm with the same guarantee. We remark that polynomial time here refers to a running time that is polynomial in the size of the ground set \(E\). To summarize, they show the following theorem.

4.1 Properties of a Locally Optimal Solution↩︎

Let \(S\) be a locally optimal solution output by the following standard local search algorithm⁹. We remark that its running time is polynomial since by Lemma 1 the cost of a solution is a polynomially bounded integer and, at each improving step, the cost decreases by at least one.

4.1.0.1 \(localSearch(\cdot)\)

\(S \leftarrow\) arbitrary solution for \(k\)-Median \(S \leftarrow S'\) return \(S\)

Let \(S\) be the solution returned by \(localSearch()\). Local search achieves a \(5\) approximation for \(k\)-median, see e.g. Chapter 9.2 in [50].

In the remaining part of the algorithm and its analysis we fix \(S\), and recall that we fixed the reference optimal solution \(\text{OPT}\). We distinguish different types of clusters of \(\text{OPT}\) and analyze their properties in the next two sections. We let \(S_p\) be the cost paid by \(p\) in \(S\) and recall that \(\text{OPT}_p\) denotes the cost \(p\in D\) pays in \(\text{OPT}\).

4.1.1 Pure Clusters↩︎

We say that a cluster \(C^*\) of \(\text{OPT}\) is pure (w.r.t. \(S\)) if there exists a cluster \(C'\) of \(S\) such that \(|C' \Delta C^*| \le {3\varepsilon} \min(|C^*|,|C'|)\). In which case we also say that \(C'\) is pure w.r.t. \(\text{OPT}\). We say that \(C'\) and \(C^*\) are associated. The following lemma follows from the fact that the input is \(\beta\)-stable for \(\beta := \varepsilon/\log n\) and that the solution \(S\) is a \({5}\)-approximation by Lemma 9. Given a client or center \(a\) and a distance \(r\), we let \(B(a,r)\) be the set of clients and centers at distance at most \(r\) from \(a\). This lemma is originally proved in [45], we include a proof for completeness. In this proof we use in a few places the assumption that \(\varepsilon>0\) is upper bounded by a small enough constant.

Let \(C^*\) be a pure cluster of \(\text{OPT}\) and \(C'\) be the associated cluster of \(S\). Let \(c^*\) be the center of \(C^*\) and \({c'}\) be the center of \({C'}\). We define \(t(c^*) := {c'}\). For any client \(p \in C^*\), let \(r(p) := d(p, {c'}) = d(p, t(c^*))\). We have the following lemma which is the only lemma that requires that the solution \(S\) is obtained via the local search (the proof of the previous lemma only used that it was a constant-factor approximation). In words, it says that \(S\) approximates the connection cost of clients belonging to pure clusters of the optimal solution almost perfectly.

4.2 Cheap Clusters and \(D\)-Sample Process to Hit Expensive Clusters↩︎

In the previous section, we showed that the cost of pure clusters in \(\text{OPT}\) is close to to their optimal cost in our local search solution \(S\). Our goal in this section is to “hit” those non-pure clusters of \(\text{OPT}\) that have a high cost in \(S\). We say that a non-pure cluster \(C^*\) of \(\text{OPT}\) with center \(c^*\) is basic-cheap if the total cost in \(S\) of the clients in \(C^*_\text{avg}\) is less than \(\varepsilon^{5}\text{opt}/\log n\) or if there exists a center of \(S\) at distance at most \((1+\varepsilon)\text{avg}_{C^*,\text{OPT}} + \varepsilon\gamma_{C^*}\) from \(c^*\), where \(\gamma_{C^*} := \frac{1}{|C^*|} \sum_{p\in C^*} (\text{OPT}_p + S_p)\); in the latter case we also say that \(C^*\) is covered by \(S\).

The following procedure, that aims to “hit” all clusters of \(\text{OPT}\) that are non-pure and non-basic-cheap, is inspired by the classic \(k\)-means++ algorithm and its so-called \(D^2\)-sampling procedure to sample clients proportional to their cost in solution \(S\). For \(k\)-median this becomes \(D\)-sampling (instead of \(D^2\)-sampling).

4.2.0.1 \(D\)-\(Sample(S,s)\)

\(W \leftarrow \emptyset\) Add to \(W\) one client \(p\) sampled with probability \(\frac{d(p, S)}{\text{cost}(S)}\) return \(W\)

Next let \(W\) be the set returned by \(D\)-\(Sample(S,s^*)\) with \[s^* = {5} \cdot \frac{\log n}{\varepsilon^{5}}\ln\left( \frac{7}{\varepsilon^{2}}\right)\,.\] We say that \(W\) hits a cluster \(C^*\) of \(\text{OPT}\) if \(C^*_{\text{avg}}\cap W\neq \emptyset\), i.e., if \(W\) contains at least one leader of \(C^*\). We have the following lemma that says that we hit all non-pure and non-basic-cheap clusters except for a set \(V\) of clusters that have an insignificant cost in \(S\).

For a non-pure optimal cluster \(C^*\) with center \(c^* \in \text{OPT}\), we let \(t(c^*)\) be the closest center in \(S\) to \(c^*\), and for any \(p \in C^*\), we let the replacement cost of \(p\) be \(r(p) := d(p, t(c^*))\).

4.2.0.2 Successful \(W\).

We say that the set of clients \(W\) obtained from the D-sample process is a successful sample if ?? holds. We define the following two types of \(\text{OPT}\) clusters. We say that a non-pure cluster \(C^*\) of \(\text{OPT}\) with center \(c^*\) is cheap if it is basic-cheap or is in \(V\); a non-pure cluster is expensive otherwise. In other words, a cluster \(C^*\) of the optimal solution is expensive if it is a non-pure and non-basic-cheap cluster such that \(C^*_{avg} \cap W \neq \emptyset\).

Assuming that \(W\) is successful, we have a good bound on the cost of the clients assigned to cheap centers in the optimal solution.

Given \(S\) and \(W\), the set of clusters of the optimal solution \(\text{OPT}\) is thus partitioned into pure clusters, cheap clusters, and expensive clusters. We let \(\hat{\text{OPT}}\) be the centers of \(\text{OPT}\) that are expensive. We further define the set \(D^*_{\texttt{exp}}\subseteq D\) to be the subset of clients that belong to the expensive clusters in \(\text{OPT}\). We have thus partitioned \(D\) into sets \(D^*_{\texttt{pure}}, D^*_{\texttt{cheap}}\), and \(D^*_{\texttt{exp}}\) depending on the type of optimal cluster they belong to. Lemma 11 bounds the cost of the clients in \(D^*_{\texttt{pure}}\) in \(S\) and Lemma 13 bounds the cost of the clients in \(D^*_{\texttt{cheap}}\). For future reference, we summarize these two lemmas (by weakening the upper bound for clients in \(D^*_{\texttt{pure}}\)).

It follows that the connection cost in solution \(S\) of clients in \(D- D^*_{\texttt{exp}}\) is within a factor \(2\) of their cost in the optimal solution. The remaining part of the algorithm is thus devoted to modifying \(S\) to obtain a small connection cost of the clients in \(D^*_{\texttt{exp}}\) without significantly increasing the cost of the other clients.

4.3 Identifying Balls of Expensive Clusters↩︎

By the definition of expensive clusters, each expensive cluster \(C^*\) of \(\text{OPT}\) satisfies \(C^*\cap W \neq \emptyset\) where \(W\) is the sample obtained by running the sampling procedure of the last subsection. Here, our goal is to guess a subset \(\mathcal{B}\) of balls so that for each expensive cluster \(C^*\) there is a ball \(B(\ell, \rho) \in \mathcal{B}\) so that \(\ell\), which we refer to as a leader, is in \(C^*_{avg}\) and \(\rho\) is a very close approximation to \(\text{avg}_{C^*, \text{OPT}}\). This guarantees that the center \(c^* \in \hat{\text{OPT}}\) of cluster \(C^*\) is in \(B(\ell, \rho)\) and that no other center in \(B(\ell, \rho)\) is "too" far from \(c^*\) since the radius of the ball is \(\approx \text{avg}_{C^*, \text{OPT}}\). The balls \(\mathcal{B}\) will then be used when we approximate the centers in \(\hat{\text{OPT}}\) via submodular function maximization subject to a partition matroid constraint (the balls will correspond to the partitions of the matroid). As the algorithm does not know the set of expensive clusters, it enumerates all subsets of \(W\), and for each guessed point, it enumerates a constant number of radii.

4.3.0.1 \(ballGuess(S,W)\)

\(\mathcal{L}_\texttt{ball} \leftarrow \emptyset\) add \(\mathcal{B}= \left\{B(p_1, (1+\varepsilon^3)^{i_1}), B(p_2, (1+\varepsilon^3)^{i_2}), \ldots, B(p_q, (1+\varepsilon^3)^{i_q}\right\}\) to \(\mathcal{L}_{\texttt{ball}}\) return \(\mathcal{L}_\texttt{ball}\)

We show that the \(ballGuess()\) runs in polynomial time and that one of the subsets \(\mathcal{B}\) of balls that the procedure constructs is a correct guess: every expensive cluster \(C^*\) has a leader, and \(\text{avg}_{C^*, \text{OPT}}\) is guessed approximately correctly. We say that a set of balls \(\mathcal{B}\) is a valid set of balls if it satisfies the following: For each expensive cluster \(C^*\) of \(\text{OPT}\), we have a ball \(B(\ell, \rho) \in \mathcal{B}\) such that \(\ell\in C^*_{avg}\) is a leader and \[\text{avg}_{C^*,\text{OPT}} \leq \rho \leq \text{avg}_{C^*,\text{OPT}} + \varepsilon\gamma_{C^*},\] where we recall that \(\gamma_{C^*} = \frac{1}{|C^*|} \sum_{p \in C^*} (\text{OPT}_p + S_p)\).

We thus have that the ball procedure produces a family \(\mathcal{L}_{\texttt{ball}}\) such that a set \(\mathcal{B}\in \mathcal{L}_{\texttt{ball}}\) satisfies the conditions of the lemma. While our algorithm will try all possible sets in \(\mathcal{L}_{\texttt{ball}}\) (since it does not know which one is valid), we do our analysis by considering the run of the algorithm when it selects this set \(\mathcal{B}\) of valid balls.

4.3.1 Dummy Centers and Mixed Solutions \(M_O\) and \(M_D\)↩︎

Next, the algorithm creates, for each ball \(B(\ell, \rho) \in \mathcal{B}\) with center \(\ell\) and radius \(\rho\), a dummy center \(\delta\) at distance \(\rho\) from \(\ell\) and at distance \(\rho + d(\ell, p)\) from any other input point \(p\). Let \(\Lambda\) be the set of dummy centers, so \(|\Lambda| = |\mathcal{B}|\). Recall that \(D^*_{\texttt{exp}}\) is the set of clients that are in an expensive cluster of \(\text{OPT}\), i.e., served by a center in \(\hat{\text{OPT}}\) in the optimal solution.

4.3.1.1 Definition of the mixed solutions \(M_O\) and \(M_D\).

Next, let us analyze the cost of the swap \((\hat{\text{OPT}}, S_0)\). Namely, of the solution \(M_O = S - S_0 \cup \hat{\text{OPT}}\), where \(M\) in \(M_O\) stands for “mixed solution” and the subscript \(O\) stands for that the mixed solution is obtained by swapping in some elements from \(\text{OPT}\) (and removing \(S_0\)). We will also analyze the “dummy” version of \(M_O\) where instead of swapping in \(\hat{\text{OPT}}\), we swap in the dummy centers \({\Lambda}\). We denote that solution by \(M_D = S - S_0 \cup \Lambda\), where the subscript \(D\) stands for “dummy”.

Notice that \(M_{O}\) contains \(S- S_0\) and \(\hat{\text{OPT}}\). Therefore, if we sum up the above bounds for all clients we get \[\begin{align} \text{cost}(M_O) & \leq \sum_{p\in D^*_{\texttt{exp}}} \text{OPT}_p + \sum_{p\in D{-} D^*_{\texttt{exp}}} r(p)\,, \end{align}\] which by Lemma 14 is at most \(\sum_{p\in D^*_{\texttt{exp}}} \text{OPT}_p + \sum_{p\in D{-}D^*_{\texttt{exp}}} 2 \text{OPT}_p + O(\varepsilon\cdot \text{opt})\) (assuming that that the sample \(W\) was successful). By swapping \(S_0\) with \(\hat{\text{OPT}}\) we thus get a \(1\)-approximation on the clients \(D^*_{\texttt{exp}}\) and a \(2\)-approximation of the remaining clients (plus a small error term). Our goal in the next sections will thus be to approximate this swap. The next few steps will be aimed at simplifying (or guessing parts of) \(S_0\). The last step will then approximate \(\hat{\text{OPT}}\) and the remaining part of \(S_0\) by submodular function maximization subject to a partition matroid constraint. For that part, it will be helpful to have a bound on the dummy solution as well; specifically, a modified version of it (see Lemma 19 and Claim 7). For intuition of those statements, let us here say that one can show \[\begin{align} \text{cost}(M_D) & \leq \sum_{p\in D^*_{\texttt{exp}}} 3\text{OPT}_p + \sum_{p\in D- D^*_{\texttt{exp}}} r(p) + O(\varepsilon\cdot \text{opt})\,\, \end{align}\] by observing that only the clients \(D^*_{\texttt{exp}}\) have a different connection cost in \(M_D\) than in \(M_O\). Moreover, each such client \(p\in D^*_{\texttt{exp}}\) that was previously assigned to a center \(c^* \in \hat{\text{OPT}}\), and belongs to cluster \(C^*\) of \(\text{OPT}\), has an associated dummy center \(\delta\) at distance at most \(d(p, c^*) + 2 \text{avg}_{C^*, \text{OPT}} + \varepsilon\gamma_{C^*}\) (assuming the set \(\mathcal{B}\) of balls is valid). Simplifications then give the stated inequality as \(|C^*| \text{avg}_{C^*, \text{OPT}} \leq (1+2\varepsilon) \sum_{p\in C^*} \text{OPT}_p\) and \(|C^*| \varepsilon\gamma_{C^*} = \varepsilon\sum_{p\in C^*} ( \text{OPT}_p + S_p)\).

4.4 Removal of Expensive Centers of \(S_0\)↩︎

Thus, it remains to show that our algorithm can yield a good approximation to the gain that the swap \((\hat{\text{OPT}}, S_0)\) would provide. Of course, it will not necessarily be optimum, but we can show it is enough to conclude the proof of our theorem. We focus on the iteration of the procedure that produces valid ball guesses. In particular, at this point given that \(W\) is successful and the ball guesses are valid, the number of balls in our ball guess is equal to \(|S_0|=|\hat{\text{OPT}}|=|\Lambda|\leq \frac{\log n}{\varepsilon^3}\). Our algorithm then makes use of the following procedure that takes as input the local search solution \(S\) and the set \(\Lambda\) of dummy centers.

4.4.0.1 \(expRem(S,\Lambda)\)

\(\mathcal{L}_{\text{exp}}\leftarrow \emptyset\) \(\mathcal{Q}\leftarrow \emptyset\) With probability 1/2 do the following. Consider the clustering induced by \(\Lambda\cup S-\mathcal{Q}\) and, for each \(c\in S-\mathcal{Q}\), let \(\text{cost}(c)\) be the cost of the cluster associated with \(c\) in the considered solution Sample one \(c\in S-\mathcal{Q}\) with probability \(\frac{\text{cost}(c)}{\sum_{c'\in S-\mathcal{Q}}\text{cost}(c')}\) Set \(\mathcal{Q}\leftarrow \mathcal{Q}\cup \{c\}\)

\(\mathcal{L}_{\text{exp}}\leftarrow \mathcal{L}_{\text{exp}}\cup \{\mathcal{Q}\}\) return \(\mathcal{L}_{\text{exp}}\)

The goal of the above procedure is to guess a subset \(\mathcal{Q}\) of all “costly” centers in \(S_0\) (the set \(\mathcal{L}_{\text{exp}}\) contains all guesses). Specifically, if we consider the solution \((S - \mathcal{Q}) \cup \Lambda\), then we wish that the cost of the clusters corresponding to the remaining centers in \(S_0 - \mathcal{Q}\) is at most \(\varepsilon\cdot \text{opt}\). Formally, the clusters corresponding to \(S_0 - \mathcal{Q}\) in \(S - \mathcal{Q}\cup \Lambda\) consists of all the clients whose closest center in \(S - \mathcal{Q}\cup \Lambda\) is from \(S_0 - \mathcal{Q}\). If we let \(D' \subseteq D\) be those clients then the total cost in solution \(S- \mathcal{Q}\cup \Lambda\) of the clusters with centers in \(S_0 - \mathcal{Q}\) is defined as \[\sum_{p\in D'} d(p, S- \mathcal{Q}\cup \Lambda) = \sum_{p\in D'} d(p, S_0 - \mathcal{Q})\,,\] where the equality holds because of the definition of \(D'\).

4.4.1 Consistently Assigning Clients in Mixed Solutions and the sets \(\mathcal{U}\) and \(\mathcal{R}\)↩︎

While our algorithm tries all possible \(\mathcal{Q}\in \mathcal{L}_{\text{exp}}\), we focus on the execution path of a set \(\mathcal{Q}\) of centers satisfying the properties of Lemma 18, i.e.,

1. \(\mathcal{Q}\subseteq S_0\), and

2. the cost in the solution \(S - \mathcal{Q}\cup \Lambda\) of the clusters with centers in \(S_0 - \mathcal{Q}\) is at most \(\varepsilon\cdot \text{opt}\).

We define the solution \(S_{\mathcal{Q}} := S- \mathcal{Q}\cup \Lambda\) and for a center \(c\in S_{\mathcal{Q}}\) we let \(S_{\mathcal{Q}}(c)\) be the subset of clients closest to \(c\) (i.e., assigned to \(c\)) in the solution \(S_{\mathcal{Q}}\). The second property above allows us to consider each cluster \(S_{\mathcal{Q}}(c)\), \(c\in S_0 - \mathcal{Q}\), as contracted by paying a small extra cost of \(\varepsilon\cdot \text{opt}\). In particular, this allows us to give a “consistent” assignment \(\mu_O\) of clients in the mixed solutions. Here, consistent means that all clients in \(S_Q(c)\), for \(c\in S_0 - \mathcal{Q}\), are assigned to the same center in the mixed solutions where all of \(S_0\) is removed.

4.4.1.1 Definition of \(\mu_O\) and \(\mu_D\).

We modify how the clients are assigned in the solution \(M_O\) to obtain the assignment \(\mu_O\). For every \(c \in S_0 - \mathcal{Q}\), all the clients in \(S_{\mathcal{Q}}(c)\) are reassigned to the same center of \(M_O\) as follows. Let \(c_1\) be the center of \(\hat{\text{OPT}}\) that is the closest to \(c\) and let \(c_2\) be the center of \(M_O-\hat{\text{OPT}}= S - S_0\) that is the closest to \(c\). The clients of \(S_{\mathcal{Q}}(c)\) are all assigned to either \(c_1\) or \(c_2\):

• If \(d(c,c_1) \le d(c,c_2)/2\), assign \(S_{\mathcal{Q}}(c)\) to \(c_1\); \(S_{\mathcal{Q}}(c)\) is called a type-1 cluster.

• Otherwise (\(d(c,c_1) > d(c,c_2)/2\)), assign \(S_{\mathcal{Q}}(c)\) to \(c_2\); \(S_{\mathcal{Q}}(c)\) is called a type-2 cluster.

Let \(T_1\) be the set of clients in a type-1 cluster and \(T_2\) the set of clients in a type-2 cluster. The remaining clients in \(D^*_{\texttt{exp}}- (T_1 \cup T_2)\) are assigned to their closest centers in \(\hat{\text{OPT}}\), and the remaining clients in \((D- D^*_{\texttt{exp}})- (T_1 \cup T_2)\) are assigned to their closest centers in \(S- S_0\). Notice that, even neglecting the extra cost due to the consistent assignment, the above assignment of clients in \(T_2\) is suboptimal when \(d(c,c_2)>d(c,c_1)>d(c,c_2)/2\). The motivation for this reassignment is technical. More specifically, it will be used in Lemma 19 to have a better upper bound on the cost of clients in \(C^*\cap T_1\) for a non-expensive cluster \(C^*\) (case b2). This leads to a larger upper bound on the cost of clients in \(C^*\cap T_2\) for an expensive cluster \(C^*\) (case a3), which is however tolerable.

We further obtain an assignment \(\mu_D\) of clients in \(M_D\) by modifying \(\mu_O\) as follows: each client \(p\) with \(\mu_O(p) \in \hat{\text{OPT}}\) is assigned to the associated dummy center by \(\mu_D\). So for each client \(p\) we have \(\mu_D(p) = \mu_O(p)\) unless \(\mu_O(p)\in \hat{\text{OPT}}\) in which case \(\mu_D(p)\) equals the dummy center associated with \(\mu_O(p)\).

4.4.1.2 Sets \(\mathcal{R}\) and \(\mathcal{U}\).

By the definition of type-1 and type-2 cluster, we can split the set of centers of \(S_0 - \mathcal{Q}\) into two groups \(\mathcal{R}\) and \(\mathcal{U}\). Let \(\mathcal{R}\) be the set of centers of \(S_0- \mathcal{Q}\) whose set of clients is completely assigned to a center of \(\hat{\text{OPT}}\) in the assignment \(\mu_O\), and let \(\mathcal{U}= S_0 - \mathcal{Q}- \mathcal{R}\) be the remaining ones that are assigned to centers in \(S- S_0\).

We end this section by analyzing the costs of the assignments \(\mu_O\) and \(\mu_D\). Recall that we use the notation \(\text{cost}(M_O,\mu_O)\) to denote the cost of \(M_O\) equipped with assignment \(\mu_O\) and, similarly \(\text{cost}(M_D, \mu_D)\) for the cost of \(M_D\) equipped with assignment \(\mu_D\). We say that the selection of \((W, \mathcal{B}, \mathcal{Q})\) is successful, if the sample \(W\) selected in 4.2 is successful, the set of balls \(\mathcal{B}\) from Section 4.3 is valid, and \(\mathcal{Q}\) selected in this section satisfies the properties of Lemma 18.

4.5 Removal of Cheap Centers in \(S_0\)↩︎

At this stage we have defined a clustering \(S_{\mathcal{Q}} = S - \mathcal{Q}\cup \Lambda\), where \(\Lambda\) is the set of dummy centers. Recall that the mixed solution \(M_O\) equals \(S-S_0 \cup \hat{\text{OPT}}\). So \(S_\mathcal{Q}- \Lambda\) represents progress compared to \(S\) in that we have already removed a subset \(\mathcal{Q}\) of \(S_0\). Furthermore, with respect to the assignment of clients \(\mu_O\), we have that the remaining centers \(S_0 - Q\), which we want to remove, are divided into two sets \(\mathcal{R}\) and \(\mathcal{U}\). The clusters with centers in \(\mathcal{R}\) are completely assigned (by \(\mu_O\)) to centers in \(\hat{\text{OPT}}\), and every cluster with center in \(\mathcal{U}\) is completely assigned to a center in \(S - S_0\). The task of this section is to make further progress by guessing the centers in \(\mathcal{U}\) and their reassignment to centers in \(S- S_0\). This turns out to be a difficult task, and we will instead “approximately” guess a set \(\widetilde{\mathcal{U}}\) and reassignment \(\widetilde{\mu}\) of the clients of those clusters. Specifically, we will output a solution \(S_{\mathcal{Q}\cup \widetilde{\mathcal{U}}} = S_{\mathcal{Q}} - \widetilde{\mathcal{U}}\) (obtained by removing \(\widetilde{\mathcal{U}}\) from \(S_{\mathcal{Q}}\)) and an assignment \(\widetilde{\mu}\) of clients to centers in \(S_\mathcal{Q}-\widetilde{\mathcal{U}}\). This is done through the following lemma. Recall that for \(c\in S_{\mathcal{Q}}\), \(S_{\mathcal{Q}}(c)\) is the set of clients assigned to \(c\) in \(S_\mathcal{Q}\), i.e., closest to \(c\) among all centers in \(S_\mathcal{Q}\).

In words, the above properties of \(\widetilde{\mu}\) say that we maintain the assignment of clients whose closest center remains the same, and the clients associated to the removed centers \(\widetilde{\mathcal{U}}\) are reassigned to centers not in \(\mathcal{R}\) at no higher cost (up to \(O(\varepsilon\cdot \text{opt})\)) than the cost of the reassignment of \(\mathcal{U}\) in the modified solution \(M_O\).

Let \(\mathcal{X}\) be the centers in \(S-S_0\) to which the points \(p\in S_{\mathcal{Q}}(c)\) with \(c\in \mathcal{U}\) are assigned according to \(\mu_O\). Notice that \(|\mathcal{X}|\leq |\mathcal{U}|\) and \(\mathcal{X}\cap (\mathcal{Q}\cup \mathcal{U}\cup \mathcal{R})=\emptyset\). We assume that the values of \(|\mathcal{U}|\), \(|\mathcal{R}|\), and \(|\mathcal{X}|\) are known. This can be achieved by trying, for each such value, all the integers between \(0\) and \(|S_0|\leq \frac{\log n}{\varepsilon^3}\). Let \(\ell:=|\mathcal{U}|+|\mathcal{R}|+|\mathcal{X}|\leq 2|\mathcal{U}|+|\mathcal{R}|\leq 2|S_0 - \mathcal{Q}|\). Then we run the recursive procedure \(cheapRem()\) described in the box with input \((\mathcal{U}',\mathcal{R}',\mathcal{X}',\mathcal{N},\widetilde{\mathcal{U}})=(\emptyset,\emptyset,\emptyset,\emptyset,\emptyset)\). We assume that \(cheapRem()\) has access to the quantities \(S\), \(\mathcal{Q}\), \(|\mathcal{U}|\), \(|\mathcal{R}|\), \(|\mathcal{X}|\) and \(\ell\), as well as to a global variable \(\mathcal{L}_{cheap}\), which is initialized to \(\emptyset\). The intuition for the parameters is as follows. Intuitively \(\mathcal{U}'\), \(\mathcal{R}'\) and \(\mathcal{X}'\) are subsets of \(\mathcal{U}\), \(\mathcal{R}\) and \(\mathcal{X}\), resp., that we have already identified, while \(\widetilde{\mathcal{U}}\) is the current value of the set \(\widetilde{\mathcal{U}}\) under construction. Intuitively, \(\mathcal{N}\) are the centers to which the points \(p\in S_{\mathcal{Q}}(c)\) with \(c\in \widetilde{\mathcal{U}}\) are reassigned, namely \(\widetilde{\mu}(p)\in \mathcal{N}\). At the end of the root call, the global variable \(\mathcal{L}_{cheap}\) contains the desired collection of sets \(\widetilde{\mathcal{U}}\) as in Lemma 20. Whenever some \(\widetilde{\mathcal{U}}\) is added to \(\mathcal{L}_{cheap}\), we define a corresponding \(\widetilde{\mu}\) as follows: For each \(p\in S_{\mathcal{Q}}(c)\), \(\widetilde{\mu}(p)=c\) if \(c\in S_{\mathcal{Q}}-\widetilde{\mathcal{U}}\). Otherwise, i.e. if \(c\in \widetilde{\mathcal{U}}\), \(\widetilde{\mu}(p)=next(c)\in \mathcal{N}\), where \(next(c)\) is defined in the recursive call when \(c\) is added to \(\widetilde{\mathcal{U}}\).

4.5.0.1 \(cheapRem(\mathcal{U}',\mathcal{R}',\mathcal{X}',\mathcal{N},\widetilde{\mathcal{U}})\)

Add \(\widetilde{\mathcal{U}}\) to \(\mathcal{L}_{cheap}\) and, for each \(c\in \widetilde{\mathcal{U}}\), set \(next(c)\) to the closest center to \(c\) in \(S-\mathcal{Q}-\widetilde{\mathcal{U}}-\widetilde{\mathcal{R}}\) halt Add \(\widetilde{\mathcal{U}}\) to \(\mathcal{L}_{cheap}\) and halt Let \(c\in S-\mathcal{Q}-\mathcal{R}'-\mathcal{X}'-\mathcal{N}-\widetilde{\mathcal{U}}\) minimize \(R(c):=\sum_{p\in S_{\mathcal{Q}}(c)}d(p,next(c))\), where \(next(c)\) is the closest center to \(c\) in \(S-\mathcal{Q}-\mathcal{U}'-\mathcal{R}'-\widetilde{\mathcal{U}}-\{c\}\). \(cheapRem(\mathcal{U}',\mathcal{R}',\mathcal{X}'\cup \{c\},\mathcal{N},\widetilde{\mathcal{U}})\) \(cheapRem(\mathcal{U}',\mathcal{R}'\cup \{c\},\mathcal{X}',\mathcal{N},\widetilde{\mathcal{U}})\) \(cheapRem(\mathcal{U}',\mathcal{R}',\mathcal{X}',\mathcal{N}\cup \{next(c)\},\widetilde{\mathcal{U}}\cup \{c\})\) \(cheapRem(\mathcal{U}',\mathcal{R}'\cup \{next(c)\},\mathcal{X}',\mathcal{N},\widetilde{\mathcal{U}})\) \(cheapRem(\mathcal{U}'\cup \{next(c)\},\mathcal{R}',\mathcal{X}',\mathcal{N},\widetilde{\mathcal{U}})\) \(cheapRem(\mathcal{U}',\mathcal{R}',\mathcal{X}',\mathcal{N}\cup \{next(c)\},\widetilde{\mathcal{U}}\cup \{c\})\)

4.5.1 Mixed Solutions after the Removal of \(\widetilde{\mathcal{U}}\)↩︎

We let \((S_{\mathcal{Q}\cup \widetilde{\mathcal{U}}}, \widetilde{\mu})\) be the output of a successful run of the \(cheapRem()\) procedure, i.e., where \(\widetilde{\mathcal{U}}\in \mathcal{L}_{cheap}\) and its associated assignment \(\widetilde{\mu}\) satisfies the properties of Lemma 20. Recall that \(S_{\mathcal{Q}\cup \widetilde{\mathcal{U}}}\) consists of the centers \(S' = S - \mathcal{Q}- \widetilde{\mathcal{U}}\) and the dummy centers \(\Lambda\). Further recall that \(M_O\) consists of the centers \(S- S_0 = S - \mathcal{Q}- \mathcal{U}- \mathcal{R}\) and \(\hat{\text{OPT}}\). \(M_D\) is the same set of centers except that \(\hat{\text{OPT}}\) is replaced by \(\Lambda\). Notice that some centers of \(M_O\) and \(M_D\) are now removed if \(\widetilde{\mathcal{U}}- \mathcal{U}\neq \emptyset\). To take care of this, we modify these mixed solutions to obtain \(M'_O\) and \(M'_D\).

We first define \(M'_O\); the definition of \(M'_D\) is then very similar. The centers of \(M'_O\) are \(S- \mathcal{Q}- \widetilde{\mathcal{U}} - \mathcal{R}\) and \(\hat{\text{OPT}}\). Hence, the difference between \(M_O\) and \(M'_O\) is that in \(M_O\) we remove \(\mathcal{U}\) from \(S\) and in \(M'_O\) we remove \(\widetilde{\mathcal{U}}\). In other words, \(M'_O = M_O \cup \mathcal{U}- \widetilde{\mathcal{U}}\). Similarly, we let \(M'_D = M_D \cup \mathcal{U}- \widetilde{\mathcal{U}}\). We update the assignment \(\mu_O\) of \(M_O\) to an assignment \(\mu'_O\) of \(M'_O\) (and the assignment \(\mu_D\) to \(\mu'_D\)). Recall that \(\mu_O\) assigns each client \(p\) to its closest center in \(\hat{\text{OPT}}\) (if \(p\in D^*_{\texttt{exp}}\)) or its closest center in \(S- S_0\) (if \(p\in D- D^*_{\texttt{exp}}\)) except for those clients that belong to a cluster \(S_{\mathcal{Q}}(c)\) with \(c\in \mathcal{U}\cup \mathcal{R}\). Indeed, the clients in \(S_\mathcal{Q}(c)\) are all assigned to the center of \(\hat{\text{OPT}}\) that is closest to \(c\) if \(c\in \mathcal{R}\), and if \(c\in \mathcal{U}\) they are all assigned to the center in \(S - S_0\) that is closest to \(c\). We also recall that \(\mu_D\) is the same as \(\mu_O\) except when \(\mu_O(p) \in \hat{\text{OPT}}\) in which case \(\mu_O(p)\) is replaced by its corresponding dummy center.

4.5.1.1 Definitions of \(\mu_O'\) and \(\mu_D'\).

For clients \(p\in S_{\mathcal{Q}}(c)\) with \(c \not\in \mathcal{U}\cup \widetilde{\mathcal{U}}\cup \Lambda\), we define \(\mu_O'(p) = \mu_O(p)\). For \(p\in S_{\mathcal{Q}}(c)\) with \(c\in \Lambda\), we let \(\mu'_O(p)\) be the closest center in \(\hat{\text{OPT}}\). Finally, for \(p\in S_{\mathcal{Q}}(c)\) with \(c\in \mathcal{U}\cup \widetilde{\mathcal{U}}\), we define \(\mu'_O(p) = \widetilde{\mu}(p)\).

The assignment \(\mu'_D\) is obtained in the same way from \(\mu_D\) with the difference that we use \(\Lambda\) instead of \(\hat{\text{OPT}}\): For clients \(p\in S_{\mathcal{Q}}(c)\) with \(c \not\in \mathcal{U}\cup \widetilde{\mathcal{U}}\cup \Lambda\), we define \(\mu_D'(p) = \mu_D(p)\). For \(p\in S_{\mathcal{Q}}(c)\) with \(c\in \Lambda\), we let \(\mu'_D(p)\) be the closest center in \(\Lambda\). Finally, for \(p\in S_{\mathcal{Q}}(c)\) with \(c\in \mathcal{U}\cup \widetilde{\mathcal{U}}\), we define \(\mu'_D(p) = \widetilde{\mu}(p)\).

This completes the definition of \(\mu'_O\) and \(\mu'_D\). We remark that we have \(\mu'_O(p) = \mu_O(p)\) and \(\mu'_D(p) = \mu_D(p)\) for all \(p\in S_\mathcal{Q}(c)\) with \(c\not \in \mathcal{U}\cup \widetilde{\mathcal{U}}\cup \Lambda\).

We continue by arguing that \(\mu'_O\) is well-defined, i.e., that \(\mu'_O(p) \in M_O'\) for every \(p\in D\) (the proof for \(\mu'_D\) is the same). This is immediate for a client \(p\in S_\mathcal{Q}(c)\) with \(c \in \Lambda\). For a client \(p\in S_{\mathcal{Q}}(c)\) with \(c\in \cal U \cup \widetilde{\mathcal{U}}\), it holds because, by Lemma 20, \(\widetilde{\mu}(p)\) equals \(c\in M'_O\) if \(c \in \mathcal{U}- \widetilde{\mathcal{U}}\) and otherwise \(\widetilde{\mu}(p) \in S- \mathcal{Q}- \widetilde{\mathcal{U}}- \mathcal{R}\subseteq M'_O\). It remains to verify that \(\mu_O(p) \in M_O'\) for a client \(p\in S_\mathcal{Q}(c)\) with \(c\not \in \mathcal{U}\cup \widetilde{\mathcal{U}}\cup \Lambda\). If \(c\in \mathcal{R}\), we have \(\mu_O(p) \in \hat{\text{OPT}}\subseteq M'_O\). Similarly, if \(c \not \in \mathcal{U}\cup \widetilde{\mathcal{U}}\cup \Lambda \cup \mathcal{R}\) and \(p\in D^*_{\texttt{exp}}\) we have \(\mu_O(p) \in \hat{\text{OPT}}\subseteq M'_O\). In the remaining case when \(c \not \in \mathcal{U}\cup \widetilde{\mathcal{U}}\cup \Lambda \cup \mathcal{R}\) and \(p\in D- D^*_{\texttt{exp}}\), \(\mu_O(p)\) equals \(p\)’s closest center in \(S- S_0\). As \(p\in S_\mathcal{Q}(c)\), we thus have \(\mu_O(p) = c \in S - (S_0 \cup \widetilde{\mathcal{U}}) \subseteq M'_O\).

The following upper bound on \(\text{cost}(M'_O, \mu'_O) + \text{cost}(M'_D, \mu'_D)\) is a fairly immediate consequence of the assumption that the cheap-removal process is successful (Property 3c of Lemma 20). Similarly to before, we say that the selection of \((W, \mathcal{B}, \mathcal{Q}, \widetilde{\mathcal{U}},\widetilde{\mu})\) is successful, if the sample \(W\) selected in 4.2 is successful, the set of balls \(\mathcal{B}\) from Section 4.3 is valid, \(\mathcal{Q}\) selected in Section 4.4 satisfies the properties of Lemma 18, and \(\widetilde{\mathcal{U}},\widetilde{\mu}\) selected in this section satisfies the properties of Lemma 20.

To better understand \(\text{cost}(M'_O, \mu'_O)\), let us consider the cost \(d(p, \mu'_O(p))\) of a single client \(p\):

• If \(p \in S_{\mathcal{Q}}(c)\) with \(c\not\in \widetilde{\mathcal{U}}\cup \mathcal{R}\) then \(\widetilde{\mu}(p) = c\) by Property 3a of Lemma 20. Moreover, \(\mu'_O(p)\) assigns \(p\) either to a center in \(\hat{\text{OPT}}\) or to one in \(S - \mathcal{Q}- \widetilde{\mathcal{U}}- \cal R\) and we have \(d(p, c) \leq d(p, S - \mathcal{Q}- \widetilde{\mathcal{U}}- \cal R)\). Hence, in either case, we have \[d(p, \mu'_O(p)) \geq d(p, \{\widetilde{\mu}(p)\} \cup \hat{\text{OPT}}) = d(p, \{\widetilde{\mu}(p)\} \cup \hat{\text{OPT}}\cup \Lambda) \,.\]

• If \(p\in S_{\mathcal{Q}}(c)\) with \(c\in \mathcal{R}\) then \(\mu'_O(p) = \mu_O(p) = c^*\in \hat{\text{OPT}}\) where \(c^*\) is the center of \(\hat{\text{OPT}}\) that is closest to \(c\). So \[d(p, \mu_O'(p)) = d(p, c^*)\,.\]

• If \(p \in S_{\mathcal{Q}}(c)\) with \(c\in \widetilde{\mathcal{U}}\) then \(\mu'_O(p) = \widetilde{\mu}(p)\) and so \[d(p, \mu_O'(p)) \geq d(p, \{\widetilde{\mu}(p)\} \cup \hat{\text{OPT}}\cup \Lambda).\]

Similarly, we can analyze \(d(p, \mu_D(p))\) by replacing \(\hat{\text{OPT}}\) with the set \(\Lambda\) of dummy centers (and \(c^*\) by its associated dummy center). Summarizing, we have \[\begin{align} \text{cost}(M'_O, \mu'_O) &\geq \sum_{c\in S_{\mathcal{Q}} - \mathcal{R}}\sum_{p\in S_{\mathcal{Q}}(c)} d\left(p, \{c\} \cup \hat{\text{OPT}}\cup \Lambda\right) + \sum_{c\in \mathcal{R}} \min_{c' \in \hat{\text{OPT}}} \sum_{p\in S_{\mathcal{Q}}(c)} d\left(p, c' \right)\\ \intertext{and} \text{cost}(M'_D, \mu'_D) &\geq \sum_{c\in S_{\mathcal{Q}} - \mathcal{R}}\sum_{p\in S_{\mathcal{Q}}(c)} d\left(p, \{c\} \cup \Lambda\right) + \sum_{c\in \mathcal{R}} \min_{c'\in \Lambda}\sum_{p\in S_{\mathcal{Q}}(c)} d\left(p, c'\right) \end{align}\]

Furthermore, by Properties 3a and 3b of Lemma 20, we have that, for every \(c\in \mathcal{R}\), the set \(S_{\mathcal{Q}}(c)\) of clients assigned to \(c\) in \(S_{\mathcal{Q}}\) equals the set \(\widetilde{\mu}^{-1}(c)\) of clients assigned by \(\widetilde{\mu}\). So, if we let \(\{C_c\}_{c\in S_{\mathcal{Q}\cup \widetilde{\mathcal{U}}}}\) be the partitioning of the set \(D\) of clients according to \(\widetilde{\mu}\), i.e., \(C_c = \{p\in D\mid \widetilde{\mu}(p) =c\}\), we can thus rewrite the above bounds on the cost as \[\begin{align} \text{cost}(M'_O, \mu'_O) &\geq \sum_{c\not \in \mathcal{R}}\sum_{p\in C_c} d\left(p, \{c\} \cup \hat{\text{OPT}}\cup \Lambda\right) + \sum_{c\in \mathcal{R}}\min_{c' \in \hat{\text{OPT}}}\sum_{p\in C_c} d\left(p, c'\right) \tag{20}\\ \intertext{and} \text{cost}(M'_D, \mu'_D) &\geq \sum_{c \not\in \mathcal{R}}\sum_{p\in C_c} d\left(p, \{c\} \cup \Lambda\right) + \sum_{c\in \mathcal{R}}\min_{c' \in \Lambda}\sum_{p\in C_c} d\left(p, c'\right)\,.\tag{21} \end{align}\] In the next section, we use these bounds to give a polynomial-time algorithm that outputs a solution \(S^*\) with \(k\) centers so that (see Lemma 21) \[\begin{align} \text{cost}(S^*) \leq \frac{(1+2\varepsilon)}{2} \left( \text{cost}(M'_O, \mu'_O) + \text{cost}(M'_D, \mu'_D) \right) + O(\varepsilon\text{opt}) \leq \sum_{p\in D} 2 \text{OPT}_p + O(\varepsilon\cdot \text{opt}) \end{align}\] where the second inequality is by Claim 7. So the proof of Lemma 21 in the next subsection is the final step in the proof of Theorem [thm:mainadditivecenters] (see also Section 4.7 where we put everything together to prove Theorem [thm:mainadditivecenters]).

4.6 Finding \(S^*\) via Submodular Optimization↩︎

In this section, we give a polynomial-time algorithm for finding the solution \(S^*\) by reducing the problem to maximizing a submodular function subject to a partition matroid constraint. Specifically, we prove the following lemma:

Recall that at this point the algorithm calculated the local search solution \(S\), sampled \(W\), guessed \(\mathcal{B}\), \(\mathcal{Q}\), and \(\widetilde{\mathcal{U}}\) with the assignment \(\widetilde{\mu}\) of the clustering \(S_{\mathcal{Q}\cup \widetilde{\mathcal{U}}}\). We assume that all these choices were successful guesses, i.e., that \((W, \mathcal{B}, \mathcal{Q}, \widetilde{\mathcal{U}}, \widetilde{\mu})\) is successful. Further recall the notation that we partition the clients into the clusters \(\{C_c\}_{c\in S_{\mathcal{Q}\cup \widetilde{\mathcal{U}}}}\) where \(C_c = \{ p\in D: \widetilde{\mu}(p) =c\}\).

Our goal is to give a polynomial-time algorithm that finds approximations of the sets \(\hat{\text{OPT}}\) and \(\mathcal{R}\) that only have slightly worse cost. We start by defining the feasible set of candidates for \(\hat{\text{OPT}}\) as a partition matroid. Recall that \(\hat{\text{OPT}}\) contains one center from each ball in \(\mathcal{B}\).

4.6.0.1 Definition of partition matroid \(\mathcal{M}_\mathcal{B}\).

We define the partition matroid that captures the constraint that we wish to open a center in each ball in \(\mathcal{B}\). Let \(F_\mathcal{B}\) be the (multi) subset of facility/center locations containing \(B\cap F\) for each ball \(B\in \mathcal{B}\). If a center \(c\) is in multiple balls in \(\mathcal{B}\), then \(F_\mathcal{B}\) contains one distinct copy of \(c\) for each ball. We let \(F_{\mathcal{B}}(B) \subseteq F_\mathcal{B}\) denote the facilities associated with \(B\in \mathcal{B}\). These sets satisfy the following two properties:

• The sets \(F_{\mathcal{B}}(B)\) partition \(F_\mathcal{B}\).

• For \(B \in \mathcal{B}\), \(F_{\mathcal{B}}(B)\) contains (a copy of) every facility in \(F\cap B\).

The first property holds since we took a unique copy of each center for each ball, and they are thus disjoint: \(F_\mathcal{B}(B) \cap F_\mathcal{B}(B') = \emptyset\) for distinct \(B,B' \in \mathcal{B}\). Indeed, while it is not better for the cost to open multiple copies of a center, we make the copies to ensure the above two properties. This allows us to define the partition matroid \(\mathcal{M}_\mathcal{B}= (F_\mathcal{B}, \mathcal{I})\) where \[\mathcal{I}= \{X \subseteq F_\mathcal{B}: |X\cap F_\mathcal{B}(B)| \leq 1for everyB\in \mathcal{B}\}\,.\] Moreover, since there is exactly one ball in \(\mathcal{B}\) for each center in \(\hat{\text{OPT}}\), we have \(\hat{\text{OPT}}\in \mathcal{I}\) (where we slightly abuse notation as we should take the copy of center \(c^*\in \hat{\text{OPT}}\) that belongs to its associated ball).

4.6.0.2 Core, concentrated and hit clusters.

Our goal is now to define a submodular function \(f\) so that we obtain a good approximation to \(\hat{\text{OPT}}\) by maximizing \(f\) over the matroid constraint \(\mathcal{M}_\mathcal{B}\). In particular, the domain of \(f\) is every subset of \(F_\mathcal{B}\). However, we need some additional steps before defining \(f\). In particular, we introduce the concept of the core of a cluster \(C_c\) and the notions of concentrated and hit clusters, which allow us to simplify the structure of centers in \(\mathcal{R}\). For a cluster \(C_c\), we define the core of \(C_c\) as \[\begin{gather} C^{\text{core}}_c = \left\{p \in C_c: d(p, c) \leq \varepsilon\cdot \frac{\text{cost}(S)}{|\mathcal{R}|\cdot |C_c|}\right\}\,. \end{gather}\] We further say that cluster \(C_c\) is concentrated if \[\begin{gather} |C^{\text{core}}_c| \geq (1-\varepsilon) |C_c| \end{gather}\] and it is hit by a set \(X\) of centers if there is a point \(p \in C^{\text{core}}_c\) such that \[\begin{gather} d(p, X) < d(p,c)\,. \end{gather}\] For shortness we will sometimes say that a center is concentrated (resp., hit), if the corresponding cluster is so.

4.6.0.3 Guessing the centers of \(\mathcal{R}\) that are not concentrated.

We further simplify the task of finding the set of centers \(\mathcal{R}\) by guessing the centers of \(\mathcal{R}\) that are not concentrated. Specifically, partition the set \(\mathcal{R}\) into \(\mathcal{R}_0\) and \(\mathcal{R}_1\), where \(\mathcal{R}_1\) contain those centers of \(\mathcal{R}\) that are concentrated and \(\mathcal{R}_0\) contains those that are not. We can correctly guess \(\mathcal{R}_0\) in polynomial time since the following simple claim shows that it is a subset of the centers whose cluster costs at least \(\varepsilon^2 \cdot \text{opt}/|\mathcal{R}|\), of which there are only \(O(|\mathcal{R}|/\varepsilon^2)\) many, and so guessing \(\mathcal{R}_0\) can thus be done in time \(2^{O(|\mathcal{R}|/\varepsilon^2)}\).

Now let \(\mathcal{P}\) be the potential centers that can be in \(\mathcal{R}\). Specifically, we let \(\mathcal{P}\) be the set that contains a center \(c\) in \(S -\mathcal{Q}- \widetilde{\mathcal{U}}\) if \(C_c\) equals the set of clients in \(S_{\mathcal{Q}}(c)\), where we recall that \(S_{\mathcal{Q}}(c)\) is the set of clients that are closest to \(c\) in the clustering \(S_{\mathcal{Q}}\). Notice that the algorithm has all the information \(S, \mathcal{B}, \mathcal{Q}, \widetilde{\mathcal{U}}\) and \(\widetilde{\mu}\) to calculate \(\mathcal{P}\). Furthermore, by Lemma 20, we have that no client from \(\widetilde{\mathcal{U}}\) was reassigned by \(\widetilde{\mu}\) to a center in \(\mathcal{R}\). So for \(c\in \mathcal{R}\) we have \(C_c = S_{\mathcal{Q}}(c)\). Hence, \(\cal R \subseteq \mathcal{P}\) and we can guess \(\mathcal{R}_0\) as follows:

4.6.0.4 Guessing \(\mathcal{R}_0\)

1. Let \(\mathcal{C}\) be the clusters of \(\mathcal{P}\) whose cost is at least \(\varepsilon^2 \cdot \text{opt}/|\mathcal{R}|\).

2. Output each subset of \(\mathcal{C}\).

By the above claim and the definition of \(\mathcal{P}\), one of the outputs is \(\mathcal{R}_0\). Furthermore, the above guessing procedure outputs a family of polynomial many subsets. Indeed, we have \(|\mathcal{R}| \leq \log(n)/\varepsilon^3\) by Lemma 10. Moreover, the total cost of the clusters in \(\mathcal{P}\) is \(O(\text{opt})\). To see this notice that the clusters corresponding to \(\mathcal{P}\) is a subset of the clusters of \(S_{\mathcal{Q}}\) and the cost of \(S_{\mathcal{Q}}\) is at most \(\text{cost}(S - S_0 \cup \Lambda)\) (since \(S_{\mathcal{Q}}\supseteq S- S_0 \cup \Lambda\)), which has cost at most \(O(\text{opt})\) by Lemma [lemma:S0properties]. This implies that \(|\mathcal{C}| = O(\log(n)/\varepsilon^5)\), so the total number of subsets is \(n^{1/\varepsilon^{O(1)}}\). The algorithm proceeds by trying all possible subsets in the output, and we analyze the algorithm when it takes the correct guess of \(\mathcal{R}_0\).

4.6.0.5 Definition of the submodular function \(f\).

We first define another function \(g\) on the same domain as \(f\), i.e., on all subsets \(X\) of \(F_\mathcal{B}\). We will then define \(f\) by \(f(X) = g(\emptyset) - g(X)\). Let the closed cost of a cluster \(C_c\) be defined as \[\text{closedcost}_c(X) := \begin{cases} \sum_{p\in C_c} d(p, \{c\} \cup X \cup \Lambda) & if C_c is hit by X, \\ \min_{c'\in X \cup \Lambda} \sum_{p\in C^{\text{core}}_c} d(p, c') + \sum_{p\in C_c - C^{\text{core}}_c} d(p, \{c\} \cup X \cup \Lambda) & otherwise. \end{cases}\] Further, let \(\mathcal{P}_1\) be the potential centers for \(\mathcal{R}_1\): it contains each center \(c\in \mathcal{P}- \mathcal{R}_0\) so that \(c\) is concentrated, i.e., \(|C^{\text{core}}_c| \geq (1-\varepsilon) |C_c|\). We remark that the algorithm can calculate this set \(\mathcal{P}_1\) as it only depends on \(\mathcal{P}\), the guessed set \(\mathcal{R}_0\), the value \(\text{cost}(S)\), and the clusters \(C_c\) defined by \(\widetilde{\mu}\). Moreover, by definition, we have \(\mathcal{R}_1 \subseteq \mathcal{P}_1\). For a subset \(X \subseteq F_\mathcal{B}\), we then then define \(g(X)\) to be the minimum value of \[\begin{gather} \sum_{c \not \in \mathcal{R}_0 \cup \mathcal{R}'_1}\sum_{p\in C_c} d\left(p, \{c\} \cup X \cup \Lambda\right) + \sum_{c\in \mathcal{R}_0} \sum_{p\in C_c} d(p, X \cup \Lambda) + \sum_{c\in \mathcal{R}'_1} \text{closedcost}_c(X) \end{gather}\] over all subsets \(\mathcal{R}'_1 \subseteq \mathcal{P}_1\) with \(|\mathcal{R}_1'| = |\mathcal{R}_1| = |\mathcal{R}| - |\mathcal{R}_0|\). In words, over the best \(\mathcal{R}_1'\), \(g(X)\) is the cost of the solution obtained by removing the centers \(\mathcal{R}_0 \cup \mathcal{R}_1'\) and assigning clients as follows:

• If \(p\in C_c\) for a remaining center \(c \not\in \mathcal{R}_0 \cup \mathcal{R}_1'\) or \(p \not \in C^{\text{core}}_c\) with \(c\in \mathcal{R}'_1\), \(p\) is assigned to its closest center in \(\{c\} \cup X \cup \Lambda\).

• If \(p \in C_c\) for a removed center \(c\in \mathcal{R}_0\), \(p\) is assigned to its closest center in \(X \cup \Lambda\).

• If \(p \in C^{\text{core}}_c\) for a removed center \(c\in \mathcal{R}'_1\), \(p\) is assigned to its closest center in \(\{c\} \cup X \cup \Lambda\) if \(X\) hits \(C_c\), and otherwise all clients in \(C^{\text{core}}_c\) are assigned to the same center \(c'\in X \cup \Lambda\) that minimizes the cost.

We remark that this assignment is infeasible in the sense that it may assign clients to removed centers in \(\mathcal{R}'_1\). Nevertheless, we relate the values of \(g(\emptyset)\) and \(g(\hat{\text{OPT}})\) to \(\text{cost}(M'_D, \mu'_D)\) and \(\text{cost}(M'_O, \mu'_O)\), respectively; and, we show that given an \(X \subseteq F_\mathcal{B}\) that is independent in \(M_\mathcal{B}\), i.e., \(X\in \mathcal{I}\), we can in polynomial-time output \(k\) centers whose cost is at most \((1+2\varepsilon)g(X) + 15\varepsilon\text{opt}\). Finally, the definition of \(g\) allows us to prove that \(f\) (defined by \(f(X) = g(\emptyset) - g(X)\)) is a monotone submodular function.

We give the proof of the lemma in the next subsection. We explain here how it implies Lemma 21.

4.6.1 Proof of Lemma 22↩︎

4.6.1.1 Proof of Property 1.

Given \(X \subseteq F_{\mathcal{B}}\), we argue that we can evaluate \(g(X)\) in polynomial time. For a center \(c \in \mathcal{P}_1\), define \[\text{cost-inc}_c(X) = \text{closedcost}_c(X) - \sum_{p\in C_c} d(p, \{c\} \cup X \cup \Lambda)\,.\] In other words, using that \(d(p,c ) \leq d(p, X)\) for \(p\in C^{\text{core}}_c\) if \(C_c\) is not hit by \(X\), \[\begin{align} \text{cost-inc}_c(X) = \begin{cases} 0 & if C_c is hit by X, \\ \min_{c'\in X \cup \Lambda} \sum_{p\in C^{\text{core}}_c} (d(p, c') - d(p,\{c\} \cup \Lambda)) & otherwise. \end{cases} \label{eq:increase} \end{align}\tag{22}\] We remark that \(\text{cost-inc}_c(X)\geq 0\) by definition. Let \(D_0\) denote the clients belonging to clusters \(C_c\) with \(c\in \mathcal{R}_0\). With this notation, \(g(X)\) is the minimum value \[\begin{align} \sum_{p\in D- D_0} d(p, \{\widetilde{\mu}(p)\} \cup X \cup \Lambda) + \sum_{p\in D_0} d(p, X \cup \Lambda) + \sum_{c \in \mathcal{R}'_1} \text{cost-inc}_c(X) \label{eq:nicedefofg} \end{align}\tag{23}\] over all subsets \(\mathcal{R}'_1 \subseteq \mathcal{P}_1\) with \(|\mathcal{R}'_1| = |\mathcal{R}_1|\). We further have that the value of \(\text{cost-inc}_c(X)\) for \(c\in \mathcal{R}'_1\) is independent of other centers in \(\mathcal{R}'_1\). We can thus obtain the best choice of \(\mathcal{R}'_1\) by evaluating \(\text{cost-inc}_c(X)\) for every \(c\in \mathcal{P}_1\) and choose the \(|\mathcal{R}_1|\) ones of smallest value. Notice that the algorithm knows \(|\mathcal{R}_1|\) since it equals \(|S_0| - |\mathcal{Q}| - |\widetilde{\mathcal{U}}| - |\mathcal{R}_0| =|\mathcal{B}| - |\mathcal{Q}| - |\widetilde{\mathcal{U}}| - |\mathcal{R}_0|\). After we have obtained \(\mathcal{R}'_1\) in polynomial time, we can evaluate \(g(X)\) in polynomial time by simply calculating the sum.

4.6.1.2 Proof of Property 2.

In the proof of this property it will be convenient to use definition 23 of \(g\). We start by verifying that \(f\) is monotone. I.e., that \(f(Y) \geq f(X)\) when \(X \subseteq Y\), which is equivalent to verifying that \(g(Y) \leq g(X)\). Let \(g(X)\) equal \[\sum_{ p\in D- D_0} d(p, \{\widetilde{\mu}(p)\} \cup X \cup \Lambda) + \sum_{p\in D_0} d(p, X \cup \Lambda)+ \sum_{c \in \mathcal{R}'_1} \text{cost-inc}_c(X)\] for some set \(\mathcal{R}'_1\). Then \(g(Y)\) is at most \[\sum_{p\in D- D_0} d(p, \{\widetilde{\mu}(p)\} \cup Y \cup \Lambda)+ \sum_{p\in D_0} d(p, Y \cup \Lambda) + \sum_{c \in \mathcal{R}'_1} \text{cost-inc}_c(Y)\] As trivially \(d(p, \{\widetilde{\mu}(p)\} \cup Y \cup \Lambda) \leq d(p, \{\widetilde{\mu}(p)\}\cup X \cup \Lambda)\), \(d(p, Y \cup \Lambda) \leq d(p, X \cup \Lambda)\) and \(\text{cost-inc}_c(Y) \leq \text{cost-inc}_c(X)\) (see 22 ), we have \(g(Y) \leq g(X)\) as required. Moreover, as \(f(\emptyset) = 0\) by definition, non-negativity follows.

We proceed to verify that \(f\) is submodular, i.e., that for every \(X \subseteq Y \subseteq F_B\) and \(c_0 \in F_B - Y\), \(f(X \cup \{c_0\}) - f(X) \geq f(Y \cup \{c_0\}) - f(Y)\), or equivalently \[\begin{align} g(X \cup \{c_0\}) - g(X) \leq g(Y \cup \{c_0\}) - g(Y)\,. \label{eq:submodularineq} \end{align}\tag{24}\] Let \(\mathcal{R}_1^X, \mathcal{R}_1^Y\), and \({\mathcal{R}}_1^{Y+c_0}\) be subsets of \(\mathcal{P}_1\) of cardinality \(|\mathcal{R}_1|\) such that \[\begin{align} g(X) &= \sum_{p\in D- D_0} d(p, \{\widetilde{\mu}(p)\} \cup X \cup \Lambda) + \sum_{p\in D_0} d(p, X \cup \Lambda) + \sum_{c \in \mathcal{R}^X_1} \text{cost-inc}_c(X)\\ g(Y) &= \sum_{p\in D- D_0} d(p, \{\widetilde{\mu}(p)\} \cup Y \cup \Lambda)+ \sum_{p\in D_0} d(p, Y \cup \Lambda) + \sum_{c \in \mathcal{R}^Y_1} \text{cost-inc}_c(Y)\\ g(Y \cup \{c_0\}) & = \sum_{p\in D- D_0} d(p, \{\widetilde{\mu}(p)\} \cup (Y \cup \{c_0\}) \cup \Lambda)+ \sum_{p\in D_0} d(p, (Y \cup \{c_0\}) \cup \Lambda) + \sum_{c \in {\mathcal{R}}^{Y+c_0}_1} \text{cost-inc}_c(Y\cup \{c_0\}) \end{align}\] We shall define \({\mathcal{R}}^{X+c_0}_1\) to be a subset of \(\mathcal{P}_1\) of cardinality \(|\mathcal{R}_1|\) so that the upper bound \[\begin{align} g(X\cup \{c_0\}) \leq \sum_{p\in D- D_0} d(p, \{\widetilde{\mu}(p)\} \cup (X\cup \{c_0\}) \cup \Lambda)+ \sum_{p\in D_0} d(p, (X \cup \{c_0\}) \cup \Lambda) + \sum_{c \in {\mathcal{R}}^{X+c_0}_1} \text{cost-inc}_c(X \cup \{c_0\}) \end{align}\] allows us to verify Inequality 24 . First notice that no matter the definition of \({\mathcal{R}}^{X+c_0}_1\), we have that \[\begin{align} \sum_{p\in D- D_0} (d(p, \{\widetilde{\mu}(p)\} \cup (X\cup \{c_0\}) \cup \Lambda) - d(p, \{\widetilde{\mu}(p)\} \cup X \cup \Lambda) ) +\sum_{p\in D_0} (d(p, (X\cup \{c_0\}) \cup \Lambda) - d(p, X \cup \Lambda) ) \label{eq:boringsubmodular1} \end{align}\tag{25}\] is upper bounded by \[\begin{align} \sum_{p\in D- D_0} (d(p, \{\widetilde{\mu}(p)\} \cup (Y \cup \{c_0\}) \cup \Lambda) - d(p, \{\widetilde{\mu}(p)\} \cup Y \cup \Lambda)) + \sum_{p\in D_0}(d(p, (Y \cup \{c_0\}) \cup \Lambda) - d(p, Y \cup \Lambda))\,. \label{eq:boringsubmodular2} \end{align}\tag{26}\] Indeed, if we let \(D' \subseteq D- D_0\) be the subset of clients for which \(d(p, c_0) < d(p, \{\widetilde{\mu}(p)\} \cup Y \cup \Lambda)\) and \(D'_0 \subseteq D_0\) be the subset of clients for which \(d(p, c_0) < d(p, Y \cup \Lambda)\), then 26 equals \[\sum_{p\in D'} (d(p, c_0) - d(p, \{\widetilde{\mu}(p)\} \cup Y \cup \Lambda))+ \sum_{p\in D'_0} (d(p, c_0) - d(p, Y \cup \Lambda))\] and we have \[\eqref{eq:boringsubmodular1} \leq \sum_{p\in D'} (d(p, c_0) - d(p, \{\widetilde{\mu}(p)\} \cup X \cup \Lambda)) + \sum_{p\in D'_0} (d(p, c_0) - d(p, X \cup \Lambda))\,.\] It follows that 25 is at most 26 because \[\sum_{p\in D'} ( d(p, \{\widetilde{\mu}(p)\} \cup Y \cup \Lambda) - d(p, \{\widetilde{\mu}(p)\} \cup X \cup \Lambda)) + \sum_{p\in D'_0} ( d(p, Y \cup \Lambda) - d(p, X \cup \Lambda)) \leq 0\,.\] To prove that \(f\) is submodular, it is thus sufficient to define \({\mathcal{R}}^{X+c_0}_1\) so that \[\begin{align} \sum_{c\in {\mathcal{R}}^{X+c_0}_1} \text{cost-inc}_c(X \cup \{c_0\}) - \sum_{c\in {\mathcal{R}}^X_1} \text{cost-inc}_c(X)\leq \sum_{c\in {\mathcal{R}}^{Y+c_0}_1} \text{cost-inc}_c(Y \cup \{c_0\}) - \sum_{c\in {\mathcal{R}}^Y_1} \text{cost-inc}_c(Y)\,. \label{eq:mainsubmodular} \end{align}\tag{27}\] To this end, let \(\Delta_{\text{new}}\) contain the centers in \({\mathcal{R}}^{Y+c_0}_1 - {\mathcal{R}}^Y_1\) and those centers \(c \in {\mathcal{R}}^{Y+c_0}_1 \cap \mathcal{R}^Y_1\) with \(\text{cost-inc}_c(Y \cup \{c_0\}) < \text{cost-inc}_c(Y)\). Notice that we may assume that, for each \(c\in \Delta_{\text{new}}\), \[\text{cost-inc}_c(Y \cup \{c_0\})= \text{cost-inc}_c(\{c_0\}) = \begin{cases} 0 & if C_c is hit by c_0, \\ \sum_{p\in C^{\text{core}}_c} (d(p, c_0) - d(p,\{c\} \cup \Lambda)) & otherwise. \end{cases}\] because the addition of \(c_0\) caused a decrease in \(\text{cost-inc}(\cdot)\) for these clusters. Further, let \(\Delta_{\text{old}}^Y\) contain \(\Delta_{\text{new}} \cap \mathcal{R}^{Y}_1\) and the centers \(\mathcal{R}^{Y}_1 - \mathcal{R}^{Y+c_0}_1\). So \(\mathcal{R}^{Y+c_0}_1 = (\mathcal{R}^{Y}_1 - \Delta_{\text{old}}^Y) \cup \Delta_{\text{new}}\) and \(|\Delta_{\text{new}}| = |\Delta_{\text{old}}^Y|\). We now define \(\mathcal{R}^{X+c_0}_1 = (\mathcal{R}^{X}_1 - \Delta_{\text{old}}^X) \cup \Delta_{\text{new}}\) where \(\Delta^X_{\text{old}}\) is obtained as follows:

• Initialize \(\Delta_{\text{old}}^X =\mathcal{R}^X_1\cap \Delta_{\text{new}}\).

• While \(|\Delta_{\text{old}}^X|< |\Delta_{\text{new}}|\), add a center according to the following priorities:

  • If there is a center \(c\in \mathcal{R}^X_1 - \Delta_{\text{old}}^X\) so that \(c\not \in \mathcal{R}^{Y}_1\), add \(c\) to \(\Delta_{\text{old}}^X\).

  • Else add a center \(c\in \mathcal{R}^X_1- \Delta_{\text{old}}^X\) with \(c \in \Delta_{\text{old}}^Y\).

We claim that the above is well-defined, i.e., that if \(|\Delta_{\text{old}}^X|< |\Delta_{\text{new}}|\) and there is no center \(c\in \mathcal{R}^X_1 - \Delta_{\text{old}}^X\) so that \(c\not \in \mathcal{R}^{Y}_1\), then there must be a center \(c\in \mathcal{R}^X_1- \Delta_{\text{old}}^X\) with \(c \in \Delta_{\text{old}}^Y\). This is because \(|\Delta_{\text{old}}^X| < |\Delta_{\text{new}}| = |\Delta_{\text{old}}^Y|\) and all remaining centers \(\mathcal{R}_1^X - \Delta_{\text{old}}^X\) are in \(\mathcal{R}^Y_1\) in this case, so at least one of them must be in \(\Delta_{\text{old}}^Y\) (recall that \(|\mathcal{R}_1^X| = |\mathcal{R}_1^Y|\)).

With this notation we have \[\begin{align} \notag \sum_{c\in {\mathcal{R}}^{Y+c_0}_1} \text{cost-inc}_c(Y \cup \{c_0\}) - \sum_{c\in {\mathcal{R}}^Y_1} \text{cost-inc}_c(Y ) & = \sum_{c\in \Delta_{\text{new}}} \text{cost-inc}_c(Y \cup \{c_0\}) - \sum_{c\in \Delta_{\text{old}}^Y}\text{cost-inc}_{c}(Y) \\ &= \sum_{c\in \Delta_{\text{new}}} \text{cost-inc}_c(\{c_0\}) - \sum_{c\in \Delta_{\text{old}}^Y}\text{cost-inc}_{c}(Y)\,. \label{eq:firstsubmodular} \end{align}\tag{28}\] Similarly, \[\begin{align} \sum_{c\in {\mathcal{R}}^{X+c_0}_1} \text{cost-inc}_c(X \cup \{c_0\}) - \sum_{c\in {\mathcal{R}}^X_1} \text{cost-inc}_c(X ) & \leq \sum_{c\in \Delta_{\text{new}}} \text{cost-inc}_c(X \cup \{c_0\}) - \sum_{c\in \Delta_{\text{old}}^X} \text{cost-inc}_{c}(X) \notag\\ & = \sum_{c\in \Delta_{\text{new}}} \text{cost-inc}_c(\{c_0\}) - \sum_{c\in \Delta_{\text{old}}^X} \text{cost-inc}_{c}(X)\,, \label{eq:secondsubmoular} \end{align}\tag{29}\] where we used that \(\text{cost-inc}_c(X \cup \{c_0\}) \leq \text{cost-inc}_c(X)\) for any center \(c\).

To analyze this, let \(\pi\) be a bijection from \(\Delta_{\text{old}}^Y\) to \(\Delta_{\text{old}}^X\) so that \(\pi(c) =c\) for all \(c\in \Delta_{\text{old}}^Y \cap \Delta_{\text{old}}^X\).

By the above claim, \[\begin{align} \sum_{c\in \Delta_{\text{old}}^Y}\text{cost-inc}_{c}(Y) - \sum_{c\in \Delta_{\text{old}}^X} \text{cost-inc}_{c}(X) = \sum_{c\in \Delta_{\text{old}}^Y}(\text{cost-inc}_{c}(Y) - \text{cost-inc}_{\pi(c)}(X)) \leq 0 \end{align}\] and thus by the above arguments (see 28 and 29 ) \[\sum_{c\in {\mathcal{R}}^{X+c_0}_1} \text{cost-inc}_c(X \cup \{c_0\}) - \sum_{c\in {\mathcal{R}}^X_1} \text{cost-inc}_c(X)\leq \sum_{c\in {\mathcal{R}}^{Y+c_0}_1} \text{cost-inc}_c(Y \cup \{c_0\}) - \sum_{c\in {\mathcal{R}}^Y_1} \text{cost-inc}_c(Y)\,.\] We have thus verified 27 , which concludes the proof that \(f\) is submodular.

4.6.1.3 Proof of Property 3.

For every \(c\in \mathcal{R}_1\), we have \[\begin{align} \text{closedcost}_c(\emptyset) & =\min_{c'\in \Lambda}\sum_{p\in C^{core}_c}d(p,c')+\sum_{p\in C_c-C^{core}_c}d(p,\{c\}\cup \Lambda)\\ & \leq \min_{c'\in \Lambda}(\sum_{p\in C^{core}_c}d(p,c')+\sum_{p\in C_c-C^{core}_c}d(p,c'))=\min_{c'\in \Lambda}\sum_{p\in C_c}d(p,c'). \end{align}\] Thus \[\begin{align} g(\emptyset) &\leq \sum_{c \not \in \mathcal{R}}\sum_{p\in C_c} d\left(p, \{c\} \cup \Lambda\right) + \sum_{p\in D_0} d(p, \Lambda) + \sum_{c\in \mathcal{R}_1} \text{closedcost}_c(\emptyset) \\ &\leq \sum_{c \not \in \mathcal{R}}\sum_{p\in C_c} d\left(p, \{c\} \cup \Lambda\right)+ \sum_{p\in D_0} d(p, \Lambda) + \sum_{c\in \mathcal{R}_1} \min_{c'\in \Lambda} \sum_{p\in C_c} d(p, c') \\ & \leq \sum_{c \not \in \mathcal{R}}\sum_{p\in C_c} d\left(p, \{c\} \cup \Lambda\right) + \sum_{c\in \mathcal{R}} \min_{c'\in \Lambda} \sum_{p\in C_c} d(p, c') \overset{\eqref{eq:MprimeDbound}}{\leq}\text{cost}(M'_D, \mu'_D)\,. \end{align}\]

4.6.1.4 Proof of Property 4.

Consider any \(c\in \mathcal{R}_1\). If \(C_c\) is hit by \(\hat{\text{OPT}}\) one has \[\begin{align} \text{closedcost}_c(\hat{\text{OPT}}) & = \sum_{p\in C_c}d(p,\{c\}\cup \hat{\text{OPT}}\cup \Lambda)\leq \min_{c'\in \hat{\text{OPT}}}\sum_{p\in C_c}d(p,c'). \end{align}\] Otherwise \[\begin{align} \text{closedcost}_c(\hat{\text{OPT}}) & =\min_{c'\in \hat{\text{OPT}}\cup \Lambda}\sum_{p\in C^{core}_c}d(p,c')+\sum_{p\in C_c-C^{core}_c}d(p,\{c\}\cup \hat{\text{OPT}}\cup \Lambda)\\ & \leq \min_{c'\in \hat{\text{OPT}}}(\sum_{p\in C^{core}_c}d(p,c')+\sum_{p\in C_c-C^{core}_c}d(p,c'))=\min_{c'\in \hat{\text{OPT}}}\sum_{p\in C_c}d(p,c'). \end{align}\] Hence in both cases \(\text{closedcost}_c(\hat{\text{OPT}})\leq \min_{c'\in \hat{\text{OPT}}}\sum_{p\in C_c}d(p,c')\). Thus \[\begin{align} g(\hat{\text{OPT}}) &\leq \sum_{c \not \in \mathcal{R}}\sum_{p\in C_c} d\left(p, \{c\} \cup \hat{\text{OPT}}\cup \Lambda\right) + \sum_{p\in D_0}d(p, \hat{\text{OPT}}\cup \Lambda) + \sum_{c\in \mathcal{R}_1} \text{closedcost}_c(\hat{\text{OPT}}) \\ &\leq \sum_{c \not \in \mathcal{R}}\sum_{p\in C_c} d\left(p, \{c\} \cup \hat{\text{OPT}}\cup \Lambda\right)+ \sum_{p\in D_0} d(p, \hat{\text{OPT}}\cup \Lambda) + \sum_{c\in \mathcal{R}_1} \min_{c'\in \hat{\text{OPT}}} \sum_{p\in C_c} d(p, c') \\ & \leq \sum_{c \not \in \mathcal{R}}\sum_{p\in C_c} d\left(p, \{c\} \cup \hat{\text{OPT}}\cup \Lambda\right) + \sum_{c\in \mathcal{R}} \min_{c'\in \hat{\text{OPT}}} \sum_{p\in C_c} d(p, c')\overset{\eqref{eq:MprimeObound}}{\leq}\,\text{cost}(M'_O, \mu'_O). \end{align}\]

4.6.1.5 Proof of Property 5.

Let \(X \subseteq F_\mathcal{B}\) be independent in \(M_\mathcal{B}\), i.e., \(X\in \mathcal{I}\). We give a polynomial-time algorithm that outputs \(k\) centers \(S^*\) whose cost is at most \((1+2\varepsilon)g(X) +15\varepsilon\text{opt}\). Let \(\mathcal{R}'_1\) be a subset of \(\mathcal{P}_1\) of cardinality \(|\mathcal{R}_1|\) so that \[\begin{gather} g(X) = \sum_{c \not \in \mathcal{R}_0 \cup \mathcal{R}'_1}\sum_{p\in C_c} d\left(p, \{c\} \cup X \cup \Lambda\right)+ \sum_{p \in D_0} d(p, X \cup \Lambda) + \sum_{c\in \mathcal{R}'_1} \text{closedcost}_c(X) \end{gather}\] By the arguments in the proof of the first property, we can calculate \(\mathcal{R}'_1\) in polynomial time. Now we obtain \(S^*\) from \(S_{\mathcal{Q}\cup \widetilde{\mathcal{U}}}\) as follows:

• Initialize \(S^* = S_{\mathcal{Q}\cup \widetilde{\mathcal{U}}} = S \cup \Lambda- \mathcal{Q}- \widetilde{\mathcal{U}}\).

• Remove centers \(\mathcal{R}_0\) and \(\mathcal{R}'_1\) from \(S^*\) to obtain a set of cardinality \(k\).

• Finally, for each ball in \(\mathcal{B}\), if \(X\) contains a center \(c\) in that ball, replace the associated dummy center by \(c\); otherwise, replace the dummy center with an arbitrary center in the ball.

By the definition of the dummy centers \(\Lambda\), the cost of \(S^*\) is at most \[\sum_{c \not \in \mathcal{R}_0 \cup \mathcal{R}'_1}\sum_{p\in C_c} d\left(p, \{c\} \cup X \cup \Lambda\right)+ \sum_{p \in D_0} d(p, X \cup \Lambda) + \sum_{c\in \mathcal{R}'_1} \sum_{p\in C_c} d(p, X \cup \Lambda)\,.\] To relate this to \(g(X)\) we need to compare \(\text{closedcost}_c(X)\) to \(\sum_{p\in C_c} d(p, X\cup \Lambda)\) for every \(c\in \mathcal{R}'_1\). Recall that \[\text{closedcost}_c(X) = \begin{cases} \sum_{p\in C_c} d(p, \{c\} \cup X \cup \Lambda) & if C_c is hit by X, \\ \min_{c'\in X \cup \Lambda} \sum_{p\in C^{\text{core}}_c} d(p, c') + \sum_{p\in C_c - C^{\text{core}}_c} d(p, \{c\} \cup X \cup \Lambda) & otherwise. \end{cases}\] Consider a cluster \(C_c\) with \(c\in \mathcal{R}'_1\) and partition \(C_c- C^{\text{core}}_c\) into sets \(A\) and \(B\) where \(A\) contain those clients \(p\) so that \(d(p, \{c\} \cup X \cup \Lambda) =d(p, c)\) and \(B\) contain the remaining clients \(p\) with \(d(p, \{c\} \cup X \cup \Lambda) = d(p, X \cup \Lambda)\). Suppose first that there is a client \(p_0 \in C^{\text{core}}_c\) so that \(d(p_0, X \cup \Lambda) < d(p_0, c)\), i.e., \(C_c\) is hit by \(X \cup \Lambda\). By the definition of \(C^{\text{core}}_c\), we have \(d(p_0, c) \leq \varepsilon\cdot \frac{\text{cost}(S)}{|\mathcal{R}| \cdot |C_c|}\leq 5 \varepsilon\cdot \frac{\text{opt}}{|\mathcal{R}| \cdot |C_c|}\) where we used that \(\text{cost}(S) \leq 5 \cdot \text{opt}\) by Lemma 9. So, by the triangle inequality, \[\begin{align} \sum_{p\in C_c} d(p, X \cup \Lambda)& \leq \sum_{p\in C_c - B} (d(p, c) + d(c, p_0) + d(p_0, X\cup \Lambda)) + \sum_{p\in B} d(p, X \cup \Lambda)\\ &\leq \sum_{p\in A} d(p, c) + \sum_{p\in B} d(p, X \cup \Lambda) + 15\varepsilon\cdot \frac{\text{opt}}{|\mathcal{R}|}\,, \end{align}\] where we used \(d(p_0, X\cup \Lambda) \leq d(c, p_0) \leq 5\varepsilon\cdot \frac{\text{opt}}{|\mathcal{R}| \cdot |C_c|}\) and \(d(p, c) \leq 5\varepsilon\cdot \frac{\text{opt}}{|\mathcal{R}| \cdot |C_c|}\) for any \(p\in C^{\text{core}}_c\) for the last inequality. Moreover, by definition of \(A\) and \(B\), we have \(d(p, c) = d(p, \{c\} \cup X \cup \Lambda)\) for any \(p\in A\) and \(d(p, X \cup \Lambda) = d(p, \{c\} \cup X \cup \Lambda)\) for any \(p\in B\). Hence, in this case, \[\begin{align} \sum_{p\in C_c} d(p, X \cup \Lambda) \leq \sum_{p\in C_c - C^{\text{core}}_c} d(p, \{c\} \cup X \cup Y) + 15 \varepsilon\cdot \frac{\text{opt}}{|\mathcal{R}|} \leq \text{closedcost}_c(X) + 15\varepsilon\cdot \frac{\text{opt}}{|\mathcal{R}|}\,. \end{align}\] Let us now consider a cluster \(C_c\) with \(c\in \mathcal{R}'_1\) that is not hit by \(X \cup \Lambda\), particularly not by \(X\). Then \[\begin{align} \text{closedcost}_c(X) &= \min_{c'\in X \cup \Lambda} \sum_{p\in C^{\text{core}}_c} d(p, c') + \sum_{p\in C_c - C^{\text{core}}_c} d(p, \{c\} \cup X \cup \Lambda) \\ & \geq \sum_{p\in C^{\text{core}}_c \cup B} d(p, X \cup \Lambda) + \sum_{q\in A} d(q, c) \end{align}\] We further have \[\begin{align} \sum_{p\in C_c} d(p, X \cup \Lambda) & = \sum_{p\in C^{\text{core}}_c \cup B} d(p, X \cup \Lambda) + \sum_{q\in A} d(q, X \cup \Lambda)\\ & \leq \sum_{p\in C^{\text{core}}_c \cup B} d(p, X \cup \Lambda) + \sum_{q\in A} \frac{1}{|C^{\text{core}}_c|}\sum_{p\in C^{\text{core}}_c} (d(q, c) + d(c, p) + d(p, X \cup \Lambda)) \end{align}\] by the triangle inequality. Now using that \(d(c,p) \leq 5 \varepsilon\cdot \frac{\text{opt}}{|\mathcal{R}| \cdot |C_c|}\) we obtain the upper bound \[\begin{align} \sum_{p\in C_c} d(p, X \cup \Lambda) & \leq \left(1 + \frac{|A|}{|C^{\text{core}}_c|}\right) \sum_{p\in C^{\text{core}}_c\cup B} d(p, X \cup \Lambda) + \sum_{q\in A} d(q,c) + 5\varepsilon\frac{\text{opt}}{|\mathcal{R}|} \\ &\leq \left(1 + \frac{\varepsilon}{(1-\varepsilon)}\right) \sum_{p\in C^{\text{core}}_c \cup B} d(p, X \cup \Lambda) + \sum_{q\in A} d(q,c) + 5\varepsilon\frac{\text{opt}}{|\mathcal{R}|} \\ & \leq (1+ 2\varepsilon) \text{closedcost}_c(X) + 5\varepsilon\frac{\text{opt}}{|\mathcal{R}|} \end{align}\] where for the second inequality we used that every cluster in \(\mathcal{R}_1' \subseteq \mathcal{P}_1\) is concentrated. In more detail \(|C^{\text{core}}_c|\geq (1-\varepsilon)|C_c|\), hence \(|A|\leq |C_c-C^{\text{core}}_c|\leq \varepsilon|C_c|\).

Hence, for any \(c\in \mathcal{R}_1'\) we proved that \(\sum_{p\in C_c} d(p,X \cup \Lambda) \leq (1+2\varepsilon) \text{closedcost}_c(X) + 15 \varepsilon\frac{\text{opt}}{|\mathcal{R}|}\). We thus get that the cost of \(S^*\) is at most

\[\begin{align} & \sum_{c \not \in \mathcal{R}_0 \cup \mathcal{R}'_1}\sum_{p\in C_c} d\left(p, \{c\} \cup X \cup \Lambda\right)+ \sum_{p \in D_0} d(p, X \cup \Lambda) + \sum_{c\in \mathcal{R}'_1}\left( (1+2\varepsilon) \text{closedcost}_c(X) + 15 \varepsilon\frac{\text{opt}}{|\mathcal{R}|}\right) \\ \leq & (1+2\varepsilon) \left(\sum_{c \not \in \mathcal{R}_0 \cup \mathcal{R}'_1}\sum_{p\in C_c} d\left(p, \{c\} \cup X \cup \Lambda\right)+ \sum_{p \in D_0} d(p, X \cup \Lambda) + \sum_{c\in \mathcal{R}'_1} \text{closedcost}_c(X) \right) + 15\varepsilon\text{opt} \end{align}\] which equals \((1+2\varepsilon) g(X) + 15\varepsilon\text{opt}\).

4.7 Putting Everything Together – Proof of Theorem [thm:mainadditivecenters]↩︎

We now turn to proving Theorem [thm:mainadditivecenters]. We first describe the algorithm we analyse.

4.7.0.1 A \((2{+\varepsilon})\)-Approximation for \(k\)-Median on an \(\varepsilon/\log n\)- Stable Instance \(k, D, F, d\).

\(S\leftarrow localSearch()\) \(W\leftarrow D\)-\(Sample(S,s^*)\) \(\mathcal{L}_{\texttt{ball}} \leftarrow ballGuess(S,W)\) Compute the dummy centers \(\Lambda\) according to \(\mathcal{B}\) \(\mathcal{L}_{\text{exp}}\leftarrow epxRem(S,\Lambda)\) \(\mathcal{L}_{cheap} \leftarrow \emptyset\) \(cheapRem(\emptyset,\emptyset,\emptyset,\emptyset,\emptyset)\) Approximately solve the submodular maximization problem subject to a partition matroid induced by \((S,W,\mathcal{B},\mathcal{Q},\widetilde{\mathcal{U}},\widetilde{\mu})\) and turn the obtained solution into a \(k\)-median solution \(S_{S,W,\mathcal{B},\mathcal{Q},\widetilde{\mathcal{U}},\widetilde{\mu}}\) return the cheapest solution of type \(S_{S,W,\mathcal{B},\mathcal{Q},\widetilde{\mathcal{U}},\widetilde{\mu}}\)

5 Analysis of Robust LogAdaptive↩︎

In this section, we prove Theorem 4, showing that a solution \(\mathcal{H}\) of \(\eta\)-valid sequences yields an almost \(2\)-LMP approximation. The proof is almost identical to that for LogAdaptive presented in Section 3.3. There are only two minor changes:

1. Definition 3 of \(\eta\)-openability allows a facility to be paid up to an \(n \eta\)-additive difference. This difference only appears in Lemma [lemma:approx95guarantee95robust] below, which is an analog of Lemma 6.

   lemmalemmaapproxguaranteerobust We have \(\sum_{j\in D} \alpha^*_j \geq (1-\delta) \sum_{j\in D} d(j, S^*) + \sum_{i\in S_{\mathsf{reg}}^*} (\hat{f} - n \eta)\).

2. Definiton 4 of a \(\eta\)-valid sequence allows \(h_t\) is \(\eta\)-openable with respect to a super set \(S' \supseteq S \cup \{ h_1, \dots, h_{t-1} \}\). This difference only appears in (the last part of) the proof of Lemma [lemma:dual95feasibility95robust], an analog of Lemma [lemma:dual95feasibility].

   lemmalemmadualfeasibilityrobust For a facility \(i\), \(\; \sum_{j \in D} [\alpha^*_j - 2d(i,j)]^+ \leq \hat{f}.\)

These two lemmas immediately imply Theorem 4. The other supporting claims and lemmas (Claim 10 and Lemma 23) remain identical.

In order to use mostly the same analysis, one syntactic difference between the setting of Section 3.3 and the current setting that we have to reconcile is that the former analyzes the outcome of LogAdaptive while the latter analyzes a solution \(\mathcal{H} = \{ H_1, \dots, H_L \}\) of \(\eta\)-valid sequences. To use the same terminology from Section 3.3, let us consider the execution of the solution \(\mathcal{H}\) where for \(p = 1, \dots, L\), we run the \(p\)-th phase according to the sequence \(H_p\); in Stage 1, each facility in the sequence becomes open one by one with the corresponding \((\tau_j)_j\) values, and in Stage 2 at the end of the phase, \(\theta \leftarrow \theta(1+\varepsilon^2)\).

Then an atomic step can still be defined in the same way as in LogAdaptive; it corresponds to opening a facility in Stage 1 (and updating \(\alpha, S, A\) accordingly) or increasing \(\alpha\) values in Stage 2 simultaneously (and updating \(S\) accordingly). By “at any point of the algorithm”, we mean any point in the algorithm’s execution that is not in the middle of an atomic step. The set of open facilities \(S\) can be partitioned to be the set of the open free facilities \(S_{\mathsf{free}}\) and the set of the open regular facilities \(S_{\mathsf{reg}}\).

Throughout the analysis, we let \(\alpha^*_j\) be the final \(\alpha\)-value of a client \(j\in D\), and we let \(S^*\) be the set of opened facilities. (Also let \(S_{\mathsf{free}}^*\) and \(S_{\mathsf{reg}}^*\) be the set of finally open free and regular facilities respectively.) We start by analyzing the approximation guarantee of the algorithm with respect to \(\alpha^*\), and we then prove that \(\alpha^*/2\) is a feasible solution to the dual.

5.1 Approximation Guarantee.↩︎

We prove Lemma [lemma:approx95guarantee95robust] restated below. The only difference from Lemma 6 is that opening a facility only requires \(\hat{f} - n \eta\) instead of \(\hat{f}\).

5.2 Dual Feasibility↩︎

We prove Lemma [lemma:dual95feasibility95robust] for dual feasibility. The following claim is identical to Claim [claim:dual-feasible-induction] without any modification.

As usual, fix an arbitrary regular facility \(i \in F\). The setup in this paragraph is also identical to Section 3.3. Let \(D^* = \{ j \in D : \alpha^*_j > 2d(i, j) \}\) be those clients that contribute to the left-hand-side. Further, order the clients in \(D^*\) according to \(\alpha^*\) values by the time they are removed from \(A\) (in the algorithm) and break ties according to \(\alpha^*\) values (in increasing order). We will use \(j, k\) to denote clients in \(D^*\), and let us slightly abuse notation and use \(j \leq k\) with respect to this ordering. In other words, we have \(j\leq k\) if \(j\) was removed from \(A\) in an atomic step before \(k\) was removed, \(j\) and \(k\) was removed during the same atomic step and \(\alpha^*_j \leq \alpha^*_k\). We also use the terminology that a facility \(i\) freezes \(i_0\) if \(i\) becomes open when \(i_0\) is not, and \(d(i, i_0) \leq (1+3\varepsilon)\theta/2\). (Of course, \(i\) freezes itself when it is open.)

The following lemma and the proof are also identical to Lemma 7.

Equipped with the above lemma, we are ready to complete the proof of dual feasibility.

Acknowledgment↩︎

The authors are grateful to Rares-Darius Buhai for valuable feedback on the writing. In particular, for identifying the need to explicitly write Lemma 8.

References↩︎

---

1. Google Research, France.↩︎

2. IDSIA, USI-SUPSI, Switzerland. Supported in part by the SNF Grants 200021-200731 and 200021-236706.↩︎

3. University of Michigan, Ann Arbor, MI, USA. Supported in part by NSF 2236669.↩︎

4. Aarhus University, Denmark. Supported in part by the Independent Research Fund Denmark (DFF) under grant No 1051-00106B and a Google Research Award.↩︎

5. EPFL, Switzerland. Supported in part by the Swiss State Secretariat for Education, Research and Innovation (SERI) under contract number MB22.00054.↩︎

6. Sometimes in the literature one assumes \(F=D\) or \(D\subseteq F\). We consider the more general case and make no such assumption.↩︎

7. Solutions opening slightly more than \(k\) centers are sometimes called pseudo-solutions in the literature.↩︎

8. Throughout this overview, we assume no solution opens exactly \(k\) centers, because we are done if this happens.↩︎

9. Here and in the following procedures, the input instance is considered as passed implicitly.↩︎

10. We remark that we could select \(\zeta\) to be arbitrarily small and get a better guarantee in the statement of Lemma 21. We have chosen this value to simplify the calculations as improving the guarantee of Lemma 21 does not improve the overall result.↩︎