Single-exponential recovery and bounded-price strictness for metric k-median

Proof. Detect zero optimum first. It occurs exactly when every client location contains an available facility and the number of distinct client locations is at most k. More generally, if repeated indexed points are initially represented by zero distances, use their zero-distance equivalence classes for this test. Opening one facility in each relevant class gives cost zero.

Suppose the optimum cost P^* is positive. Guess a positive client–facility distance M from the input; there are at most n|F| possibilities. For the correct guess, M is the largest assigned distance in some fixed optimum, so

Set

Separate client and facility copies when a point serves both roles. For distinct indexed points x,y set

This is a metric. Indeed, ceiling is monotone and subadditive on nonnegative arguments; enforcing the lower bound one on distinct points and applying a common cap preserve the triangle inequality. For a triangle with repeated indices the assertion is immediate. For three distinct indices it follows by applying these two monotone, subadditive operations to the original triangle inequality. These observations also cover distinct copies whose original distance is zero.

The original optimum, evaluated in d_M, has cost at most P^*/u+n. Thus for the correct guess the new optimum Q^* satisfies

The assumed algorithm’s output has rounded cost at most 5Q^*<C. Choose nearest rounded assignments for that output. None of their edges has rounded length C, because the whole sum is smaller than C. On every selected edge, therefore, d(x,y)\le u\,d_M(x,y). The original nearest-assignment cost is no larger than that of these assignments. The output consequently has original cost at most

using Equation (2.2). On the successful event the same argument replaces 5 by A.

Run the algorithm for every positive guess and return the feasible output with the least original cost. It is at least as good as the output of the correct guess, so no union bound over guesses is needed. All sets returned respect the budget. Sorting distances, taking ceilings, and constructing the rounded matrices require polynomial-bit rational arithmetic. The number of guesses is polynomial, and the rounded distance bound is a fixed polynomial for fixed \varepsilon_0.□

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

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 3.1’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

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

The weighted sum of these upper bounds for p is therefore at most

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

This is (3.1). Since u\ge1, it implies (3.2). Declaring every center bad gives the final assertion.□

Proof. Set

The all-bad case of Lemma 3.2 gives

Call a center short if n_i\operatorname{sep}_i<b. In particular, every empty comparison cluster is short.

Selecting a threshold. Let t_a=(\mu/100)2^{-a} for 0\le a<J_\mu. At threshold t_a, declare i good precisely when it is not short and V_i\le t_ab, and let m_a be the resulting number of bad centers. For a fixed nonshort center i, the geometric tail of those values t_ab that are strictly less than V_i has sum at most 2V_i. Consequently,

The first term accounts for short centers and surplus facilities at every threshold; the second accounts for all other bad centers. Since J_\mu\ge40/\mu and \mu\le1, the average of the left-hand summands is at most

Choose a threshold t=t_a attaining at most this average, and use its good/bad partition. Thus

Every nonshort bad center has V_i>tb. By (3.3) and (3.6),

This proves the count bound.

Proxy geometry and the number of crowded balls. For each good i, choose a nearest facility \phi_i\in S to i, and write r_i=d(i,\phi_i). Such a center has n_i>0. For every p\in C_i, nearest choice and the triangle inequality give r_i\le d(i,s(p))\le d_p^*+s_p. Hence

Consider the open balls in the ambient metric

They contain their respective proxies. They are pairwise disjoint: for distinct i,j\in O, both separations are at most d(i,j), so the sum of the ball radii is at most d(i,j)/2; membership in both balls would contradict the triangle inequality. In particular the proxies are distinct.

There are h-m good balls and |S|=h+\ell local facilities. Every good ball contains at least one local facility. Because the balls are disjoint, the number of them containing at least two local facilities is at most

Call these balls crowded. All other good balls contain exactly their one proxy as a local facility.

Charging the assignment excess. We upper-bound the sum of d(p,\phi_i)-d_p^* over all good clusters using three contributions. Individual excesses may be negative; only their total upper bound is needed.

First, for a good center with a crowded ball, the triangle inequality and (3.9) give

