Proof. Enumerate all sets of at most five facilities to remove and all sets of at most five facilities to add, checking those exchanges that leave exactly \(r\) facilities. There are \(O(N^{10})\) pairs, and each resulting cost can be evaluated in polynomial time. Perform any strict improvement and repeat. Every cost is an integer between zero and \(nB\), so at most \(nB\) strict improvements are performed.

For completeness, consider an exchange with removal set \(R\subseteq S\), addition set \(A\subseteq F\), \(|R|,|A|\le5\), and nonempty result \(T=(S\setminus R)\cup A\) of size at most \(r\). All facilities in \(S\setminus T\) belong to \(R\), and \(|S\setminus T|\ge r-|T|\). Restoring any \(r-|T|\) of them gives a set of size \(r\), still differing from \(S\) by at most five removals and five additions, with cost at most \(\operatorname{cost}(T)\). Thus the final local optimum also rules out every improving exchange of this form. ◻

Proof. Protect the proxy set \(\Phi=\{\phi_i:i\in O_g\}\), meaning that no exchange below removes any member of \(\Phi\). Write \(g=|O_g|\), \(m=|O_b|\), and \(q=|S\setminus\Phi|\). Distinctness of the proxies and \(h\le|S|\) imply \[q=|S|-g\ge h-g=m.\] If \(m=0\), every client can use its proxy, so \(S_g\le D_g\) and both inequalities follow. Assume henceforth that \(m>0\); in particular an unprotected facility exists.

For every \(i\in O_b\), choose a nearest facility \(\nu(i)\in S\) to \(i\). Retain this choice for the routing argument. Separately define an image \(\psi(i)\in S\setminus\Phi\): if \(\nu(i)\) is unprotected, take \(\psi(i)=\nu(i)\); if \(\nu(i)\) is protected, take any unprotected facility as \(\psi(i)\). Thus the image used to organize exchanges need not be the nearest facility used for routing.

Let \(a\) be the number of nonempty image classes of \(\psi\). A class of size \(t\) receives its image facility together with \(t-1\) auxiliary unprotected facilities that are not images of any bad center. These sets of facilities can be chosen disjointly across classes: the total number of auxiliary facilities needed is \(m-a\), whereas the number available is \(q-a\ge m-a\). Facilities in these allocated sets will be called slots.

We give a nonnegative weighting of feasible exchanges. For an image class \(I\subseteq O_b\) of size \(t\le5\), make the single exchange of weight one that removes its \(t\) slots and adds every center in \(I\). For a class of size \(t>5\), for each \(i\in I\) and each of the \(t-1\) auxiliary slots, make the exchange that removes that slot and adds \(i\), with weight \(1/(t-1)\). These are exchanges of width at most five. Their results are nonempty and have size at most \(|S|\), even when an added facility already belongs to \(S\): they are interpreted as actual set unions, and Lemma 4’s padding observation applies. Local optimality therefore gives a nonnegative cost change for every one of them.

Every bad center is added in exchanges of total weight exactly one. A slot allocated to a class of size at most five has removal weight one. In a class of size \(t>5\), the image slot is never removed and each auxiliary slot has removal weight \[\frac{t}{t-1}\le\frac65=u.\] Unallocated facilities are never removed. Thus every facility in \(S\) has total removal weight at most \(u\).

We also need a preservation property. In every exchange that does not add a particular bad center \(i\), its remembered nearest facility \(\nu(i)\) survives. If \(\nu(i)\) is protected, this is part of the construction. Otherwise \(\nu(i)=\psi(i)\) is the image slot of \(i\)’s class. A small-class exchange that removes this slot adds all centers of the class, including \(i\); a large-class exchange never removes it. Other classes have disjoint slots. This proves the property, including when \(O\cap S\ne\varnothing\).

Consider a client \(p\in C_i\) with \(i\in O_b\). In every exchange that adds \(i\), route \(p\) to \(i\), at cost change \(d_p^*-s_p\). In any other exchange retain its old assignment if possible. If its old facility is removed, use the preserved facility \(\nu(i)\), for which \[\begin{align*} d(p,\nu(i)) &\le d_p^*+d(i,\nu(i))\\ &\le d_p^*+d(i,s(p)) \le 2d_p^*+s_p. \end{align*}\] The weighted sum of these upper bounds for \(p\) is therefore at most \[d_p^*-s_p+2u d_p^*.\] Here the first term uses total addition weight one. For the other exchanges we upper-bound their removal weight by the full removal weight of \(s(p)\), which is at most \(u\); the extra charge \(2d_p^*\) is nonnegative. Removing and immediately adding back the same facility only reduces the need for this extra charge.

For a client \(p\in C_i\) with \(i\in O_g\), keep the old assignment unless its serving facility is removed, in which case use the protected proxy \(\phi_i\). Nearest assignment in \(S\) gives \(d(p,\phi_i)-s_p\ge0\), so its weighted cost change is at most \(u(d(p,\phi_i)-s_p)\).

Each described routing is feasible for its exchange. Summing the upper bounds on cost change, and using nonnegativity of every actual cost change, yields \[0\le P_b-S_b+2uP_b+u(D_g-S_g).\] This is (5). Since \(u\ge1\), it implies (6). Declaring every center bad gives the final assertion. ◻

Proof. Set \[V_i=\sum_{p\in C_i}(s_p+d_p^*),\qquad q_0=\bigl|\{i\in O:n_i\operatorname{sep}_i<b\}\bigr|.\] The all-bad case of Lemma 5 gives \[ \sum_{i\in O}V_i=\operatorname{cost}(S)+P\le6P. \tag{10}\] Call a center short if \(n_i\operatorname{sep}_i<b\). In particular, every empty comparison cluster is short.

