Proof. \(\Box\) F: I changed the proof here to not require strong stability. We refrain from recreating the proof in entirety. Instead we refer interested readers to the proof of Lemma 2 in [1].\(\Box\) K: I would say we should omit this since we are invoking the needed lemmas from [1] anyway.. We first perturb the distances as follows:

\[\label{eq:perturbed-dist} \delta^{\prime}(i, j)=\left\{\begin{tabular}{l l} \left(1+\varepsilon^{\prime}\right) \cdot \delta(i, j) & ; if i \neq \sigma(j, S) \\ \delta(i, j) & ; otherwise \end{tabular}\right.\tag{1}\]

We present a slightly modified version of Lemma 2 in [1]:

In this lemma, we let \(S\) be the nearly-good solution of Algorithm 1. Let \(O\) be any optimum solution of \(\mathcal{I}^\prime\). Using stability condition \(O\) should also be an optimum solution for \(\mathcal{I}\). We observe that \[\operatorname{cost}'(S) = \operatorname{cost}(S) \leq \operatorname{cost}'(O),\] where \(\operatorname{cost}'\) indicates the cost of a solution under \(\delta'\). Therefore \(S\) is a optimum solution for \(\mathcal{I}^\prime\). Using the stability condition one more time, we conclude that \(S\) must also be an optimum solution of \(\mathcal{I}\) and this \(S \in \mathcal{O}= \{O_1, \ldots, O_\ell\}\). Assume that Algorithm 1 encounters \(S\) in iteration \(t \leq \left\lfloor 2k\cdot \ln (\Delta n)\right\rfloor\). Since \(S\) has the lowest possible cost for the instance \(\mathcal{I}\), the local search must terminate at iteration \(t\) and return \(S\). ◻

Proof. By Theorem 4, it suffices to show that \(\mathcal{I}(S, n)\) is also \((\alpha, \beta)\)-stable. Consider any \(\delta \leq \delta^\prime \leq \alpha \cdot \delta\) and \(p \leq p^\prime \leq \alpha \cdot p\). Define \(\operatorname{cost}_{\mathrm{pen}}^\prime(S) = \sum_{j \in X^{grid}} \min_{i \in S} \left\{\min \left\{\delta^\prime(i, j), p^\prime(j)\right\}\right\}\) for every \(S \subseteq C^{grid}\). First we prove that every optimal solution \(O\) of the \(k^2\)-Median, \((X^{grid}, C^{grid}, \delta^{\prime}, p')\) cannot have two centres in a \(C_{i, j}\) for \(1 \leq i, j, \leq k\). For the sake of contradiction assume that there exist \(1 \leq i, j, \leq k\) such that there exist \(\vec{a}, \vec{b} \in C_{i, j} \cap O\). Due to the pigeonhole principle, we have \(i'\) and \(j'\), \(1 \leq i^{\prime}, j^{\prime}, \leq k\) such that \(C_{i^{\prime}, j^{\prime}} \cap O = \varnothing\). Let \(O^{\prime} = (O \backslash \{\vec{a}\}) \cup \{\vec{c}\}\) for any \(\vec{c} \in C_{i^{\prime}, j^{\prime}}\). We then argue that \(\operatorname{cost}_{\mathrm{pen}}^\prime(O^{\prime})\) is smaller than \(\operatorname{cost}_{\mathrm{pen}}^\prime(O)\), which is a contradiction. Let \(D\) be the set of all points in a circle with centre \(\vec{c}\) and radius \(\frac{1}{\alpha}\). Every \(\vec{x} \in D\) satisfies \(\delta^{\prime}(\vec{x}, \vec{c}) \leq \alpha \delta(\vec{x}, \vec{c}) \leq 1\). Also, since every other point \(\vec{d} \neq \vec{a}\), \(\vec{d} \in O^\prime\), has the property \(\delta(\vec{c}, \vec{d}) \geq 2 - (n - 1) \varepsilon\), we have \(\delta^\prime(\vec{d}, \vec{x}) \geq \delta(\vec{d}, \vec{x}) \geq 2 - \alpha - (n - 1) \varepsilon\) which is greater than 1 for large enough \(n\) (for \(n\) polynomial in \(\frac{1}{\alpha - 1}\)). Also, \(p'(\vec{x}) \geq p^{grid}(\vec{x}) = 1\) which is smaller than \(\delta^{\prime}(\vec{x}, \vec{c})\). Therefore, every point in \(D\) will be assigned to \(\vec{c}\). Thus, adding \(\vec{c}\) to \(O\) will decrease \(\operatorname{cost}_{\mathrm{pen}}^\prime(O)\) at least by \[\label{eq:k-median-penalty-alpha-beta-stable-hardness-1} \begin{align} \iint_{D} (1 - \delta^{\prime}(\vec{x}, \vec{c})) d\mu &\geq \iint_{D} \left(1 - \alpha \delta(\vec{x}, \vec{c})\right) d\mu \\ & \stackrel{(i)}{\geq} \frac{1}{\varepsilon^2} \left( \pi \left(\frac{1}{\alpha} - \varepsilon\right)^2 - \pi \alpha \left( \frac{2}{3} \cdot \left(\frac{1}{\alpha} + \varepsilon\right)^3 + \varepsilon \left(\frac{1}{\alpha} + \varepsilon\right)^2 \right) \right),\\ \end{align}\tag{6}\] where (i) is due to Lemma 5. Next, note that in order for any \(\vec{x} \in A\) to be assigned to \(\vec{a}\), \(\delta^{\prime}(\vec{x}, \vec{a})\) should be less than \(p'(\vec{x}) \leq \alpha\). Subsequently, all such \(\vec{x}\) should have \(\delta(\vec{x}, \vec{a}) \leq \alpha\), i.e., they should belong to a circle with radius \(\alpha\) and centre \(\vec{a}\), which we denote by \(D^{\prime}\). Next, notice that \[\label{eq:k-median-penalty-alpha-beta-stable-hardness-2} \begin{align} \delta^{\prime}(\vec{x}, \vec{b}) & \leq \alpha \delta(\vec{x}, \vec{b}) \leq \alpha (\delta(\vec{x}, \vec{a}) + \varepsilon (n - 1)) = \delta(\vec{x}, \vec{a}) + \left(\alpha - 1\right) \delta(\vec{x}, \vec{a}) + \alpha \varepsilon (n - 1) \\ & \leq \delta^{\prime}(\vec{x}, \vec{a}) + \left(\alpha - 1\right) \delta(\vec{x}, \vec{a}) + \alpha \varepsilon (n - 1). \end{align}\tag{7}\] Thus, removing \(\vec{a}\) from \(O\) will decrease \(\operatorname{cost}_{\mathrm{pen}}^\prime(O)\) by at most \[\label{eq:k-median-penalty-alpha-beta-stable-hardness-3} \begin{align} \iint_{D^{\prime}} &\max \left[ \delta^{\prime}(\vec{x}, b) - \delta^{\prime}(\vec{x}, \vec{a}), 0\right] \stackrel{(i)}{\leq} \iint_{D^{\prime}} \left(\alpha - 1\right) \delta(\vec{x}, a) + \alpha \varepsilon (n-1) d\mu \\ &\leq \frac{1}{\varepsilon^2} \left( \left(\alpha - 1\right) \frac{2\pi}{3} (\alpha + \varepsilon)^3 + (\alpha - 1)\varepsilon \pi (\alpha + \varepsilon)^2 + \alpha \varepsilon (n-1) \pi ( \alpha + \varepsilon)^2 \right). \\ \end{align}\tag{8}\] Next we combine 6 and 8 to derive \(\operatorname{cost}_{\mathrm{pen}}^\prime(O^{\prime}) - \operatorname{cost}_{\mathrm{pen}}^\prime(O) \leq \frac{1}{\varepsilon^2} \left((\alpha^4 - \alpha^3) \frac{2 \pi}{3} - \frac{ \pi}{3 \alpha^2} + O(n \varepsilon) \right)\), which is less than zero for \(1 < \alpha < 1.2\) for large enough \(n\). This contradicts \(O\) minimizing \(\operatorname{cost}_{\mathrm{pen}}^\prime\).

Consider \(O^\prime \in \mathcal{F}_{k^2}\) to be any optimum solution of \(\mathcal{I}(S, n)\). So far, we have established that \(O\) contains \(k^2\) centres, one in each \(C_{i, j}\) for \(1 \leq i, j, \leq k\). This indicates that \(O^\prime\) has the same property. Let \(f:O^\prime \rightarrow O\) be the unique function such that for any \(o \in O^\prime\), if \(o \in C_{i, j}\) for some \(1 \leq i, j, \leq k\), then also \(f(o) \in C_{i, j}\). Therefore, \(\sum\nolimits_{o \in O_p} \delta(o, f_p(o)) \leq k^2 \varepsilon (n-1) \leq \beta\). This implies that \(\delta^{bij}_{\mathcal{I}}(O, O^\prime) \leq \beta\). Thus, \(\mathcal{I}(S, n)\) is \((\alpha, \beta)\)-stable. ◻

Proof. To establish this result, our analysis requires extra care compared to [1]. Friggstad et al.introduce the notion of being nearly-good with respect to a fixed reference point, namely the unique optimal solution. In our setting, we generalize stability to accommodate instances with multiple optimal solutions. As a result, the absence of a single fixed reference point introduces new complications, which we discuss below.

We first argue that the algorithm terminates at a nearly-good solution. According to the definition of nearly-good solutions, any optimum solution could cause the solution \(S\) to violate the nearly-good solution condition. We say that \(S\) is nearly-good for \(F\) if \(cost(S) - cost(F) \leq 2\varepsilon \Psi(S, F)\). Algorithm 1 clearly terminates as in each round it selects a new \(S\) with strictly smaller cost. Assume that the set \(S\) in the last round is not nearly-good, meaning that there exists an optimum \(F \in \mathcal{F}_k\) for which \(S\) is not nearly-good. Observe that by Theorem 2, there should exist \(S' \in \mathcal{F}_k\) such that \(\left|S-S^{\prime}\right| \leq \rho\) and \(\operatorname{cost}\left(S^{\prime}\right) \leq \operatorname{cost}(S)+\frac{\operatorname{cost}(F)-\operatorname{cost}(S)+\varepsilon \cdot \Psi(S, F)}{k} < \operatorname{cost}(S)\), since the numerator of the fraction is negative. This is a contradiction because the \(\rho\)-swap local search could discover \(S'\) and move to it in the next iteration, contradicting the assumption that \(S\) was the returned solution.

It only remains to prove a nearly-good solution is found within \(2 k \cdot \ln (n \Delta)\) iterations. Let \(\mathcal{O}= \{O_1, O_2, \ldots, O_\ell\}\) be the set of optimal solutions. For the sake of contradiction, suppose that after \(K=[2 k \cdot \ln (n \Delta)]\) iterations Algorithm 1 has still not encountered a nearly-good solution. Say \(S_0, S_1, \ldots, S_K \in \mathcal{F}_k\) is the sequence of sets held by the algorithm after the first \(K\) iterations, where \(S_0\) is the initial set. Then for all \(i = 0, ..., K\) we should have \(S_i\) is not nearly-good at least with some \(O_{i} \in \mathcal{O}\). Therefore, by Theorem 2, for each \(i \in [K]\) we have

\[\begin{align} \operatorname{cost}\left(S_i\right)-\operatorname{cost}(O_i) & \leq \operatorname{cost}(S_{i - 1})-\operatorname{cost}(O_i)+\frac{\operatorname{cost}(O_i)-\operatorname{cost}(S_{i - 1})+\varepsilon \Psi(S_{i - 1}, O_i)}{k} \\ & < \operatorname{cost}(S_{i - 1})-\operatorname{cost}(O_i)+\frac{\operatorname{cost}(O_i)-\operatorname{cost}(S_{i - 1})}{2 k} \\ & = \left(1-\frac{1}{2 k}\right) \cdot(\operatorname{cost}(S_{i - 1})-\operatorname{cost}(O_i)) \\ & = \left(1-\frac{1}{2 k}\right) \cdot(\operatorname{cost}(S_{i - 1})-\textsf{OPT}) \\ \end{align}\] The second inequality follows from the fact that \(\varepsilon \Psi(S_{i - 1}, O_i) < \frac{1}{2} \Psi(S_{i - 1}, O_i) \leq \frac{1}{2}(\operatorname{cost}(S_{i - 1}) + \operatorname{cost}(O_i))\) by our choice of \(\varepsilon\). Because costs are integral, \(\operatorname{cost}(S_K) - \textsf{OPT}= 0\) which contradicts that \(S_K\) is not a nearly-good solution ◻

Proof. Sample a random partition \(\pi\) of \(O^{\prime} \cup S^{\prime}\) with mentioned properties and consider the effect of the swap \(S \rightarrow S \triangle T\) for each part \(T \in \pi\). We bound \(\mathbf{E}_\pi\left[\sum_{T \in \pi} \operatorname{cost}_{\mathrm{pen}}(S \triangle T)-\operatorname{cost}_{\mathrm{pen}}(S)\right]\) from above by describing a valid way to redirect each \(j \in X\) in each swap. We use the shorthand \(c_j^*=\min(\delta(j, \sigma(j, O))^2, p(j))\) for the cost of connecting \(j\) in \(O\) and \(c_j=\min(\delta(j, \sigma(j, S))^2, p(j))\) similarly for \(S\). Based on possible reassignments of \(j \in X\), we break the analysis into four cases:

Case 1: Either \(\{\sigma(j, S), \sigma(j, O)\} \subseteq S \cap O\) or both \(\delta(j, O)^2, \delta(j, S)^2 \geq p(j)\). The former means that \(\sigma(j, S)\) remains open after each swap, and not reassigning \(j\) is a valid option; the latter means paying the penalty for \(j\) is the better option. Thus, the reassignment cost is bounded by \(c_j^* - c_j = 0\).

Case 2: \(\sigma(j, S) \in S^{\prime}\) and \(\sigma(j, O) \in S \cap O\) and \(\delta(j, S)^2 < p(j)\) (note that if the last condition does not hold, we are in the previous case). Move \(j\) to \(\sigma(j, O)\) when swapping the part \(T\) with \(\sigma(j, S) \in T\). As \(\sigma(j, S)\) remains open when swapping all other \(T^{\prime} \neq T\), we can leave \(j\) assigned to \(\sigma(j, S)\) to upper-bound its cost change for swaps \(T^{\prime} \neq T\) by 0. The total cost assignment for \(j\) is then bounded by \(c_j^*-c_j\).

Case 3: \(j\) with \(\sigma(j, S) \in S \cap O\) and \(\sigma(j, O) \in O^{\prime}\) and \(\delta(j, O)^2 < p(j)\). Move \(j\) to \(\sigma(j, O)\) when swapping the part \(T\) with \(\sigma(j, O) \in T\) and do not move \(j\) when swapping any other part \(T^{\prime} \neq T\). This places an upper bound of \(c_j^*-c_j\) on the total assignment cost change for \(j\).

Case 4: Finally, consider \(j\) with \(\sigma(j, S) \in S^{\prime}\) and \(\sigma(j, O) \in O^{\prime}\) and \(\delta(j, O)^2, \delta(j, S)^2 < p(j)\) (note that if the last condition doesn’t hold, we are in one of the previous cases). Note these are precisely the points \(j \in \overline{X}^{pen}_{S, O}\). From 2 , \[\mathbf{E}_\pi\left[\sum\nolimits_{T \in \pi} \tilde{\Delta}_j^T\right] \leq(1+\varepsilon) \cdot c_j^*-(1-\varepsilon) \cdot c_j=c_j^*-c_j+\varepsilon \cdot\left(c_j+c_j^*\right)\] Aggregating this cost bound for all clients, we see \[\mathbf{E}_\pi\left[\sum\nolimits_{T \in \pi} \operatorname{cost}_{\mathrm{pen}}(S \triangle T)-\operatorname{cost}_{\mathrm{pen}}(S)\right] \leq \operatorname{cost}_{\mathrm{pen}}(O)-\operatorname{cost}_{\mathrm{pen}}(S) +\varepsilon \cdot \Psi_{pen}(S, O)\] Therefore there is some \(\pi\) and some \(T \in \pi\) with \[\begin{align} \operatorname{cost}_{\mathrm{pen}}(S \triangle T)-\operatorname{cost}_{\mathrm{pen}}(S) &\leq \frac{\operatorname{cost}_{\mathrm{pen}}(O)-\operatorname{cost}_{\mathrm{pen}}(S)+\varepsilon \cdot \Psi_{pen}(S, O)}{|\pi|} \\ &\leq \frac{\operatorname{cost}_{\mathrm{pen}}(O)-\operatorname{cost}_{\mathrm{pen}}(S)+\varepsilon \cdot \Psi_{pen}(S, O)}{k} \end{align}\] The last inequality relies on \(|\pi| \leq k\) and \(\operatorname{cost}_{\mathrm{pen}}(O)-\operatorname{cost}_{\mathrm{pen}}(S)+\varepsilon \cdot \Psi_{pen}(S, O) < 0\). ◻

Proof. The proof sis similar to that of [1]. As \(S\) is a nearly-good solution, \(c_j^* \leq c_j\) for \(j \in X^2\), and \(c_j^*=c_j\) for \(j \in X^3\), we have: \[\begin{align} \sum\nolimits_{j \in X^4} c_j & \leq \sum\nolimits_{j \in X^1} c_j+\sum\nolimits_{j \in X^4} c_j=\operatorname{cost}_{\mathrm{pen}}(S)-\sum\nolimits_{j \in X^2} c_j-\sum\nolimits_{j \in X^3} c_j \\ & \leq \operatorname{cost}_{\mathrm{pen}}(S)-\sum\nolimits_{j \in X^2} c_j^*-\sum_{j \in X^3} c_j^* \\ & \leq \operatorname{cost}_{\mathrm{pen}}(O_q)+2 \varepsilon \cdot \Psi_{pen}(S, O_q)-\sum\nolimits_{j \in X^2} c_j^*-\sum\nolimits_{j \in X^3} c_j^* \\ & =\sum\nolimits_{j \in X^1} c_j^*+\sum_{j \in X^4} c_j^*+2 \varepsilon\left(\sum\nolimits_{j \in X^4} c_j^*+c_j\right) \end{align}\] Rearranging, \[\label{eq:k-means-alpha-solution-penalty-polynomial-2} \sum_{j \in X^4} c_j \leq \frac{1}{1-2 \varepsilon} \left(\sum_{j \in X^1} c_j^*+(1+2 \varepsilon) \cdot \sum_{j \in X^4} c_j^*\right) \leq(1+6 \varepsilon) \cdot\left(\sum_{j \in X^1} c_j^*+\sum_{j \in X^4} c_j^*\right)\tag{9}\]  ◻

Proof. Claim 1. For every \(\vec{y}\) in \(A\) define \(M_{\vec{y}}\) to be square centred at \(y\) with side length \(\varepsilon\). Notice that every point in \(R\) is in an \(M_{\vec{y}}\) for some \(\vec{y} \in A\), and since every point in each square is at most \(\varepsilon\) away from its centre, we immediately derive \(D_{r - \varepsilon} \subseteq \bigcup_{\vec{y} \in A \cap D_r} M_{\vec{y}} \subseteq D_{r + \varepsilon}\). Therefore, \[\iint_{D_{r - \varepsilon}} d \mu^\star \leq \iint_{\bigcup_{\vec{y} \in A \cap D_r} M_{\vec{y}}} d \mu^\star = \varepsilon^2 |A \cap D_r| = \varepsilon^2 \iint_{D_r} d \mu\] This yields the first inequality, and the second inequality can be attained in a similar manner.

Claim 2. Again, using the fact that \(\bigcup_{\vec{y} \in A \cap D_{r}} M_{\vec{y}} \subseteq D_{r + \varepsilon}\) we derive \[\begin{align} \iint_{D_{r + \varepsilon}} \delta(\vec{a}, \vec{x}) d \mu^\star &\geq \iint_{\bigcup_{\vec{y} \in A \cap D_{r }} M_{\vec{y}}} \delta(\vec{a}, \vec{x}) d \mu^\star \\ & \geq \iint_{\bigcup_{\vec{y} \in A \cap D_r} M_{\vec{y}}} \delta(\vec{a}, \vec{y}) - \delta(\vec{x}, \vec{y}) d \mu^\star \\ & \geq \iint_{\bigcup_{\vec{y} \in A \cap D_r} M_{\vec{y}}} \delta(\vec{a}, \vec{y}) - \varepsilon \iint_{\bigcup_{\vec{y} \in A \cap D_r} M_{\vec{y}}} d \mu^\star \\ & = \sum_{\vec{y} \in A \cap D_r}\iint_{M_{\vec{y}}} \delta(\vec{a}, \vec{y}) - \varepsilon \iint_{\bigcup_{\vec{y} \in A \cap D_r} M_{\vec{y}}} d \mu^\star \\ & \stackrel{(i)}{\geq} \varepsilon^2 \sum_{\vec{y} \in A \cap D_r} \delta(\vec{a}, \vec{y}) - \varepsilon \iint_{D_{r + \varepsilon}} d \mu^\star \\ & = \varepsilon^2 \iint_{D_r} \delta(\vec{a}, \vec{x}) d \mu - \varepsilon \iint_{D_{r + \varepsilon}} d \mu^\star \\ \end{align}\] Where (i) is due the fact that \(\bigcup_{\vec{y} \in A \cap D_r} M_{\vec{y}} \subseteq D_{r + \varepsilon}\).

Finally, note that \(\iint_{D_{r}} 1 d \mu^\star\) is simply the area of a circle with radius \(r\), which is \(\pi r^2\). Moreover, \(\iint_{D_r} \delta(\vec{x}, \vec{a}) d \mu^\star\) is the volume of a cylinder with radius and height \(r\), which has a cone with radius and height \(r\), carved out from it. Therefore, \(\iint_{D_r} \delta(\vec{x}, \vec{a}) d \mu^\star = \pi r^3 - \frac{1}{3} \pi r^3 = \frac{2}{3} \pi r^3\). This completes the proof. ◻

Proof. Define \(\delta^{pen} (\vec{x}, \vec{y}) := \max \left(\|(x_1, x_2) - (y_1, y_2)\|_2, |x_3 - y_3|\right)\) for \(\vec{x} = (x_1, x_2, x_3)\) and \(\vec{y} = (y_1, y_2, y_3)\). Note that this is a metric, because \[\begin{align} \delta^{pen}(\vec{x}, \vec{z}) &= \max \left(\|(x_1, x_1) - (z_1, z_2)\|_2, |x_3 - z_3|\right) \\ & \leq \max \left(\|(x_1, x_1) - (y_1, y_2)\|_2 + \|(x_1, x_1) - (z_1, z_2)\|_2, |x_3 - y_3| + |y_3 - z_3|\right) \\ & \leq \max\left(\|(x_1, x_2) - (y_1, y_2)\|_2, |x_3 - y_3|\right) + \max \left(\|(y_1, y_1) - (z_1, z_2)\|_2, |y_3 - z_3|\right) \\ & \leq \delta^{pen}(\vec{x}, \vec{y}) + \delta^{pen}(\vec{y}, \vec{z}) \end{align}\] Moreover, \(\delta^{pen}\) has doubling dimension \(3 = \log_2 8\), because any ball of radius \(r\) w.r.t. \(\delta^{pen}\) is a cylinder with radius and height \(r\), which can be covered by \(8\) balls of radius \(r/2\).

Define \(X', C'\) to extend \(X^{grid}, C^{grid}\) into 3 dimensions by setting their third coordinate to zero: \[X' := \{ (u, v, 0) \mid (u, v) \in X^{grid} \}, \quad C' := \{ (u, v, 0) \mid (u, v) \in C^{grid} \}\] Then define \(C'' = \bigcup_{1 \leq i, j \leq k} \{ (2i - 1, 2j, 1), (2i, 2j - 1, 1)\)} and \(C := C' \cup C''\). Also, define \(X\) to be \(X'\) together with \(\varSigma\) points in each of \((2i - 1, 2j, 1)\) and \((2i, 2j - 1, 1)\) for \(1 \leq i, j \leq k\).

We prove that solving the \(3k^2\)-Median instance \((X, C, \delta^{pen})\) is equivalent to solving the \(k^2\)-Median instance \((X^{grid}, C^{grid}, \delta, p^{grid})\). First, we show all \(2k^2\) candidate centres in \(C''\) should be selected in all optimum solutions of \((X, C, \delta^{pen})\). Note that every third coordinate of every candidate centre in \(C''\) is 1. Thus, every data point in \(X'\) has distance at least 1 to them. Moreover, note that for every \((u, w) \in X^{grid}\) such that \(\|(u, w) , (2i, 2j - 1)\|_2 \leq 1\), we have \(\delta^{pen}((u, w, 0), (2i, 2j - 1, 1)) = 1\). Similarly, for every \((u, w) \in X^{grid}\) such that \(\|(u, w) , (2i - 1, 2j)\|_2 \leq 1\), we have \(\delta^{pen}((u, w, 0), (2i, 2j - 1, 1)) = 1\). In other words, the circle with radius 1 around every \((2i, 2j - 1, 0)\) and \((2i, 2j - 1, 0)\) is distance 1 away from some centre in \(C''\). These circles cover all of \(X'\). Thus, the cost of any solution containing \(C''\) will be at most \(\varSigma\). On the other hand, for any solution that doesn’t contain any \(\vec{a} \in C''\), the cost of data points located in \(\vec{a}\) alone is \(\varSigma\).

Next, since aforementioned circles cover \(X'\), any data point with a distance of more than 1 from some selected candidate centre in \(C'\) will be assigned to some centre in \(C''\) and will have a cost of 1. This means that solving \(k^2\)-Median for \((X, C, \delta^{pen})\) is equivalent to solving \(3k^2\)-Median for \((X^{grid}, C^{grid}, \delta, p^{grid})\). Finally, with an argument identical to our argument in Theorem [thm:k-median-penalty-alpha-beta-stable-hardness-mult-mult] we can also prove that \((X, C, \delta^{pen})\) is \((\alpha, \beta)\)-stable for any \(0 < \beta, 1 < \alpha < 1.2\). ◻

Proof. Let the sphere be centred at \((a, b, c, d)\) and radius \(r\). Consider the function \(f(t)=(t-a)^2+\left(t^2-b\right)^2+\left(t^3-c\right)^2+\left(t^4-d\right)^2-r^2\). Note that \(t_1\), \(t_2\), and \(t_3\) are roots of this polynomial. Moreover, \(t_2, t_3\) are also roots of \(f'(t)\). We will apply Descartes’ rule of signs to upper-bound the number of strictly positive roots of \(f'(t)\). The rule says that the number of strictly positive roots of a polynomial is upper-bounded by the number of sign changes between non-zero coefficients (assuming the coefficients are arranged in decreasing order of the degree of their corresponding term). To this end, we expand the polynomial \(f(t)\) : \[\begin{align} f(t) & =t^2-2 a t+a^2+t^4-2 b t^2+b^2+t^6-2 c t^3+c^2+t^8-2 d t^4+d^2-r^2 \\ & =t^8+t^6+(1-2 d) t^4-2 c t^3+(1-2 b) t^2-2 a t+\left(a^2+b^2+c^2+d^2-r^2\right) \end{align}\] Thus, \(f'(t) = 8 t^7+ 6t^5 + 4(1-2 d) t^3 - 6 c t^2 + 2 (1-2 b) t -2 a\).

Hence, the coefficient sequence is given by \(\left(8,6,4(1-2 d),-6 c,2(1-2 b), -2a\right)\). Clearly, there are (at most) 4 changes in sign in this sequence, which implies that the number of strictly positive roots is upper-bounded by 4. However, we already know of 4 roots to this polynomial. Two of them are corresponding to \(t_2, t_3\). Using the median value theorem and observing that \(f(t_1) = f(t_2) = f(t_3)\), there should exist a \(t'_1 \in (t_1, t_2)\) and \(t'_2 \in (t_2, t_3)\) such that \(f'(t'_1) = f'(t'_2) = 0\). Therefore \(f'\) cannot be zero anywhere else. Note that for \(t \rightarrow \infty\), the moment curve must be outside the sphere. Thus, the only way \(t_2, t_3, t'_1, t'_2\) could be the only roots of \(f'\) is for all \(t \in\left(t_1, t_2\right) \cup\left(t_2, t_3\right) \cup (t_3, \infty)\) to lie outside of the sphere. ◻

Proof. Similarly to the proof of Lemma 6 , let the sphere have centre \((a, b, c)\) and radius \(r\). We then analyze the derivative of the function

\[\begin{align} f(t) & =(t-a)^2+\left(t^2-b\right)^2+\left(t^3-c\right)^2-r^2 \\ & =t^2-2 a t+a^2+t^4-2 b t^2+b^2+t^6-2 c t^3+c^2-r^2 \\ & =t^6+t^4-2 c t^3+(1-2 b) t^2-2 a t+\left(a^2+b^2+c^2-r^2\right) \end{align}\] Thus, \(f'(t) = 6 t^5+4 t^3- 6 c t^2+2(1-2 b) t-2 a\).

The coefficients are \(\left(6,4,-6 c, 2(1-2 b),-2 a\right)\), which has (at most) 3 changes of sign. Hence Descartes’ rule implies that there are at most 3 roots. We already know of 3 roots to this polynomial, two of which correspond to \(t_1, t_2\). From the median value theorem, since \(f(t_1) = f(t_2)\), there must exist a \(t'_1 \in (t_1, t_2)\) such that \(f'(t'_1) = 0\). Similar to Lemma 6, the only way \(t_1, t_2, t'_1\) could be the only roots of \(f'\) is for \(t \in\left(O, t_1\right) \cup(t_1, t_2) \cup \left(t_2, \infty\right)\) to all lie outside of the sphere. ◻

Proof. For a fixed parameter \(k\), consider a graph \(G=(V, E)\) on \(n=|V|\) vertices and \(m=|E|\) edges, along with an integer \(s\). Arbitrarily index the vertices \(v_1, \ldots, v_n\). Construct a Euclidean \(k\)-Median instance with penalties in \(\mathbb{R}^4\) denoted by \(\mathcal{I}(G, k)\) as follows. Define \(A_3 := \{ (x_1, x_2, x_3, x_4) \in \mathbb{R}^4: x_4 = 0\}\), i.e., the affine subspace of \(\mathbb{R}^4\) with the fourth coordinate of all points being zero. Every point we define initially lies on \(A_3\).

Consider the 3-dimensional moment curve \(\left(t, t^2, t^3\right)\). For each vertex \(v_i\), we define \(\tilde{v}_i = \left(i ,i^2,i^3, 0 \right) \in A_3\). For each edge \(e_{i, j}=\left(v_i, v_j\right)\) in \(G\), consider the unique 2-sphere in \(A_3\), which we denote by \(\mathbb{S}_{i, j}\), that is perpendicular to the moment curve at points \(\tilde{v}_{i}, \tilde{v}_j\). Let \(c_{i, j}\) and \(r_{i, j}\) denote the centre and radius of the 2-sphere \(\mathbb{S}_{i, j}\), respectively. Let \(c_{i, j} = (a, b, c, 0)\). Then the equation system that uniquely solves \(a, b, c\) is as follows. \[\begin{align} & (i) \quad (i - a)^2+(i^2 - b)^2+(i^3 - c)^2 = (j - a)^2+(j^2 - b)^2+(j^3 - c)^2\\ & (ii) \quad 6 i^5+4 i^3- 6 c i^2+2(1-2 b) i-2 a = 0\\ & (iii) \quad 6 j^5+4 j^3- 6 c j^2+2(1-2 b) j-2 a = 0 \end{align}\] Solving the equation system, we get \[\label{eq:hardness-alpha-k-median-penalty-abc} \begin{align} a &= i\cdot j\cdot (i + j)\cdot (3\cdot i^2 + 3\cdot i\cdot j + 3\cdot j^2 + 1) \\ b &= -(3\cdot i^4 + 12\cdot i^3\cdot j + 15\cdot i^2\cdot j^2 + i^2 + 12\cdot i\cdot j^3 + 4\cdot i\cdot j + 3\cdot j^4 + j^2 - 1)/2 \\ c &= (i + j)\cdot (2\cdot i^2 + i\cdot j + 2\cdot j^2 + 1) \end{align}\tag{10}\]

Let \(q\) be an index pair that gives rise to the maximum \(r_{i, j}\), namely \(q=\operatorname{argmax}_{i, j} \{r_{i, j}\}\) (i.e., \(q\) is of the form " \(i, j\) "). Next, define \(c^\prime_{i, j} := (a, b, c, \sqrt{r_q^2 - r^2_{i, j}})\) so that \(\delta(\tilde{v}_i, c^\prime_{i, j}) = \delta(\tilde{v}_j, c^\prime_{i, j}) = r_q\).

As we discussed in the proof of Lemma 7, for all \(t \in [n]\) we have \(\delta( \tilde{v}_t, c_{i, j})^2 = f(t)\) where \(f(t) := (t-a)^2+\left(t^2-b\right)^2+\left(t^3-c\right)^2\). Using Lemma 7 for any \(t \neq i, j\), we have \(\delta(\tilde{v}_t, c_{i, j})^2 = f(t) > r_{i, j}^2\). Examining equation (10 ) more closely reveals that \(f(t)\) is an integer multiple of \(1/4\) for all \(t \in [n]\). Thus, we derive \(\delta(\tilde{v}_t, c_{i, j})^2 \geq r_{i, j}^2 + \frac{1}{4}\). Therefore, \(\delta(\tilde{v}_t, c^\prime_{i, j})^2 \geq r_q^2 - r_{i, j}^2 + r_{i, j}^2 + \frac{1}{4} = r_q^2 + \frac{1}{4}\).

Next, we notice that in equation 10 , every coordinate of every \(c_{i, j}\) is polynomial with degree at most \(5\) with respect to \(i\) and \(j\), while every coefficient is an integer divided by two. This immediately yields that every \(r^2_{i, j} = O(n^{10})\). In particular, \(r^2_{q} = O(n^{10})\). Denoting \(\varepsilon = \sqrt{\frac{r_{q}^2 + \frac{1}{4}}{r_{q}^2} } - 1\), we would have \(\varepsilon = \Omega(\frac{1}{n^{10}})\). As a result, \(\delta\left(c^\prime_{i, j}, \tilde{z}^* \right) \geq (1+ \varepsilon) r_q\).

We are finally ready to introduce the data points, candidate centres, and penalty function of \(\mathcal{I}(G, k)\). Define data point to be \(X := \{c^\prime_{i, j} \mid i, j \in [n], (v_i, v_j) \in E\}\), candidate centres to be \(C := \{\tilde{v}_i \mid i \in [n]\}\), and penalty function to be \(p(c^\prime_{i, j}) := r_q (1 + \varepsilon)\).

Firstly, Lemma 8 immediately implies that the graph \(G\) has a partial vertex cover of size \(k\), covering at least \(s\) edges, if and only if \(\mathcal{I}(G, k)\) has a solution of cost at most \(r^q (m + (m - s) \varepsilon)\). Therefore, the only thing left to prove is that \(\mathcal{I}(G, k)\) is stable. Secondly, from Lemma 8, we also derive that, assuming that a maximal partial vertex cover of size \(k\) of \(G\) covers \(s^*\) edges, the set of optimum solutions of \(\mathcal{I}(G, k)\) is the set of all \(\{\tilde{v}_{i_1}, \tilde{v}_{i_2}, ..., \tilde{v}_{i_k}\}\) such that \(\{v_{i_1}, v_{i_2}, ..., v_{i_k}\}\) covers \(s^*\) edges in \(G\).

Fix \(\varepsilon^{\prime} = \varepsilon / 2m\). We prove that \(\mathcal{I}(G, k)\) is \((1+\varepsilon^{\prime})\)-stable to complete the proof. Consider any \(\delta \leq \delta^\prime \leq (1 + \varepsilon^\prime) \cdot \delta\) and \(p \leq p^\prime \leq (1 + \varepsilon^\prime) \cdot p\). Assume the maximal partial vertex cover of size \(k\) of \(G\) covers \(s^*\) edges. We only need to show that any optimum solution of the \(k\)-Median instance \((X, C, \delta^\prime, p')\) corresponds to a set of vertices that cover \(s^*\) edges. For every \(S \subseteq C\) define \(\operatorname{cost}_{\mathrm{pen}}^\prime(S) := \sum_{j \in X} \min_{i \in S} \left\{\min \left\{\delta^\prime(i, j), p'(j)\right\}\right\}\). Note that by definition, \(\operatorname{cost}_{\mathrm{pen}}(S) \leq \operatorname{cost}_{\mathrm{pen}}^\prime(S) \leq \operatorname{cost}_{\mathrm{pen}}(S) ( 1 + \varepsilon^\prime)\).

Denote by \(O^\prime\) an optimum solution of \((X, C, \delta^\prime, p')\). For the sake of contradiction assume that \(O^\prime\) corresponds to a set of vertices that cover \(s < s^*\) edges of \(G\), and let \(O \in \mathcal{F}_k\) be corresponding to any set of \(k\) vertices that cover \(s^*\) edges in \(G\). By Lemma 8 we have \[\begin{align} \operatorname{cost}_{\mathrm{pen}}^\prime(O) &\leq (1 + \varepsilon^\prime) \operatorname{cost}_{\mathrm{pen}}(O) = r^q ( m (1 + \varepsilon^\prime) + (m - s^*) \varepsilon (1 + \varepsilon^\prime) ) \\ & < r^q ( m + \frac{\varepsilon}{2} + (m - s^*) \varepsilon + \frac{\varepsilon^2}{2} ) < r^q ( m + (m - s^* + 1) \varepsilon )\\ & \leq r^q ( m + (m - s) \varepsilon) = \operatorname{cost}_{\mathrm{pen}}(O^\prime) \leq \operatorname{cost}_{\mathrm{pen}}^\prime(O^\prime) \end{align}\] This is a contradiction. Therefore, every optimum solution of \((X, C, \delta^\prime, p')\) is also an optimum solution of \((X, C, \delta, P)\), which completes the proof. ◻

Proof. For a fixed parameter \(k\), we are given a graph \(G=(V, E)\) on \(n=|V|\) vertices and \(m=|E|\) edges, along with an integer \(s\). Arbitrarily index the vertices \(v_1, \ldots, v_n\). Inspired by Theorem 5.1 of [12], we construct a Euclidean \(k^\prime\)-Median instance in \(\mathbb{R}^6\) with \(k^\prime = k + 1\) denoted by \(\mathcal{I}(G, k)\). We emphasize that the proof has been significantly modified to fit our stability setting while also being simplified. Define \(A_4 := \{ (x_1, x_2, x_3, x_4, x_5, x_6) \in \mathbb{R}^4: x_5 = 0, x_6 = 0\}\), i.e., the affine subspace of \(\mathbb{R}^4\) with the fifth and sixth coordinates of all points being zero. Every point we define initially lies on \(A_4\).

Consider the 4-dimensional moment curve \(\left(t, t^2, t^3, t^4\right)\). For each vertex \(v_i\), we define \(\tilde{v}_i = \left(i + 1,(i+1)^2,(i+1)^3,(i+1)^4, 0, 0 \right) \in A_4\), and \(z^{*} = (1, 1, 1, 1, 0, 0) \in A\). For each edge \(e_{i, j}=\left(v_i, v_j\right)\) in \(G\), consider the unique 3-sphere in A, which we denote by \(\mathbb{S}_{i, j}\), that is perpendicular to the moment curve at point \(\tilde{v}_{i}, \tilde{v}_j\) and also has \(z^*\) on its surface. Let \(c_{i, j}\) and \(r_{i, j}\) denote the centre and radius of the 3-sphere \(\mathbb{S}_{i, j}\), respectively. Let \(c_{i, j} = (a, b, c, d, 0, 0)\) and \(\tilde{i} = (i + 1), \tilde{j} = (j + 1)\). Then the equation system that uniquely solves \(a, b, c, d\) is as follows. \[\begin{align} & (i) \quad (\tilde{i} - a)^2+(\tilde{i}^2 - b)^2+(\tilde{i}^3 - c)^2+(\tilde{i}^4 - d)^2 \\ & \quad \quad \quad= (\tilde{j} - a)^2+(\tilde{j}^2 - b)^2+(\tilde{j}^3 - c)^2+(\tilde{j}^4 - d)^2 \\ & \quad \quad \quad = (1 - a)^2+(1 - b)^2+(1 - c)^2+(1 - d)^2 \\ & (ii) \quad a + 2\tilde{i} b + 3\tilde{i}^2 c + 4\tilde{i}^3 d = \tilde{i} + 2\tilde{i}^3 + 3\tilde{i}^5 + 4\tilde{i}^7, \\ & (iii) \quad a + 2\tilde{j} b + 3\tilde{j}^2 c + 4\tilde{j}^3 d = \tilde{j} + 2\tilde{j}^3 + 3\tilde{j}^5 + 4\tilde{j}^7. \end{align}\] One can verify, using any solver system, that the solution to the system of equations is \[\label{eq:hardness-alpha-k-median-abcd} \begin{align} a &= -\tilde{i}\cdot \tilde{j}\cdot(\tilde{i} + \tilde{j})\cdot(2\cdot \tilde{i}^3\cdot \tilde{j} + 4\cdot \tilde{i}^3 + \tilde{i}^2\cdot \tilde{j}^2 + 6\cdot \tilde{i}^2\cdot \tilde{j} + 3\cdot \tilde{i}^2 + 2\cdot \tilde{i}\cdot \tilde{j}^3 + 6\cdot \tilde{i}\cdot \tilde{j}^2 + 5\cdot \tilde{i}\cdot \tilde{j} \\ & + 4\cdot \tilde{i} + 4\cdot \tilde{j}^3 + 3\cdot \tilde{j}^2 + 4\cdot \tilde{j} + 2) \\ b &= (8\cdot \tilde{i}^5\cdot \tilde{j} + 4\cdot \tilde{i}^5 + 17\cdot \tilde{i}^4\cdot \tilde{j}^2 + 22\cdot \tilde{i}^4\cdot \tilde{j} + 3\cdot \tilde{i}^4 + 20\cdot \tilde{i}^3\cdot \tilde{j}^3 + 34\cdot \tilde{i}^3\cdot \tilde{j}^2 + 20\cdot \tilde{i}^3\cdot \tilde{j} \\ & + 4\cdot \tilde{i}^3 +17\cdot \tilde{i}^2\cdot \tilde{j}^4 + 34\cdot \tilde{i}^2\cdot \tilde{j}^3 + 29\cdot \tilde{i}^2\cdot \tilde{j}^2 + 20\cdot \tilde{i}^2\cdot \tilde{j} + 2\cdot \tilde{i}^2 + 8\cdot \tilde{i}\cdot \tilde{j}^5 + 22\cdot \tilde{i}\cdot \tilde{j}^4 \\ & + 20\cdot \tilde{i}\cdot \tilde{j}^3 + 20\cdot \tilde{i}\cdot \tilde{j}^2+ 8\cdot \tilde{i}\cdot \tilde{j} + 4\cdot \tilde{j}^5 + 3\cdot \tilde{j}^4 + 4\cdot \tilde{j}^3 + 2\cdot \tilde{j}^2 + 1)/2 \\ c &= -(\tilde{i} + \tilde{j})\cdot (2\cdot \tilde{i}^4 + 6\cdot \tilde{i}^3\cdot \tilde{j} + 4\cdot \tilde{i}^3 + 5\cdot \tilde{i}^2\cdot \tilde{j}^2 + 6\cdot \tilde{i}^2\cdot \tilde{j} + 4\cdot \tilde{i}^2 + 6\cdot \tilde{i}\cdot \tilde{j}^3 + 6\cdot \tilde{i}\cdot \tilde{j}^2 \\ &+ 7\cdot \tilde{i}\cdot \tilde{j} + 4\cdot \tilde{i} + 2\cdot \tilde{j}^4 + 4\cdot \tilde{j}^3 + 4\cdot \tilde{j}^2 + 4\cdot \tilde{j} + 2)\\ d &= (5\cdot \tilde{i}^4 + 8\cdot \tilde{i}^3\cdot \tilde{j} + 4\cdot \tilde{i}^3 + 9\cdot \tilde{i}^2\cdot \tilde{j}^2 + 6\cdot \tilde{i}^2\cdot \tilde{j} + 6\cdot \tilde{i}^2 + 8\cdot \tilde{i}\cdot \tilde{j}^3 + 6\cdot \tilde{i}\cdot \tilde{j}^2 + 8\cdot \tilde{i}\cdot \tilde{j} \\ & + 4\cdot \tilde{i} + 5\cdot \tilde{j}^4 + 4\cdot \tilde{j}^3 + 6\cdot \tilde{j}^2 + 4\cdot \tilde{j} + 3)/2 \\ \end{align}\tag{11}\]

Similar to Theorem [thm:k-median-alpha-hardness-panlty], let \(q:=\operatorname{argmax}_{i, j} \{r_{i, j}\}\) and define \(c^\prime_{i, j} := (a, b, c, d, \sqrt{r_q^2 - r^2_{i, j}}, 0)\) so that \(\delta(z^*, c^\prime_{i, j}) = \delta(\tilde{v}_i, c^\prime_{i, j}) = \delta(\tilde{v}_i, c^\prime_{i, j}) = r_q\). Again for any \(t \neq i, j \in [n]\), we have \(\delta(\tilde{v}_t, c^\prime_{i, j})^2 \geq r_q^2 + \frac{1}{4}\). We also define \(\tilde{z}^{*} = \left(1, 1, 1, 1, 0, \frac{1}{2} \right)\), and subsequently \(\delta^2(\tilde{z}^*, c_{i, j}) = r^2_q + \frac{1}{4}\).

Moreover, in 10 every coordinate of every \(c_{i, j}\) is a polynomial with degree at most \(7\) with respect to \(\tilde{i}\) and \(\tilde{j}\), while every coefficient is an integer divided by two. This immediately yields that \(r^2_{i, j} = O(n^{14})\). In particular, \(r^2_{q} = O(n^{14})\). Setting \(\varepsilon = \sqrt{\frac{r_q^2 + \frac{1}{4}}{r_{q}^2} } - 1,\) we would have \(\delta(z^*, c^\prime_{i, j}) = (1 + \varepsilon) r_q\) and \(\varepsilon = \Omega(\frac{1}{n^{14}})\).

We are finally ready to introduce the data points and candidate centres of \(\mathcal{I}(G, k)\). Define the set of candidate centres to be \(C := \{\tilde{v}_1, \tilde{v}_2, ..., \tilde{v}_n, \tilde{z}^*\}\), and the set of data points \(X\) to be \(\{c^\prime_{i, j} \mid i, j \in [n], (v_i, v_j) \in E\}\) in addition to \(\lceil m r_q \rceil\) points in \(\tilde{z}^*\).

Lemma 9 and Lemma 10 imply that the graph \(G\) has a partial vertex cover of size \(k\) covering at least \(s\) edges if and only if \(\mathcal{I}(G, k)\) has a solution of cost at most \(r^q (m + (m - s) \varepsilon)\). Therefore, the only thing left to prove is that \(\mathcal{I}(G, k)\) is stable.

Fix \(\varepsilon^{\prime} = \varepsilon / 2m\). We prove that \(\mathcal{I}(G, k)\) is \((1 + \varepsilon^{\prime})\)-stable, which completes the proof. Consider any \(\delta \leq \delta^\prime \leq (1 + \varepsilon^\prime) \cdot \delta\) and \(p \leq p' \leq (1 + \varepsilon^\prime) \cdot p\). Assume that a maximal partial vertex cover of size \(k\) of \(G\) covers \(s^*\) edges. It suffices to show that any optimum solution of \((X, C, \delta^\prime)\) corresponds to a set of vertices that covers \(s^*\) edges. For every \(S \in \mathcal{F}_{k^\prime}\), define \(\operatorname{cost}^\prime(S) = \sum_{j \in X} \min_{i \in S} \delta^\prime(i, j)\). Note that by definition \(\operatorname{cost}(S) \leq \operatorname{cost}^\prime(S) \leq \operatorname{cost}(S) ( 1 + \varepsilon^\prime)\).

Let \(O^\prime\) be an optimum solution of the \(k^\prime\)-Median instance \((X, C, \delta^\prime)\). For the sake of contradiction assume that \(O^\prime\) corresponds to a set of vertices that cover \(s < s^*\) edges of \(G\), and let \(O\) correspond to any set of vertices that cover \(s^*\) edges in \(G\). Similarly to the proof of Theorem [thm:k-median-alpha-hardness-panlty], and using Lemma 8, we derive \[\begin{align} \operatorname{cost}^\prime(O) &\leq (1 + \varepsilon^\prime) \operatorname{cost}(O) < r^q \left( m + (m - s^* + 1) \varepsilon \right) \leq r^q ( m + (m - s) \varepsilon) \\ & = \operatorname{cost}(O^\prime) \leq \operatorname{cost}^\prime(O^\prime) \end{align}\] This is a contradiction. Therefore, every optimum solution of \((X, C, \delta^\prime)\) is also an optimum solution of \((X, C, \delta)\), which completes the proof. ◻