The total contribution from crowded balls is therefore at most tb(m+\ell).

Second, suppose B_i contains exactly one local facility and p\in C_i is assigned in S to a facility other than \phi_i. That facility lies outside B_i, including possibly on its boundary, and therefore

The excess of this client is at most

Summing over these clients gives a total at most 4t\sum_iV_i.

Third, consider the remaining clients of the singleton balls, namely those assigned to their own proxy. For such a good center i, put

We claim that

If i=\phi_i, the left side is zero. Otherwise i\notin S, since a nearest facility to a facility already in S is that facility itself. Exchange \phi_i for i. Send all clients previously assigned to \phi_i to i and keep all other assignments. Clients in A_i have change d_p^*-s_p; each incoming client in I_i has change at most r_i. Local optimality implies 0\le\sum_{p\in A_i}(d_p^*-s_p)+r_i|I_i|, proving (3.10). This also explains why overlap between O and S creates no exception to the argument.

For p\in I_i, let j\ne i be its assigned comparison center. The path from i to j through \phi_i and p gives

Together with (3.9), this bounds its incoming charge by

The proxies are distinct and the local assignment is fixed. Thus a client is incoming at at most one charged proxy, and summing (3.10) gives a total at most \frac{t}{1-t}\sum_iV_i for the third contribution.

Combining the three contributions proves

Since t\le1/100<1/2, the last parenthesis is at most 36t\le(9/25)\mu<\mu/2. This proves D_g\le P_g+\mu P and finishes the proof. Empty comparison clusters were counted among the bad centers throughout and never required division by n_i.□

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 (4.4), 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 (4.3). 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

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

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 4.1 gives |\mathcal D(w,q)|\ge P/(mq). Disjointness now implies

Cancel P>0 to obtain the first bound in Equation (4.8). For every third-menu entry,

There are at most m additions, so the second bound follows. In particular,

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

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 (4.8) prove Equation (4.9). 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 4.3 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 (4.10) 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 (4.10) 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 (4.11).

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 (4.12). For p\notin N_i, one has d_p^*>1.2\bar d_i, so

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

Use Equation (4.7), r_i\le1.2\bar d_i, and Lemma 4.1 to obtain, with P_A=\sum_{i\in A}P_i,

For an uncovered nonempty cluster, retain its near-client cost T_i and sum Equation (4.12) 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

Here P_g+P_A+P_B=P.

If T=T_{\rm near}(H)>\kappa P, the ball event has probability

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

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 (4.14), 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 4.6 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 4.4 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 4.1 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

Every integrand is between zero and M_1. For a fixed feasible maximizer O_g, monotonicity and submodularity give, for every R_x,

The last inequality also holds when e\in R_x, since its left summand is then zero. Thus

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 (5.1), 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

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

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 (5.1) 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,

Iterating from G(0)=0 yields

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

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 (5.5), 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

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,

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

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

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

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 5.1 to the function in Lemma 5.2, 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

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:

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

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 (5.4) 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

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 (5.10). 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

Although M_s is chosen once for all clients of J_s, it is no larger than every offered value. Summing therefore bounds Equation (5.11) 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 (5.9) this proves Equation (5.8).

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 5.1. 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 4.7 for at most 2m steps, examining every prefix. Its successful prefix has the structure used in Theorem 5.3, and satisfies

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

Apply Theorem 5.3. Good clients, whether inside or outside J, contribute at most their proxy-assignment cost. Covered bad clients contribute at most

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 (5.12). 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

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,

The sampling event has probability \exp(-O_\kappa(m)) by Theorem 4.7; 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 (5.6); 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 4.3. At a state of its first stage, write

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 4.5 gives |N_i^1|\ge qn_i for every nonempty uncovered cluster, and hence

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

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 4.1 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

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

When only the removal condition fails, its joint event has the same lower bound by Equation (6.7). 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 (6.3).

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 (6.4) 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