Proof. For every \(j\), the number \(q_j=\max\{d_j,P/(mj)\}\) has at least \(j\) clients in its closed ball and \(q_jj\ge P/m\), so it is feasible. Conversely, if \(q\) is feasible and \(j=|\mathcal D(w,q)|\), then \(j\ge1\), \(d_j\le q\), and \(P/(mj)\le q\). Hence \(\min_jq_j\le q\). These two observations prove Equation (20), attainment, and positivity.

For a selected leader the cluster is nonempty. At least \(n_i/2\) of its clients have \(d_p^*\le2\bar d_i\): otherwise their distances alone would sum to more than \(P_i\). When \(\bar d_i=0\) all clients have zero distance, so the same assertion holds. These clients are within \((a+2)\bar d_i\) of \(w_i\). At radius \((a+2)\bar d_i+2P/(mn_i)\) their population certifies feasibility in Equation (19). Multiply the resulting bound by \(n_i\) and sum. Distinct leaders here belong to distinct bad clusters, so \(|A|\le m\) and \(\sum_{i\in A}P_i\le P\). ◻

Proof. One may first form the complete graph on the original metric points with their metric edge lengths and join \(\delta_\infty\) to all of them by edges of length \(\Delta\). A path through \(\delta_\infty\) cannot shorten an original distance, since its two adjacent edges have total length \(2\Delta\). Taking the resulting shortest-path metric and then attaching leaves proves the distance formulas and all triangle inequalities. In particular, for different leaves the distance is \(R_i+d(w_i,w_j)+R_j\).

The distance-to-set function is \(1\)-Lipschitz. More directly, \(d(x,O)\le d(x,w_i)+d(w_i,O)\le d(x,\delta_i)\), whereas \(d(x,x_i)\le d(x,w_i)+d(w_i,x_i)\le d(x,\delta_i)\). Every original facility is within \(\Delta\) of each original client, which proves the permanent-dummy assertion for a nonempty solution.

Fix an order on the original facilities, put the permanent dummy after them, and order leaves by creation time. Assign each client to the first nearest available reference point in this order. Leaf addition preserves the distances and relative order of all existing choices. A client whose chosen reference point was outside a given fixed subset of original centers cannot begin to choose a point in that subset after more choices are added. This proves the assertion simultaneously for every such subset, including a subset unknown to the algorithm. ◻

Proof. Consider two third-menu additions, with the first earlier than the second, and give their quantities subscripts \(a,b\). Suppose a client belongs to both closed client balls. Then \[d(w_a,w_b)\le q_a+q_b<\frac{r_a+r_b}{10}.\] Both inequalities \(q_a<r_a/10\) and \(q_b<r_b/10\) are strict because these are third-menu additions. Lipschitzness of distance to \(O\) gives \(|r_a-r_b|<(r_a+r_b)/10\), and hence \(9/11<r_a/r_b<11/9\). The earlier persistent leaf is an available competitor in \(D_\Lambda\) at the later step. Its correct radius therefore gives \[\begin{align*} D_\Lambda &\le d(w_b,w_a)+R_a\\ &<\frac{r_a+r_b}{10}+(1+\kappa)r_a+\kappa r_a/10\\ &\le\left(\frac1{10}+ \frac{11}{9}\left(\frac{11}{10}+\frac{11\kappa}{10}\right) \right)r_b <3r_b<10r_b. \end{align*}\] Here the penultimate strict inequality uses \(\kappa\le1\). This contradicts the condition for prescribing the third menu at \(b\). Thus the client sets are disjoint; no ambient space containing whole geometric balls is needed.

For a third-menu addition every \(p\in\mathcal D(w,q)\) satisfies \(d(p,O)\ge r-d(w,p)\ge r-q>0.9r\). The attained population inequality from Lemma 7 gives \(|\mathcal D(w,q)|\ge P/(mq)\). Disjointness now implies \[P=\sum_{p\in D}d(p,O) \ge0.9\sum_{\text{third menu}}r\,|\mathcal D(w,q)| \ge\frac{0.9P}{m}\sum_{\text{third menu}}\frac rq.\] Cancel \(P>0\) to obtain the first bound in Equation (24). For every third-menu entry, \[j=\lceil r/(\kappa q)\rceil\le r/(\kappa q)+1.\] There are at most \(m\) additions, so the second bound follows. In particular, \[j\le\frac{10m}{9\kappa}+1\le\frac{2m}{\kappa}+1\le J_{\kappa,m}.\] Availability follows inductively: a proposed third-menu addition is disjoint from previous ones using only their radii, so the same population argument certifies its prescribed index before its radius is selected.

Set \[c_\kappa=\min\left\{\frac1{3M_\kappa}, \frac1{3(E_\kappa+1)},\frac13\right\}.\] The prescribed choice in either of the first two menus has probability at least \(c_\kappa\). In the third it has probability at least \(c_\kappa2^{-j}\), since the normalizing sum is less than one. Multiplication and Equation (24) prove Equation (25). If fewer than \(m\) additions occur, replacing their number by \(m\) only weakens the lower bound. ◻

Proof. First use the exact rational distributions. Include the sampled client, mode, menu, and menu entry in the history; entries irrelevant to a removal are omitted. Fix a guide-supported nonterminal history \(\gamma\). Let \(E_\gamma\) be its prescribed mode-and-client event and let \(p_\gamma\ge\rho\) be that event’s probability in the actual experiment. For a particular eligible client, the ratio of its actual mode-and-client probability to its guided conditional probability is exactly \(p_\gamma\). For a ball addition multiply this ratio by the probability of its prescribed menu and entry, since the guide makes that choice deterministically. Correct upward radii ensure that the ball contains the corresponding comparison center. Thus no supported operation is rejected for an empty facility ball or for exceeding the observable limits.

Along any terminal guided trajectory \(\gamma\) of length at most \(2m\), multiply these conditional ratios. Lemma 9 applies to its full adaptive sequence and bounds the product of its menu losses. Consequently the actual cylinder probability of \(\gamma\) is at least the right-hand side of Equation (26) times its guided probability. The terminal guided histories form a prefix-free family: once the guide’s stopping rule holds, it makes no further draws. Their corresponding cylinders in the actual history tree are therefore disjoint. Summing over them, and using that the guide stops with total probability one, proves the bound. This summation does not select one fixed sequence of leaders; it integrates over every client history generated by the guide. Nor does it require the actual algorithm to know the stopping predicate: it records all prefixes, including the terminal one on every one of these cylinder events.

For the finite-bit assertion, the rational-arithmetic and dyadic implementation proved below preserves the probability of every elementary transition from below by a factor \(1/2\). At most \(2m\) such factors change Equation (26) by at worst \(2^{-2m}\), which has the asserted form. ◻

Proof. If \(\bar d_i>0\), fewer than \(n_i/a\) clients have distance strictly greater than \(a\bar d_i\), by summing their distances. If \(\bar d_i=0\), all clients belong to \(N_i(a)\). This proves the population bound in both cases. Choose a client in \(N_i(a)\) minimizing its reference distance; that distance is at most \(T_i(a)/|N_i(a)|\). The triangle inequality through this client proves Equation (27).

Apply the population argument with cutoff \(1.02=51/50\). The set of clients with \(d_p^*\le1.02\bar d_i\) has at least \(n_i/51\ge n_i/60\) members and is contained in \(N_i\). Its member of minimum reference distance gives the first inequality in Equation (28). For \(p\notin N_i\), one has \(d_p^*>1.2\bar d_i\), so \[d(p,H)\le d_p^*+d(i,H) \le\left(1+\frac{1.02}{1.2}\right)d_p^* +\frac{60T_i}{n_i} =1.85d_p^*+\frac{60T_i}{n_i}.\] If the mean is zero, there are no clients outside \(N_i\), and this last assertion is vacuous. ◻

Proof. Every proxy remains in \(S\setminus Q\) because \(Q\subseteq S_0\). The reference distances of good clients therefore sum to at most \(P_g+0.01P\). For a covered bad cluster, its leaf gives the pointwise bound \[ d(p,H)\le d_p^*+r_i+R_i\qquad(p\in C_i). \tag{33}\] Use Equation (23), \(r_i\le1.2\bar d_i\), and Lemma 7 to obtain, with \(P_A=\sum_{i\in A}P_i\), \[\sum_{i\in A}\sum_{p\in C_i}d(p,H) \le(3.4+1.2\kappa)P_A+5.2\kappa P.\] For an uncovered nonempty cluster, retain its near-client cost \(T_i\) and sum Equation (28) over the others. Their number is at most \(n_i\), so this cluster contributes at most \(1.85P_i+61T_i\). Empty clusters contribute zero. With \(P_B=\sum_{i\in B}P_i\) this yields \[\begin{align*} W(H) &\le P_g+0.01P+(3.4+1.2\kappa)P_A+5.2\kappa P +1.85P_B+61T_{\rm near}(H)\\ &\le(3.41+6.4\kappa)P+61T_{\rm near}(H) <3.42P+61T_{\rm near}(H). \end{align*}\] Here \(P_g+P_A+P_B=P\).

If \(T=T_{\rm near}(H)>\kappa P\), the ball event has probability \[\frac{T}{2W(H)}\ge\frac{T}{2(3.42P+61T)}\ge\rho_\kappa.\] If instead \(T\le\kappa P\) and \(I(H)>\kappa P\), then \(W(H)\le(3.42+61\kappa)P\). The removal event has probability \[\frac{I(H)}{2W(H)}>\frac{\kappa}{2(3.42+61\kappa)}=\rho_\kappa.\] In either nonterminal case \(W(H)>0\), so the client distribution is defined. ◻

Proof. Define the guide as follows. At a correct state satisfying Equation (30), stop. Otherwise, if the first inequality fails, condition the actual client-and-mode draw on ball mode and a client in \(\bigcup_{i\in B}N_i\). Such a client has a unique assigned comparison cluster \(i\in B\); add it to \(A\) with the prescribed correct radius and its leaf. If only the second inequality fails, condition on removal mode and a client assigned to \(R^*\), and delete that original center. Lemma 12 supplies the same fixed positive lower bound \(\rho_\kappa\) on both conditioning events. Every guided ball addition covers a new nonempty bad cluster, and every guided removal deletes a new member of \(S_0\). Thus all its states remain correct and all good proxies persist.

There are at most \(m\) possible removals and at most \(m\) distinct clusters that can receive balls. If all nonempty bad clusters have received balls and all of \(S_0\) has been removed, both stopping quantities are zero. More generally, a nonterminal state always has one of the progress operations just described. Each such operation increases \(|A|+|Q|\) by one, a quantity at most \(2m\). The guide therefore stops within \(2m\) steps. Empty bad clusters can remain in \(B\) throughout; they never contribute to the stopping quantities or to any division by \(n_i\).

Apply Lemma 10 with \(\rho=\rho_\kappa\). Its exponential probability bound gives a recorded terminal prefix, and the guide’s invariants give all the stated properties, including Lemma 7 for the radius sum. The arithmetic and running-time assertions follow from the implementation below. ◻

Proof. Empty parts may be discarded. Write \(q=|E|\), let \(g_{\max}\) denote the maximum in the statement, and compute \(M_1=\max_{e\in E}g(\{e\})\) using \(q\) oracle calls. If \(E\) is empty or \(M_1=0\), submodularity and telescoping give \(g(Y)\le\sum_{e\in Y} g(\{e\})=0\) for every \(Y\), so the conclusion is immediate. Otherwise \(a\ge1\) and \(0<M_1\le g_{\max}\).