The prescribed joint event therefore again has probability at least \rho_\mu. Its termination gives the last inequality in Equation (6.4).

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 (6.4).

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 4.3 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 (6.2), and Lemma 4.1 gives Equation (6.5) because a_1\le a_2=3/2. The joint progress probabilities just proved and the global radius budget meet the hypotheses of Lemma 4.4. 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.

Good clusters. Their proxies remain in H, so b_p\le d(p,H)\le d(p,\phi_i). Together with the definition of c_p, their total charge is at most P_g+\mu P.

Clusters covered in the first stage. For i\in A^1, the comparison choice X^* offers center i, and its dummy gives d(p,H)\le d_p^*+r_i+R_i. Thus both types of client charge are at most d_p^*+\theta(r_i+R_i). Since r_i\le a_1\bar d_i,

Clusters covered in the second stage. For a nonempty i\in A^2, put x_i=|C_i\cap J|/n_i\le f_i<1/3. On J use the ball charge with r_i\le a_2\bar d_i. Outside J, use the center i offered by X^* and the first-stage estimate in Equation (6.6) at H^0:

It follows that

For the last inequality, 2a_2-a_1=2-\mu>0 and

In particular this coefficient estimate uses the fraction at the first stop and the inclusion J\subseteq J^0.

Remaining clusters with f_i\ge1/3. Clients in J have charge d_p^*. Clients in J^0\setminus J have b_p\le d(p,H)\le d(p,H^0). For the at most (2/3)n_i clients outside J^0, use b_p\le d(p,H)\le d_p^*+a_1\bar d_i+T_i/(qn_i). Consequently

The sum of E_i^+ over this group of clusters is at most \kappa P by Equation (6.3).

Remaining clusters with f_i<1/3. Again clients in J have charge d_p^*. For clients outside J that lie in N_i^2, retain the base bound b_p\le d(p,H). Every other client outside J has d_p^*>a_2\bar d_i, whence

Thus

The sum of E_i^- over these remaining eligible clusters is at most \kappa P by Equation (6.4). Empty clusters have zero charge and require none of the divisions above.

Summing the errors once. The main coefficient for every bad cluster is bounded by 1+2\theta a_1: this follows from a_1\ge1 and \theta>1/e>1/3. The T_i/q terms in Equations (6.11), (6.13), and (6.14) concern disjoint subsets of B^0. Their total is therefore at most \kappa P/q. The radius errors from Equations (6.10) and (6.11) together are at most

Here a_1\le a_2=3/2, x_i\le1, and Equation (6.5) are used globally. The two negligible base-cost sums contribute at most 2\kappa P, and 2I\le2\kappa P. Along with the proxy error, these bounds establish the bound by the first expression in Equation (6.9).

Finally, Equation (6.1) implies

For the last step, \mu\le1/4 gives 3\mu^2+12\mu^3\le(3/2)\mu, and 3+2/e+3/2<6. In particular the cumulative sampling and radius errors are O(\kappa+\kappa/q)P=O(\mu^2)P; the linear error comes from the proxies, a_1-1, and \theta-1/e.□

Proof of Theorem 1.1. The algorithm retains S as a feasible candidate. When m=0, Equation (1.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 6.1 produces a suitable prefix with probability at least \exp(-O_\mu(m)). Completion is attempted at every prefix. Theorem 5.3 supplies the needed colors and labels with probability \exp(-O(m)) and always respects the cardinality bound. Conditional on these choices, Lemma 6.2 gives

By nonnegativity of cost, Markov’s inequality therefore gives conditional probability at least

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 4.1 and 4.3; 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 5.3. 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.

Witness sets and actual updates. At a regular opening with witness W\supseteq Q, one has A_W\subseteq A_Q and I_Q\subseteq I_W. Use the certified bid \tau_j for j\in A_W and the unchanged bid z for j\in A_Q\setminus A_W. Budgets of already inactive clients stay fixed. Every actual active client whose budget increases lies within vz of the newly opened regular facility. It therefore immediately becomes inactive, since

Consequently every client remaining active has its old budget z. At a free opening no budgets increase and the same conclusion holds. At a phase update, with old value z, each active budget becomes

clients reaching the second value become inactive, and all others have budget Kz, the next phase value. This proves inductively both the common active budget and the identity A=A_Q at every atomic boundary. It gives the strict form of (7.5) whenever the right side is finite.

When a regular opening inactivates a client, its final bid is at most Kz_p and at least its new scaled connection distance. Inactivation during a free opening has final bid exactly z_p. At inactivation during a phase update, the final bid equals the scaled connection distance and is at most Kz_p. In every case the bid is frozen after removal from the active set. This proves (7.6)–(7.7), using the old phase value also for a phase-update removal. Since Q only grows in the fixed metric extension, later connection distances cannot increase. Several removals in one atomic step all use the same pre-step value and pre-step set; an ordering of tied clients does not insert fictitious intermediate states.

No overbidding at actual atomic boundaries. We include the invariant argument corresponding to Claim 10, Equation (33), in Appendix A.2 of [9]. At a boundary set c_j=(1-\delta)d(j,Q) and define

Initially B_i=0 because all client–facility distances are at least one. An opening cannot increase any client’s term. Old inactive clients have smaller or unchanged c_j; an active client that stays active keeps z; and an active client that becomes inactive has new c_j\le z. The latter assertion holds even if its bid increased, because an increased bid is possible only within vz of the opening facility. A free opening has the same monotonicity without bid increases. This proves preservation at opening steps, including openings witnessed by supersets.

Consider a phase update after a maximal phase sequence. For its old active set put b_j(t)=\min\{t,c_j\} for z\le t\le Kz, and define

At t=Kz this is precisely the invariant after the simultaneous update, including newly inactive clients. If some B_i(Kz)>\lambda, continuity gives a first t_*\in[z,Kz] at which some such facility i has B_i(t_*)=\lambda; choose the first crossing among all regular facilities. Then B_{i_0}(t_*)\le\lambda for every i_0\in F. Such an i is unopened, since a facility in Q has B_i(t)=0 for all these t.

Offer \tau_j=b_j(t_*) for d(i,j)\le vz and \tau_j=z otherwise. These bids satisfy the two update restrictions. For an outside client, \delta d(i,j)\ge3v^2z\ge v^2z, so

For a nearby client this comparison holds immediately with z replaced by b_j(t_*). Also [c_j-(1-\delta)d(i,j)]^+\ge[c_j-d(i,j)]^+ for an inactive client. Thus these bids pay at least B_i(t_*)=\lambda. Finally, for every a\in A, j\in I, and i_0\in F, the triangle inequality and \tau_a\le c_a give

Since \tau_j\le b_j(t_*) for active j, the left side of (7.4) is at most B_{i_0}(t_*)\le\lambda. Hence i is 0-openable against the actual set Q, contradicting maximality. This proves the invariant through phase updates and establishes (7.8) at precisely the required states.

Payment with witness supersets. The certificate’s payment can be checked directly by a potential argument; this is the accounting in Lemma A.1 and Equation (32) of [9]. First compare a regular opening’s witness payments with its actual payments. For j\in A_Q\setminus A_W we have z\ge(1-\delta)d(j,W), whence

For j\in I_Q, replacing W by Q\subseteq W only increases the available saving. Clients in A_W keep their certified bids. Therefore (7.3) remains valid against the actual prefix with the extended actual bids.

Let r_Q count regular facilities opened in the actual prefix. At every boundary consider

Initially it is zero. At a regular opening, already inactive clients contribute their nonnegative connection savings. For an old active client a positive contribution [\tau_j-(1-\delta)d(i,j)]^+ makes it inactive, and its new slack \tau_j-(1-\delta)d(j,Q\cup\{i\}) is at least that contribution. The total increase before the paid-facility term is therefore at least \lambda-n\eta. At a free opening, old inactive slacks can only increase and new inactive slacks are nonnegative. At a phase update, the new inactive clients have zero slack, while the old terms and r_Q are unchanged. Thus \mathcal P\ge0 always. At termination, writing V for the final virtual facilities and r for its regular count, this gives

The final dual on this replay. We prove (7.9) for the budgets just constructed. The source defines this execution in Section 3.4 and immediately before Appendix A.1. Its final-dual statement is Lemma A.2, used to prove Theorem 3.10. Our argument follows Lemmas A.2–A.3 and Equations (34)–(38) of [9, Appendix A.2], whose regular-opening argument already handles witness supersets. We give the rows explicitly, including the case where the first facility that freezes the comparison facility is free. That case needs the no-overbidding invariant in place of an opening-dual condition.

Fix i\in F, write d_j=d(i,j), and put

There is nothing to prove if m=0. Order D^* by removal step, breaking ties by nondecreasing final budget \alpha_j, and then arbitrarily between equal budgets. Write j\prec k and j\succeq k for this order. This auxiliary order is specific to the present dual proof; it imposes no restriction on the arbitrary order of simultaneous removals allowed in the later strictness argument. In particular it does not create intermediate states within an atomic step.

An opening of h at phase value z freezes i if d(i,h)\le(1+3v)z/2. We use only the first such opening, if there is one. We first establish the following row for each contributor k removed strictly before that opening, or for every k\in D^* if no opening freezes i:

The elementary comparison used below is that, for a nonempty actual prefix Q, c_j=(1-\delta)d(j,Q), and u\le c_k,

Indeed, d(k,Q)\le d_k+d_j+d(j,Q), and multiplication by 1-\delta\le1 proves the assertion. When Q=\varnothing there are no inactive clients, so none of the applications to inactive clients below is needed.

Suppose first that k is removed by opening h at phase value z, before i is frozen. No contributor can have its budget increased by this opening: such an increase would require d(h,j)\le vz, whereas

contradicting j\in D^*. Thus \alpha_k=z. Apply no overbidding at the actual boundary immediately before the opening. Every j\succeq k is then active, so its term is exactly [\alpha_k-d_j]^+. A j\prec k removed in the same opening is also still active at this boundary, and its term [z-d_j]^+ dominates [\alpha_k-2d_j-d_k]^+. Any remaining j\prec k is already inactive; actual activity of k gives \alpha_k=z<c_k, so (7.15) gives the required domination for j. Discarding noncontributors proves (7.14).

Suppose instead that a simultaneous phase update removes k, with old phase value z. Use the no-overbidding invariant at the actual post-update boundary. The set Q is unchanged and \alpha_k=c_k\le Kz. Clients still active have budget Kz, which dominates the budget appearing in either term of (7.14). For an inactive j\prec k, use (7.15). An inactive j\succeq k must have been removed in this same update. Therefore c_j=\alpha_j\ge\alpha_k, where the last inequality is precisely the reason for the final-budget tie rule. Its invariant term dominates [\alpha_k-d_j]^+. This proves (7.14) also for phase-update removals.

If no opening freezes i, sum (7.14) over all k\in D^*. Replace each positive part by its argument. Each budget has coefficient m. If j has rank q, its distance occurs with coefficient q+2(m-q)+(q-1)=2m-1. Hence

which implies \sum_{j\in D^*}(\alpha_j-2d_j)\le\lambda.

It remains to consider a first freezing opening h at phase value z. Let Q,A,I be the actual state immediately before it, and let b_j be the extended actual bid used at this opening: certified bids for witness-active clients and z for the other active clients if h is regular, and b_j=z for all j\in A if h is free. Every j\in A\cap D^* is removed at this opening and has \alpha_j=b_j. To see this, suppose that j remains active. Then z\le b_j<(1-\delta)d(j,h). Every later actual prefix, and thus every later witness, contains h. Phase updates and certified bid updates are consequently capped by (1-\delta)d(j,h); unchanged active bids also satisfy this bound. It follows that \alpha_j\le(1-\delta)d(j,h). But

a contradiction. This argument applies to free and regular openings and uses only containment of the actual prefix in future witnesses.

Write R=I\cap D^*. These contributors precede the freezing opening, so they retain all rows (7.14). If h is regular, let W\supseteq Q be its witness and set

For j\in P the certified bid equals \alpha_j, whereas for j\in T the unchanged actual bid gives \alpha_j=z. Restricting (7.4) to contributors gives, for every k\in P,

For each k\in T, apply actual no overbidding immediately before the opening. The active budget is z=\alpha_k, and k is actually active, so \alpha_k<c_k. Using (7.15) for inactive clients gives

Thus actual-active but witness-inactive contributors use the actual invariant, without assuming that the two active sets coincide.

If h is free, set P=\varnothing and T=A\cap D^*. The preceding freezing argument shows that every k\in T is removed by this free opening with \alpha_k=z. The same actual pre-opening invariant and (7.15) prove (7.17) for each such k. No witness or opening-dual condition is needed for the free opening. This supplies the free first-freezing case omitted by the invocation of an opening-dual condition in the cited proof.

In either case put r=|R|, p=|P|, and t=|T|, so m=r+p+t. Sum (7.14) for k\in R, (7.16) for k\in P, and (7.17) for k\in T, replacing every positive part by its argument. Each budget has coefficient m: for R and T it occurs m times in its own row, and for P it occurs in the first sum of each of the p rows indexed by P and m-p times in its own second sum. The distance coefficients are

Consequently

Every displayed distance coefficient is at most 2m; subtracting the remaining nonnegative distance terms and dividing by m proves

This is (7.9) for the same final budgets used in the payment argument. It also holds for each free copy by distance domination, although only i\in F is needed here.

Projection and cardinality. Project each free copy of i to i and discard duplicate locations, giving U\subseteq F. For every client, d(j,U)\le d(j,V), so projection can only decrease cost. In the normal branch r=h before projection and |U|\le h+L; substituting into (7.13) and using n\le N proves (7.10). Coincident projected locations do not reduce the number h of paid regular facilities in that inequality. In the unmerged branch there are no free copies, r=|U|\le h, and \eta=0, giving (7.11). Finally assign every client to its nearest facility of a nonempty H. For each i\in H, the elementary bound

and (7.9) give (7.12) upon summation. All statements therefore use one and the same history and budgets.□

Proof. We first turn the replay inequalities into a scalar suffix inequality. After normalizing the cluster cost, two lower bounds on its slack rule out a small total deficit: a tail index would force a large suffix maximum, while an early interval would then carry too much slack. The last step transfers the resulting gap to final budgets.

Client-removal order and a suffix inequality. Index the q=|C| clients as 1,\ldots,q by their removal step in the fixed replay, breaking ties within an atomic step arbitrarily. This order is used only for the present suffix proof; the final-dual proof in Section 7 sorts tied removals by final budget. For client p, let Q_p^- denote the opened set immediately before its removal step, and let z_p be the phase value at that pre-step state. Thus clients removed in one atomic step have the same Q_p^- and z_p. Set

The imported history properties are

where Q_p^+ is the immediately post-step opened set, together with nonincreasing distances after that step. The pre-step no-overbidding inequality at i is

All sums in Equation (8.5) initially range over D.

For j<p define

For fixed j, this quantity is nonincreasing as p>j advances. Indeed it is constant within the removal step of j; at the first subsequent step, Equation (8.4) gives t\,d(j,Q_p^-)/K\le z_j; and thereafter the opened set only grows. This explains why the value for a tied removal is z_p, even though the scaled variable used elsewhere is a_p.

If j is already inactive, the triangle inequality in the fixed metric extension and Equation (8.4) give

For a tied removal the same conclusion follows from r_{jp}=z_p\ge a_p. Consequently, with

monotonicity implies, for every j<p and s\ge p,

The contribution of j<p in Equation (8.5) is at least [r_{jp}-d_j]_+: this is immediate for a tied removal, and follows from K\ge1 for an inactive client. Each j\ge p is active in the pre-step state of p, including all tied removals, and contributes at least [a_p-d_j]_+. Dropping clients outside C therefore proves

Two slack bounds and their exact sum. Divide all costs, phases, and budgets by P_C, retaining their notation. Now \sum_jd_j=1 and \lambda\le T. Write D_{p-1}=\sum_{j<p}d_j and define

Expanding [x]_+=x+[-x]_+ in Equation (8.6) yields

Alternatively, first replace A_p in Equation (8.6) by its lower bound a_p-d_p, and then expand. This gives

In the sum of D_{p-1}+(p-1)d_p over p, the coefficient of d_j is (q-j)+(j-1)=q-1. Thus the following identity is exact:

A small deficit would concentrate neither distance nor slack. For a contradiction suppose

Equations (8.9) and (8.11) imply

The function F(x)=\sum_j[d_j-x]_+ is convex and nonincreasing. Since Equation (8.11) also gives \sum_pa_p\le\lambda+2-1/q<B, Jensen’s inequality and Equation (8.10) imply

For every index set J with |J|\le2\rho q, it follows that

Finding a tail index with both required bounds. Equation (8.13) shows that fewer than cq/B indices have d_j>2B/q, because each such index contributes more than B/q to F(B/q). Equation (8.12) shows that fewer than 10cq indices have E_j>1/10. Put r=\lfloor\rho q\rfloor. The tail of exactly r indices is larger than the union of these two exceptional sets: indeed

For the last strict inequality, B>2 and \rho<1/400 give (11+1/B)c<12\rho^2/100<\rho. Hence some s\in\{q-r+1,\ldots,q\} satisfies

The suffix starting at s has at most r\le\rho q indices, so Equation (8.14) gives D_{s-1}>49/50. Also (q-s+1)d_s\le r(2B/q)\le2\rho B=1/100. Rearranging Equation (8.7) therefore yields

An early interval forces too much slack. Consider the integer interval

For p\in I, the prefix of length p-1 has at most 2\rho q indices. Using E_p,d_p\ge0 and Equation (8.14) gives

Every p\in I precedes s: indeed p\le2\rho q<(1-\rho)q+1\le q-r+1\le s. Thus A_p\ge a_s-d_s, and Equations (8.9), (8.16), and (8.17) imply

To check the integer rounding, set x=\rho q>4. Then

Consequently

contradicting Equation (8.12). We have proved \sum_pa_p\le\lambda+2-c.

Returning to the final budgets. By Equation (8.4), \alpha_p\le K^2a_p. As v\le1, K^2-1=2v^2+v^4\le3v^2, whence

by Equation (8.2). Multiplication by P_C proves Equation (8.3).□

Proof. Since L\ge1 and k>2L, we have h\ge2 and h-L=k-2L\ge1. Apply Theorem 7.1 at target h, then replay its output using Lemma 7.2 to obtain the real set U and its compatible budgets. In either output branch, |U|\le h+L=k. Pad U to size k using members of F, and run width-5 local search starting there; call its output S. Padding is possible because k\le|F|, and

This is polynomial time on the bounded integral metric, as in Lemma 3.1. Fix an optimum O of size h, padding if necessary, and write P=\operatorname{opt}_h>0, C_i=\{p:p\text{ is assigned to }i\in O\}, n_i=|C_i|, and P_i=\sum_{p\in C_i}d(i,p).

The unmerged small-price branch. Suppose the output is the unmerged solution at \lambda=2/N^2, with at most h facilities. Its payment guarantee is

Every nonempty cluster has P_i\ge1 in the positive integral metric, so \lambda\le2\le TP_i. Apply Lemma 8.1 to all nonempty clusters. Empty clusters contribute no budgets. There are at most h nonempty clusters, and therefore

Here h\lambda\le2/N\le c/200\le(c/200)P, because h\le N and P\ge1. Finally

It follows that \operatorname{cost}(U)\le(2-c/100)P, and Equation (9.5) proves the desired conclusion in this branch. This argument uses only the payment bound with its opening term dropped and the strictness just proved.

Dual comparison with an arbitrary real solution. It remains to consider the normal branch, whose replay has exactly h paid regular facilities. Put e=hN\eta, where \eta=2^{-N}. Equation (9.2) ensures e\le v\le vP. The payment and dual inequalities of Lemma 7.2 are

For any nonempty real set H\subseteq F, assign clients to nearest centers of H. For its cluster at i, the inequality \alpha_p\le2d(i,p)+[\alpha_p-2d(i,p)]_+ gives, upon summing,

Combining Equations (9.6) and (9.7) and dropping the nonnegative connection term gives

Use for H an optimum with h-L=k-2L centers. Equation (9.3) and monotonicity of the optimum imply \operatorname{cost}(H)\le(1+\xi)\operatorname{opt}_k\le(1+\xi)P, and hence

Short clusters and simultaneous removals. Set b=\lambda/8, and for i\in O let \operatorname{sep}_i=\min_{j\in O\setminus\{i\}}d(i,j). Call i short if n_i\operatorname{sep}_i<b; let N_{\rm short} be the number of short centers. Fix a nearest other center \nu(i) for every i\in O. Color all centers independently with two colors, and select the short centers of the first color whose designated neighbor \nu(i) has the second color. Each short center is selected with probability 1/4, so some coloring gives a set R with

For every i\in R, \nu(i)\notin R. Thus O\setminus R is nonempty, and all clients of C_i can be rerouted to \nu(i) with total increase at most n_i\operatorname{sep}_i<b. Keeping all other assignments proves

Empty clusters cause no difficulty: their rerouting increase is zero. Apply Equation (9.8) to H=O\setminus R:

As 2b=\lambda/4, we obtain

Equations (9.9) and (9.10) now show explicitly that

For the last inequality use \xi\le1, e\le vP, and v\le1/12. Since |S|-h=L, Equation (9.11) is precisely the scale hypothesis of Theorem 3.3 with tolerance 1/100.

The bad-cluster count and cost dichotomy. Apply Theorem 3.3 to S,O,b. We obtain distinct proxies in S for the good centers, with total proxy assignment cost at most P_g+P/100, and m bad centers satisfying

Write P_b=\sum_{i\text{ bad}}P_i and P_g=P-P_b. If P_b\le P/10, Lemma 3.2, with u=6/5, gives

where c<1 follows from Equation (8.1).

Otherwise P_b>P/10. Let

For every bad center excluded from \mathcal B_T, P_i<\lambda/T. Equation (9.12) and T=200C_0 therefore imply

Every member of \mathcal B_T has a nonempty positive-cost cluster, so Lemma 8.1 applies there. For each of the other centers, the cluster version of Equation (9.7) gives \sum_{p\in C_i}\alpha_p\le\lambda+2P_i, including empty clusters. Summing over all h centers of O proves

The full h\lambda in Equation (9.13) cancels the full h\lambda in Equation (9.6), giving

To divide by 1-\delta, note that

Thus \operatorname{cost}(U)\le(2-c/100)P, and Equation (9.5) proves the first inequality in Equation (9.4). Finally P=\operatorname{opt}_h\le\operatorname{opt}_{h-L} \le(1+\xi)\operatorname{opt}_k proves its second inequality. All choices made by the algorithm were the imported construction, padding, and local search; O, the coloring, and the good/bad partition are used only in the proof.□

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,

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 (10.2).

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 (10.2) gives P+n_i\operatorname{sep}_i\ge(1+\beta)P, proving Equation (10.3). 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 3.1 and 3.2 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 5.4 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 (10.5), including the case k=1.

Suppose now that k>2L. Compute the candidate of Proposition 9.1 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 5.4 with

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 9.1 gives cost at most

This conclusion is deterministic.

Otherwise, let h' be supplied by Lemma 10.1, 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 (10.3) says that no center is short at scale b, so the left side of the scale condition in Theorem 3.3 is zero. With tolerance 1/100, that theorem supplies distinct good proxies with total assignment cost at most P_g+P/100, and

The recovery call at this particular h' therefore has, with probability at least 1-\zeta, cost at most

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 5.4. Keeping S_k proves the unconditional factor-five bound.□

Proof of Theorem 1.2. Handle the elementary cases and zero optimum as in Section 2. Apply Lemma 2.1 with the fixed \varepsilon_0=\gamma/16 and the algorithm of Proposition 10.2. The successful approximation factor on the original rational metric is at most

For the last inequality, expand the product:

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

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:

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.□