For vectors \(x\ge0\) with \(\sum_{e\in E_j}x_e\le1\), independently in each part select \(e\) with probability \(x_e\), and select nothing with the remaining probability. Let \(R_x\) be the resulting feasible random set and \(G(x)=\mathbb E[g(R_x)]\). Multilinearity across the parts gives \[ \partial_eG(x)=\mathbb E\bigl[ \Delta_e g(R_x\setminus E_j)\bigr],\qquad e\in E_j. \tag{34}\] Every integrand is between zero and \(M_1\). For a fixed feasible maximizer \(O_g\), monotonicity and submodularity give, for every \(R_x\), \[g_{\max}-g(R_x) \le\sum_{e\in O_g}\Delta_e g(R_x) \le\sum_{e\in O_g}\Delta_e g(R_x\setminus E_{j(e)}).\] The last inequality also holds when \(e\in R_x\), since its left summand is then zero. Thus \[ \sum_{j=1}^a\max_{e\in E_j}\partial_eG(x) \ge g_{\max}-G(x). \tag{35}\]

Choose a dyadic rational \(\tau\) of bit length \(O(\log(2/\varepsilon))\) with \(\min\{\varepsilon/8,1/16\}\le\tau\le\min\{\varepsilon/4,1/8\}\) and let \(T\) be the smallest power of two at least \(a^2/\tau\). Starting at \(x^{(0)}=0\), perform \(T\) steps. At step \(t\), estimate every derivative in Equation (34), choose a largest estimated derivative in each part, and add \(1/T\) to each chosen coordinate. Let \(v^{(t)}\) be the zero–one vector of chosen coordinates. At time \(t\) every part has total mass \(t/T\), so all iterates and all segments \(x^{(t)}+uv^{(t)}\), \(0\le u\le1/T\), are feasible.

There are \(Q_0=Tq\) derivative estimates. For each estimate take the mean of \[L=\left\lceil\frac{Q_0a^2}{4\tau^3}\right\rceil\] independent samples of its marginal. Each sample has variance at most \(M_1^2/4\). Chebyshev’s inequality shows that the probability of error greater than \(\tau M_1/a\) is at most \(\tau/Q_0\). This assertion holds conditionally on every preceding choice, because fresh samples are used at the current iterate. The union bound therefore shows that all estimates are accurate with probability at least \(1-\tau\), even though the iterates are adaptive. On this event, the chosen direction obeys \[ \nabla G(x^{(t)})\cdot v^{(t)} \ge g_{\max}-G(x^{(t)})-2\tau M_1. \tag{36}\]

For completeness, the finite step has a controlled integration error. Couple a categorical draw at \(x\) and at \(x+uv\) by changing a part’s outcome only when the additional mass \(u\) assigned to its selected coordinate is used. Such a change occurs with probability \(u\) in each part. For a derivative with its own part omitted, the probability that any other part changes is at most \(au\). Since the marginal in Equation (34) lies in \([0,M_1]\), its expectation changes by at most \(auM_1\). Summing over the \(a\) selected coordinates and integrating for \(0\le u\le1/T\) gives, with the slightly looser bound convenient below, \[G(x^{(t+1)})-G(x^{(t)}) \ge\frac{g_{\max}-G(x^{(t)})-2\tau M_1}{T} -\frac{a^2M_1}{T^2} \ge\frac{g_{\max}-G(x^{(t)})-3\tau M_1}{T}.\] Iterating from \(G(0)=0\) yields \[G(x^{(T)})\ge \bigl(1-(1-1/T)^T\bigr)(g_{\max}-3\tau M_1) \ge(1-1/e-3\tau)g_{\max}.\] Here \(g_{\max}-3\tau M_1\ge0\). Sample the final categorical set independently after the estimates. On estimation failure its gain is still nonnegative. Consequently its unconditional expected gain is at least \[(1-\tau)(1-1/e-3\tau)g_{\max} \ge(1-1/e-4\tau)g_{\max} \ge(1-1/e-\varepsilon)g_{\max}.\] All categorical probabilities in this algorithm have denominator \(T\); one uniform integer in \(\{0,\ldots,T-1\}\) therefore samples each part exactly using \(\log_2T\) fair bits. The oracle count and the number of such draws are polynomial in the stated parameters. In the present application oracle values are rational numbers of polynomial bit length, so the arithmetic also takes polynomial time. Monotonicity justifies filling parts. Finally \(1-1/e>0.6321\), so an error smaller than \(0.0121\) gives \(0.62\). For the last assertion choose a rational \(\varepsilon\) with \(0<\varepsilon\le\theta-1/e\). ◻

Proof. Select the \(b_{\mathrm{red}}\) red removals attaining the last term of Equation (38), and use the blue removals and destinations stored by the dynamic program. Fill every unused ball with an arbitrary facility in that ball. Let \(X_{\mathrm{fill}}\) be the underlying filled facility set, \(Y_{\mathrm{blue}}\) the blue destinations, and \(R_{\mathrm{red}},R_{\mathrm{blue}}\) the two removal sets. Form \[U'=\bigl(S\setminus(Q\cup R_{\mathrm{red}}\cup R_{\mathrm{blue}})\bigr) \cup X_{\mathrm{fill}}\cup Y_{\mathrm{blue}}.\] These are set unions. Since the removal sets are disjoint and have total size \(r\), and the additions have total size at most \(a+c=m\), \[ |U'|\le h-|Q|-r+a+c=h. \tag{39}\] This inequality permits repeated ball choices, overlapping balls, coincidences with retained facilities, and reopening any member of \(Q\) or either removal set. Pad \(U'\) to size \(h\), if necessary, obtaining \(U_X\). Padding is possible because \(h\le|F|\) and makes \(U_X\) nonempty. Only now invoke domination of the permanent dummy: any real center is within the original diameter of every original point. A filled center in \(\mathcal F_i\) similarly satisfies \(d(y,X_{\mathrm{fill}})\le d(y,w_i)+R_i=d(y,\delta_i)\) for any original point \(y\). Every point of \(Z\) therefore has its distance from original points attained or improved by the final solution.

For a client whose minimum in the base term uses \(X\), the distance is already attained by \(U_X\). Otherwise use its fixed assignment in \(H\). A retained real center or a dummy is covered by the preceding argument. If its assigned center \(s\) is removed red, triangle inequality bounds its new distance by \(d(p,H)+d(s,Z\cup X)\). If it is removed blue, use \(d(p,H)+d(s,y_s)\) for its stored destination \(y_s\). Charging these additional distances to all \(w'_s\) clients of a removed center is an upper bound even when some of their base minima use \(X\). Summing proves \(\operatorname{cost}(U_X)\le\Psi(X)\).

For submodularity, each client’s base-cost saving is \[d(p,H)-\min\{d(p,H),d(p,X)\} =\max\bigl(0,\max_{x\in X}\{d(p,H)-d(p,x)\}\bigr).\] The maximum of fixed offers has decreasing marginal gains and is monotone. If there are no red candidates the red term is zero. Otherwise choose a common \(C\ge\max_{s\text{ red}}w'_sd(s,Z)\), and write \[v_s(X)=C-w'_sd(s,Z\cup X) =\max\bigl(C-w'_sd(s,Z), \max_{x\in X}\{C-w'_sd(s,x)\}\bigr).\] The scores \(v_s(X)\) lie in \([0,C]\). The sum of the \(q=b_{\mathrm{red}}\) smallest red costs equals \(qC\) minus the sum \(V_q(X)\) of the \(q\) largest scores. If \(C=0\) or \(q=0\) this term is constant. Otherwise, counting scores above each level gives \[V_q(X)=\int_0^C\min\bigl(q,|\{s:v_s(X)\ge t\}|\bigr)\,dt.\] At a fixed level \(t\), each selected \(x\) covers a fixed set of red centers, in addition to a fixed baseline covered set. The marginal of adding \(x\) to its coverage count truncated at \(q\) is the minimum of the number of newly covered centers and the remaining capacity below \(q\). Both numbers can only decrease when the previously selected set grows. The integrand is therefore monotone and submodular, and so is its integral. The red saving is \(V_q(X)-V_q(\varnothing)\). Adding the base savings establishes the assertion. Identical offers from copies in different balls preserve this reasoning. ◻

Proof. For each feasible count branch, apply Lemma 14 to the function in Lemma 15, with error at most \(\theta-1/e\), and construct the corresponding \(U_X\). Keep the cheapest constructed solution, including \(S\) as a fallback. For the fixed branch under consideration, the gain guarantee and the feasibility of \(X^*\) imply \[ \mathbb E[\operatorname{cost}(U)] \le\mathbb E[\Psi(X)] \le\theta\Psi(\varnothing)+(1-\theta)\Psi(X^*). \tag{42}\] It remains to identify a suitable branch and bound this convex combination.

For each \(s\in R^*\), minimize the following mixed distance over all comparison destinations, resolving ties by a fixed rule: \[ M_s=\min\left\{ \begin{array}{ll} d(s,\phi_i),&i\text{ good},\\ (1-\theta)d(s,i)+\theta\bigl(d(s,w_i)+R_i\bigr),&i\in A,\\ d(s,i),&i\in B. \end{array}\right. \tag{43}\] Require \(s\) to be red for either of the first two destination types and blue for the third. Require every proxy used in the first type to be green. The requirements are consistent: \(R^*\subseteq S_0\) whereas all proxies lie outside \(S_0\). At most \(r\) removal centers and at most \(r\) proxy destinations receive specified colors, so the event has probability at least \(4^{-2m}\). All other proxies may have any color; if the optimization removes one of them, its displacement is paid by the surrogate just as for any other removed center.

Use the count branch equal to the sizes of these designated red and blue sets. If the designated blue count is \(b>0\), require their labels to be distinct. Its conditional probability is at least \[b!(2b)^{-b}\ge(2e)^{-b}.\] The inequality follows, for example, from \(\log(b!)\ge\int_1^b\log x\,dx=b\log b-b+1\). For \(b=0\) the event has probability one. The blue comparison assigns each designated blue removal to its chosen member of \(B\). Grouping equal destinations uses at most \(|B|=c\) blocks, so it is feasible for Equation (37) and the dynamic program. Consequently its \(K\) is at most the sum of designated blue charges \(w'_sM_s\). In particular the successful branch is never infeasible.

For the designated red subset, at \(X=\varnothing\) a proxy destination is green and a ball destination has its leaf in \(Z\). At \(X=X^*\) the corresponding true ball center is also available. At each of these two arguments, the optimized sum of smallest red costs is no greater than the sum over this same designated red subset. Therefore their convex combination, together with \(K\), is at most \[ \sum_{s\in R^*}w'_sM_s. \tag{44}\] The minimizing red subset need not be the same at the two arguments; the fixed designated subset is an admissible upper bound at both.

For \(p\in J_s\cap C_i\) offer its own cluster as a destination in Equation (43). In the good and uncovered cases, triangle inequality gives respectively \(M_s\le d(p,H)+d(p,\phi_i)\) and \(M_s\le d(p,H)+d_p^*\). In the covered case it gives \[\begin{split} M_s&\le(1-\theta)d(s,i)+\theta(d(s,w_i)+R_i)\\ &\le d(p,H)+(1-\theta)d_p^* +\theta(d_p^*+r_i+R_i) =d(p,H)+c_p. \end{split}\] Although \(M_s\) is chosen once for all clients of \(J_s\), it is no larger than every offered value. Summing therefore bounds Equation (44) by \(I+\sum_{p\in J}c_p\). The base terms of the convex combination contribute at most a further \(I\) on \(J\), and contribute exactly \(b_p\) on its complement. Together with Equation (42) this proves Equation (41).

For a good client \(d(p,H)\le d(p,\phi_i)\) since \(Q\subseteq S_0\). For a covered client, \(d(p,H)\le d_p^*+r_i+R_i\) and \(d(p,X^*)\le d_p^*\), yielding \(b_p\le c_p\). The bound for \(B\) follows from the definition of \(b_p\). All complexity statements follow from the \(r+1\) count branches, the subset dynamic program, and Lemma 14. The number of copied facilities is at most \(a|F|\le N^2\), and the surrogate can be evaluated using distance lookups and sorting. The color and label constructions use bounded numbers of fair bits. Combining their probabilities gives the claimed \(\exp(-O(m))\) event. ◻

Proof. If \(m=0\), the cost of \(S\) is at most the displayed proxy-assignment cost, hence at most \(1.01P\). The algorithm always retains \(S\) as a candidate. Suppose henceforth \(m>0\), and fix \(\kappa=10^{-6}\) and \(\theta=0.38\). Run the sampling procedure of Theorem 13 for at most \(2m\) steps, examining every prefix. Its successful prefix has the structure used in Theorem 16, and satisfies \[I\le\kappa P,\qquad T_i:=\sum_{p\in N_i}d(p,H),\quad \sum_{i\in B}T_i\le\kappa P, \qquad N_i=\{p\in C_i:d_p^*\le1.2\bar d_i\}.\] Here \(\bar d_i=P_i/n_i\) for \(n_i>0\); empty clusters contribute no clients and no terms with denominator \(n_i\). The same theorem gives \[ \begin{gathered} r_i\le1.2\bar d_i,\qquad R_i\le(1+\kappa)r_i+\kappa r^0(w_i),\qquad \sum_{i\in A}n_i r^0(w_i)\le5.2P,\\ d(p,H)\le1.85d_p^*+60T_i/n_i \quad(i\in B,\ p\in C_i\setminus N_i). \end{gathered} \tag{45}\]

Apply Theorem 16. Good clients, whether inside or outside \(J\), contribute at most their proxy-assignment cost. Covered bad clients contribute at most \[\sum_{i\in A}\left[P_i+ \theta n_i\bigl((2+\kappa)1.2\bar d_i+\kappa r^0(w_i)\bigr)\right].\] For a remaining bad cluster, clients in \(J\) cost at most \(d_p^*\); clients outside \(J\) and inside \(N_i\) contribute at most \(d(p,H)\), whose sum is bounded by \(T_i\); the other clients are bounded by the last line of Equation (45). Thus their total is at most \(1.85\sum_{i\in B}P_i+61\sum_{i\in B}T_i\). Including the two copies of \(I\) gives the conditional expectation \[\begin{split} \mathbb E[\operatorname{cost}(U)] &\le 2\kappa P+P_g+0.01P\\ &\quad+\sum_{i\in A}\left[P_i+ \theta n_i\bigl((2+\kappa)1.2\bar d_i+\kappa r^0(w_i)\bigr)\right] +1.85\sum_{i\in B}P_i+61\kappa P\\ &\le\left[1+0.38(2+10^{-6})1.2+0.01 +63\cdot10^{-6}+0.38\cdot5.2\cdot10^{-6}\right]P\\ &=1.922065432P<1.94P. \end{split}\] In the second inequality the covered-cluster coefficient \(1+0.38(2+\kappa)1.2=1.912000456\) bounds both the good coefficient \(1\) and the uncovered coefficient \(1.85\).

The output cost is nonnegative. Markov’s inequality therefore gives, conditional on the successful prefix and the color and label event, \[\Pr\{\operatorname{cost}(U)\le1.97P\} \ge 1-\frac{1.94}{1.97}=\frac3{197}.\] The sampling event has probability \(\exp(-O_\kappa(m))\) by Theorem 13; the completion event has probability \(\exp(-O(m))\). Their product with \(3/197\) is at least \(\exp(-C m)\) for an absolute constant \(C\) after enlarging \(C\), since \(\kappa\) is fixed and \(m\ge1\). These are conditional bounds for every successful prefix, so they combine without an independence assumption between its shape and the required colors.

The algorithm need not know the comparison solution, its partition, its proxies, or \(P\). It enumerates \(1\le m\le\min\{M_0,h\}\) and all integer cost guesses \(1\le P\le n\Delta\), where \(\Delta\) is the maximum original distance of the bounded integral instance. One guess equals the true \(P\). For each guess repeat the full sampling and completion experiment \(\lceil\exp(C M_0)\log(1/\zeta)\rceil\) times, taking the best feasible candidate over all prefixes and all guesses, including \(S\). The chance that every trial for the correct guess fails is at most \(\zeta\). The number of cost guesses is polynomial in \(N\), each sampling trial has polynomial work, and completion contributes only \(\exp(O(m))\operatorname{poly}(N)\). The stated running time follows. All branches, including incorrect guesses, discard prefixes with \(|Q|>m\) or more than \(m\) balls, empty facility balls, or impossible counts, and obey Equation (39); the fallback also has size \(h\). Consequently the budget holds on every outcome. The algorithm retains the minimum actual cost without testing any condition involving \(O\) or recognizing successful events. ◻

Proof. The proof specifies a guide inside the same blind sampling procedure. For every prescribed mode and eligible client set, the guide draws from the actual law conditioned on that event and uses the correct radius-menu entry specified in Lemma 9. At a state of its first stage, write \[T(H)=\sum_{i\in B}\sum_{p\in N_i^1}d(p,H),\qquad I(H)=\sum_{s\in S_0\setminus Q}\sum_{p\in J_s(H)}d(p,H).\] If \(T(H)>\kappa P\), the guide chooses a ball step whose sampled client belongs to \(N_i^1\) for some \(i\in B\). If \(T(H)\le\kappa P\) but \(I(H)>\kappa P\), it chooses a removal step whose sampled client is assigned to a member of \(S_0\setminus Q\). It stops this stage as soon as both inequalities hold in the other direction.

Here are the probability bounds needed to invoke the general guide lemma. Lemma 11 gives \(|N_i^1|\ge qn_i\) for every nonempty uncovered cluster, and hence \[ d(i,H)\le a_1\bar d_i+ \frac{\sum_{p\in N_i^1}d(p,H)}{qn_i}. \tag{51}\] Indeed, take a member of \(N_i^1\) of minimum distance to \(H\) and use the triangle inequality. Summing the resulting bound for all clients of an uncovered cluster gives \[\sum_{p\in C_i}d(p,H) \le(1+a_1)P_i+\frac1q\sum_{p\in N_i^1}d(p,H).\] Good clients have their proxies available. A client of a covered cluster can use its dummy at distance at most \(d_p^*+(2+\kappa)a_2\bar d_i+\kappa r^0(w_i)\). Since every leader used in either stage has \(r_i\le a_2\bar d_i\), Lemma 7 bounds the sum of the last radius terms by \((11/2)\kappa P\). Thus throughout the first stage the total sampling weight \(W(H)=\sum_{p\in D}d(p,H)\) satisfies the convenient bound \[ W(H)\le 6P+T(H)/q. \tag{52}\] For example, the coefficient of cluster cost before the additive proxy and radius errors is at most \(1+(2+\kappa)a_2\), and \(1+(2+\kappa)a_2+\mu+(11/2)\kappa<6\) for \(0<\mu\le1/4\).

The procedure samples proportionally to this weight and chooses its mode with probability \(1/2\). When \(T(H)>\kappa P\), the joint event prescribed by the guide has probability at least \[\frac{T(H)}{2(6P+T(H)/q)} \ge \rho_\mu:=\frac{\kappa}{2(6+\kappa/q)}>0.\] When only the removal condition fails, its joint event has the same lower bound by Equation (52). A zero total weight already satisfies both stopping conditions. At the first stop call the state \(H^0\) and use the notation of the statement; this proves Equation (48).

In the second stage the guide deletes no further original centers. The eligible centers are fixed using \(H^0\): they are precisely the nonempty \(i\in B^0\) with \(f_i<1/3\). While the final sum in Equation (49) exceeds \(\kappa P\), the guide adds a ball whose leader is in \(N_i^2\) for an eligible, still uncovered center \(i\). All reference distances can only decrease after \(H^0\), so \[W(H)\le W(H^0)\le(6+\kappa/q)P.\] The prescribed joint event therefore again has probability at least \(\rho_\mu\). Its termination gives the last inequality in Equation (49).

The reference set only grows during this stage, and the order between old choices is fixed. A client that was assigned outside the fixed set \(R^*\) cannot become assigned to it upon adding choices. Consequently \(J\subseteq J^0\), and monotonicity of distances gives the internal-cost bound in Equation (49).

Across both stages each step either deletes a fresh member of \(S_0\) or covers a fresh bad center. Thus there are at most \(2m\) steps in total. All leaves persist across the transition. Lemma 9 therefore applies once to the entire trajectory: its disjoint-ball amortization bounds the sum of costly radius-menu indices across both stages. Correct radii satisfy Equation (47), and Lemma 7 gives Equation (50) because \(a_1\le a_2=3/2\). The joint progress probabilities just proved and the global radius budget meet the hypotheses of Lemma 10. That lemma gives the claimed \(\exp(-O_\mu(m))\) probability. In particular, its guide may switch stages using the unobserved state \(H^0\): the actual procedure continues its ordinary sampling and mode choices and retains every prefix. ◻

Proof. For each cluster let \(C_i^{\mathrm{chg}}\) denote the sum of its \(c_p\) terms on \(J\) and its \(b_p\) terms outside \(J\). We account for these charges first, and then for \(2I\).

Proof of Theorem 1. The algorithm retains \(S\) as a feasible candidate. When \(m=0\), Equation (1) gives \(\operatorname{cost}(S)\le(1+\mu)P\), which suffices. For \(m>0\), first consider the branch with the correct guesses of \(P\) and \(m\). Lemma 18 produces a suitable prefix with probability at least \(\exp(-O_\mu(m))\). Completion is attempted at every prefix. Theorem 16 supplies the needed colors and labels with probability \(\exp(-O(m))\) and always respects the cardinality bound. Conditional on these choices, Lemma 19 gives \[\mathbb E[\operatorname{cost}(\widehat S)] \le(1+2/e+6\mu)P \le(1+2/e+\varepsilon/2)P.\] By nonnegativity of cost, Markov’s inequality therefore gives conditional probability at least \[1-\frac{1+2/e+\varepsilon/2}{1+2/e+\varepsilon} =\frac{\varepsilon}{2(1+2/e+\varepsilon)}>0\] of meeting the stated target. One full trial consequently succeeds with probability \(\exp(-O_{\mu,\varepsilon}(m))\).

If \(\Delta\) is the largest distance in the scaled input, then the unknown integer \(P\) belongs to \(\{1,\ldots,n\Delta\}\). Try all these values and all \(m\le\min\{h,\lfloor L_0\log N\rfloor\}\). The sampling menus are finite and have polynomial bit complexity by Lemmas 7 and 9; their single-exponential probability cost has already been accounted for over the whole trajectory. Each completion uses \(\exp(O(m))\operatorname{poly}(N)\) work for fixed \(\theta\), by Theorem 16. Repeating the trials \(\exp(O_{\mu,\varepsilon}(L_0\log N))\log(1/\zeta)\) times, with the constant enlarged if necessary, makes the failure probability at most \(\zeta\). All enumerations, repetitions, and prefix completions therefore take polynomial time for the fixed parameters. Take the cheapest feasible candidate; no successful guide, stopping state, coloring, or comparison solution needs to be identified. ◻

Proof. Fix the supplied valid sequences, price and copy lengths. This proof uses their validity. No facility deletion, change of price, or movement of a free copy during the construction’s search is used as a step of this history. Write \(\beta_j\) for a transient budget, reserving \(\alpha_j\) for its final value. Initialize \(Q=\varnothing\), \(z=1\), and \(\beta_j=1\) for all clients.

Proof. All optimum costs in the integral model are positive. Since \(\log(1+\xi)\ge\xi/2\) for \(0\le\xi\le1\) and \(\log(1+\beta)<\beta\), \[ (1+\beta)^{2L}<\exp(\xi/2)\le1+\xi. \tag{111}\] The product of the \(2L\) ratios \(\operatorname{opt}_{r-1}/\operatorname{opt}_r\), for \(k-2L<r\le k\), is greater than \(1+\xi\). Hence at least one ratio is at least \(1+\beta\). Choose the largest such index \(h'\). Every later ratio is less than \(1+\beta\), and their product is at most \((1+\beta)^{2L}<1+\xi\) (the empty product is one). This proves both inequalities in Equation (109).

We have \(h'\ge k-2L+1\ge2\). For \(i\in O\), reroute all its clients to a nearest other member of \(O\) and keep the remaining assignments. This constructs an \((h'-1)\)-center solution of cost at most \(P+n_i\operatorname{sep}_i\). The first inequality in Equation (109) gives \(P+n_i\operatorname{sep}_i\ge(1+\beta)P\), proving Equation (110). In particular no cluster of this optimum is empty. ◻

Proof. Compute a width-\(5\) local optimum \(S_k\) of size \(k\) and retain it as a candidate. Lemmas 4 and 5 give polynomial time and \(\operatorname{cost}(S_k)\le5\operatorname{opt}_k\). Every other retained candidate will also satisfy the budget, and we return the least-cost candidate.

If \(k\le2L\), apply Theorem 17 to \(S_k\) with the supplied count bound \(M_0=2L\) and failure parameter \(\zeta\). For its analysis, take an optimum of size \(k\) and declare every cluster bad. Then \(m=k\le M_0\), and the proxy condition is vacuous. Recovery gives cost at most \(1.97\operatorname{opt}_k\) with probability at least \(1-\zeta\). Since \(1.97\le2-\gamma\), this implies Equation (112), including the case \(k=1\).

Suppose now that \(k>2L\). Compute the candidate of Proposition 23 with target \(h=k-L\). In addition, for every integer \(h'\) with \(k-2L<h'\le k\), compute a width-\(5\) local optimum \(S_{h'}\) of size \(h'\) and apply Theorem 17 with \[ M_0=\left\lceil\frac{4C_0L}{\xi}\right\rceil, \qquad\text{failure parameter }\zeta. \tag{113}\] These calls require only the computed local sets, \(M_0\), and \(\zeta\). They enumerate their unknown comparison costs internally. All their feasible outputs have at most \(h'\le k\) centers.

If \(\operatorname{opt}_{k-2L}\le(1+\xi)\operatorname{opt}_k\), Proposition 23 gives cost at most \[(2-c/100)(1+\xi)\operatorname{opt}_k \le(2-\gamma)(1+\xi)\operatorname{opt}_k.\] This conclusion is deterministic.

Otherwise, let \(h'\) be supplied by Lemma 24, take an optimum \(O\) of size \(h'\), and put \(P=\operatorname{opt}_{h'}\), \(b=\beta P\). The local set \(S_{h'}\) has no surplus relative to \(O\). Equation (110) says that no center is short at scale \(b\), so the left side of the scale condition in Theorem 6 is zero. With tolerance \(1/100\), that theorem supplies distinct good proxies with total assignment cost at most \(P_g+P/100\), and \[m\le C_0P/b=C_0/\beta=4C_0L/\xi\le M_0.\] The recovery call at this particular \(h'\) therefore has, with probability at least \(1-\zeta\), cost at most \[1.97P\le1.97(1+\xi)\operatorname{opt}_k \le(2-\gamma)(1+\xi)\operatorname{opt}_k.\] The algorithm need not recognize this index or its success event: its returned minimum is no worse than this candidate. Only this one call must succeed, so there is no union-bound loss over the other indices.

Both supplied count bounds are \(O(\log(N+2))\). There are at most \(N\) cardinality choices; the local searches and the surplus construction are polynomial, and the recovery calls have polynomial time by Theorem 17. Keeping \(S_k\) proves the unconditional factor-five bound. ◻

Proof of Theorem 2. Handle the elementary cases and zero optimum as in Section 2. Apply Lemma 3 with the fixed \(\varepsilon_0=\gamma/16\) and the algorithm of Proposition 25. The successful approximation factor on the original rational metric is at most \[(2-\gamma)(1+\xi)(1+\varepsilon_0) =(2-\gamma)(1+\gamma/16)^2 \le2-\gamma/2.\] For the last inequality, expand the product: \[(2-\gamma)(1+\gamma/16)^2 =2-\frac34\gamma-\frac{15}{128}\gamma^2 -\frac1{256}\gamma^3 \le2-\gamma/2.\] The transferred unconditional bound is \(5(1+\varepsilon_0)\operatorname{opt}_k<6\operatorname{opt}_k\).

For the prescribed fixed \(a>0\), choose a rational failure parameter \[0<\zeta\le\min\{(N+2)^{-\lceil a\rceil},\gamma/24\}.\] It has polynomial bit length and \(\log(2/\zeta)=O_a(\log(N+2))\) with fixed constants. The least original-cost candidate over all rounding guesses is no worse than the candidate for the correct guess. Hence its probability of exceeding \((2-\gamma/2)\operatorname{opt}_k\) is at most \(\zeta\le(N+2)^{-a}\). Since \(\sigma=\gamma/4\), this proves the asserted probability bound. Finally, split expectation according to that successful event and use the unconditional cost bound: \[\mathbb E\operatorname{cost}(S) \le (2-\gamma/2)\operatorname{opt}_k +6\zeta\operatorname{opt}_k \le(2-\gamma/4)\operatorname{opt}_k =(2-\sigma)\operatorname{opt}_k.\] Every candidate is a real facility set of size at most \(k\). All enumerations and arithmetic have polynomial bit complexity, as established in the reduction, sampling, and completion proofs. This completes the theorem. ◻