betaFeedback

WorksComputer Science

Exact-Quota Facility Location: A Transfer Framework and Three Approximation Guarantees

Abstract

Facility location with outliers asks which facilities to open and which clients to serve, subject to a prescribed service quota. We give a framework for transferring facility-location cost certificates to this exact-quota setting. The framework yields deterministic polynomial-time approximation guarantees of 571/376<1.52571/376<1.52 for metric facility location with outliers, strictly less than 1.8531.853 for priority facility location with outliers, and 2.16995<2.172.16995<2.17 for squared-metric facility location with outliers. Each algorithm serves the prescribed number of clients and pays the original facility-opening costs. The framework separates initialization from improvement. A growth process is stopped when it first reaches the quota; deleting excess clients from its last batch leaves a payment deficit supported on a bounded number of facilities. Greedy additions then reoptimize the served client set. A threshold-coverage representation makes the resulting service cost supermodular and allows the usual density analysis to compare different client sets. Finally, enumerating and prepaying a constant number of expensive facilities absorbs the exceptional costs. A transfer theorem states exactly which initialization certificate is sufficient and how many prepaid facilities it requires. The three applications supply this certificate in different ways. The metric case uses a quota prefix of reassigning JMS; the priority case uses persistent contributions and a cleanup ordered by service level; and the squared-metric case uses a local factor-revealing certificate valid for arbitrary client subsets of the same run. We provide complete finite proofs of the numerical interfaces, including an exact rational certificate for the squared-metric bound.

Introduction

Facility location with outliers asks which facilities to open and which clients to serve. Opening a facility incurs a cost, and each served client pays its connection cost to an open facility. Given a quota pp, the objective is to minimize these two costs while serving at least pp clients. With nonnegative costs, an optimum can be chosen to serve exactly pp.

For full-service facility location, a powerful approach controls opening and connection costs separately, then improves their tradeoff by scaling opening costs and greedily adding facilities. In the metric setting, Mahdian, Ye, and Zhang [6] use this approach to obtain a 1.52-approximation. With a prescribed outlier quota, the metric guarantee of JMS [JMM+03, Section 8.6] is 2, also recorded as the best known bound by Dabas, Khuller, and Rivkin [2]. This raises a concrete question: how much of the stronger opening/connection tradeoff can be retained when the algorithm also chooses which clients to serve?

Two accounting issues arise. First, an opening event can overshoot the quota: with a target of 100 clients, it may increase the number connected from 98 to 105. Deleting five new clients restores the quota but removes their contributions to the facility’s opening cost. Second, greedy improvement changes the best choice of clients: a newly opened facility can make former outliers cheaper to serve than the current clients. The analysis must compare the resulting savings with an optimum that may serve a different client set.

Our contribution is a transfer theorem that connects quota initialization to client-reselecting improvement while retaining separate control of opening and service costs. Its input is a joint cost bound for an initial solution, allowing a bounded number of unpaid facilities. Its output is an approximation guarantee in the original costs, together with an explicit condition on how many expensive facilities must be guessed and prepaid to absorb the deficit. The shared proof handles client reselection through supermodularity. The model-specific task is to construct the initial cost bound. This separation yields three improved guarantees.

Results

All three models have finite, explicitly given facility candidates, nonnegative opening costs, and no capacities. In the metric model, connection costs are distances in a common metric space. In the priority model, each facility has a service level and each client has a minimum required level; a connection is allowed when the facility meets that requirement. In the squared-metric model, the connection matrix satisfies

cij≤cij′+ci′j′+ci′j(i,i′∈F, j,j′∈J).\sqrt{c_{ij}} \le\sqrt{c_{ij'}} + \sqrt{c_{i'j'}} + \sqrt{c_{i'j}} \qquad(i,i' \in\mathcal{F},\ j,j' \in\mathcal{J}).

This includes squared Euclidean distances on finite candidate sets.

Theorem 1.1 (Three exact-quota guarantees). There are deterministic polynomial-time algorithms for the following problems:

  1. Metric facility location with outliers, with approximation factor 571/376=1.518617…<1.52571/376 = 1.518617\ldots< 1.52.

  1. Priority metric facility location with outliers, with approximation factor strictly less than 1.8531.853.

  1. Squared-metric facility location with outliers, with approximation factor 43399/20000=2.16995<2.1743399/20000 = 2.16995 < 2.17.

Each algorithm connects exactly pp clients on feasible instances. Its running time is polynomial in the binary encoding length of the explicit rational input.

Table 1 compares these guarantees with the earlier bounds for the corresponding outlier models. The three applications have distinct roles in the framework. The metric case shows how to transfer the classical JMS–MYZ cost tradeoff through a quota prefix. Priority constraints restrict which connections are legal; they require a different initialization and cleanup, while the improvement analysis remains the same. Squared-metric costs keep all connections available but change the local geometric bound; they require a squared-metric local certificate at the same interface.

ModelEarlier guaranteeThis paper
Metric FLPO2 [JMM+03]571/376 < 1.52
Priority FLPO3 [5]< 1.853
Squared-metric FLPO9 [7]2.16995 < 2.17

Table 1. Guarantees for facility location with a prescribed outlier quota. All rows allow nonuniform opening costs and respect the quota exactly.

The transfer mechanism

For an open set SS, let Cp(S)C_p(S) be the cost of connecting the cheapest pp clients, using only legal connections. The algorithm has three stages: construct a quota-feasible solution, improve it while reselecting clients, and restore all opening costs. We describe the certificate that links them.

Keep a joint cost bound after truncation. Guess and prepay a constant-size seed set. In the branch containing expensive facilities of a fixed optimum, let PP be their total original cost and put R=F⋆−PR = F^\star- P. Here F⋆F^\star and C⋆C^\star are the opening and connection components of that optimum. After truncation, exempt at most bb additional facilities and let ww denote the opening costs with seeds and exceptions set to zero. For the initial facility set S0S_0 and constants AA, BB, t≥1t \ge1, the required certificate is

tw(S0)+Cp(S0)≤AtR+BC⋆.(1)t w(S_0) + C_p(S_0) \le AtR + BC^\star. \tag*{(1)}

The coefficients AA, BB measure the initializer’s losses, and tt weights its opening cost. For a JMS prefix, the retained clients have the pp smallest frozen budgets in a full continuation of the same run. Their total budget is therefore at most that of the optimum’s clients. Applying a local bound to each optimum facility and its assigned clients gives (1). Deleting only from the last opening event confines the unpaid contributions to one facility. The priority application obtains the same certificate through a growth process with a cleanup that preserves legal connections.

Improve the facility set and the served set together. For a fixed cost matrix and eligibility relation, CpC_p is nonincreasing and supermodular on feasible supersets. In concrete terms, opening a facility saves less once more facilities are already available, even after the clients are reselected. This follows from threshold coverage: for any price threshold, the number of clients reachable below that price is a coverage function; capping it at pp and integrating the remaining deficit gives CpC_p. Supermodularity makes the individual savings from the optimum’s facilities cover the current connection-cost gap. Greedy additions maximizing savings per unit of opening cost produce a final set SgS_g satisfying

w(Sg)+Cp(Sg)≤(A+ln⁡t)R+(1+B−1t)C⋆.(2)w(S_g) + C_p(S_g) \le(A + \ln t)R + \left(1 + \frac{B - 1}{t}\right) C^\star. \tag*{(2)}

This is the step that lets a changing served set inherit an opening/connection tradeoff.

Restore the unpaid costs. When hh seeds are the most expensive optimum facilities, pruning more expensive nonseeds makes each exception cost at most τ\tau, the cheapest seed cost. Thus P≥hτP \ge h\tau. If both coefficients in (2) are at most aa, restoring original costs gives

a(OPT−P)+P+bτ≤aOPT+[b−h(a−1)]τ.a(\mathrm{OPT}-P)+P+b\tau\le a\mathrm{OPT}+[b-h(a-1)]\tau.

The condition h(a−1)≥bh(a-1) \ge b therefore completes the transfer. It relates the approximation factor to the number of exceptional facilities and the amount of enumeration required. Our metric and priority algorithms use two seeds and one exception; the squared-metric algorithm uses one of each.

Related work and the resulting contribution

Quota prefixes and exceptional costs. Charikar, Khuller, Mount, and Narasimhan [1 Section 5.3] introduced expensive-facility guessing and pruning, stopped growth at the quota, removed excess clients from the final batch, and accounted separately for the last facility. JMS [JMM+03, Section 8.6] adapted this construction to obtain a metric 2-approximation. We retain this treatment of the final event and connect it to a stronger joint cost bound that can drive subsequent augmentation. The transfer theorem makes the cost restoration explicit for bb exceptions and hh prepaid seeds.

Cost improvement with client reselection. JMS [JMM+03] supplies the reassigning growth process and arbitrary-star factor-revealing analysis. MYZ [6] derives the (1.11, 1.78) coefficients and combines cost scaling with greedy augmentation for its full-service 1.52 guarantee. Luo, Han, Shuai, and Wang [5] also use density-based additions with client reselection as a heuristic for priority FLPO. Our analysis connects these improvement steps to the quota initializer: the supermodularity of CpC_p compares different served sets, and the joint certificate yields the two coefficients in (2). This connection gives a guarantee for the complete initialization-and-improvement procedure.

Priority connections. Luo et al. [5] give a primal-dual 3-approximation for priority FLPO. Their model and cleanup by service level provide the basis for our priority initializer. We retain frozen clients’ contributions, truncate at the quota, and preserve the separate opening and connection payments through cleanup. The resulting certificate has A=1A=1, B=3B=3 and one exceptional facility. Combining it with the shared improvement and restoration analysis gives strictly less than 1.853.

Squared-metric costs. Fernandes, Meira, Miyazawa, and Pedrosa [3] develop upper-bound factor-revealing programs and obtain a 2.17 guarantee for the scaled, greedily augmented algorithm in the full-service squared-metric model. We establish the local form needed for quota transfer: a bound on any client subset of the same run. A finite replication-and-averaging argument connects this form to their constraint system; an exact rational certificate supplies our numerical coefficients. The transfer theorem then gives 2.16995 with a prescribed outlier quota. In this model, Ren and Tian [7] give the previous 9-approximation. Zhang, Yuan, and Li [8] study a multilevel extension, in which service follows a path through one facility at each level, and give a 32-approximation. Our squared-metric result concerns the single-level model in Table 1.

Organization. § 2 states and proves the transfer theorem. § 3, § 4, and § 5 supply the three initializers and approximation guarantees. The appendices give the full event-level metric proof, discrete greedy analysis, and finite local certificates. The numerical proof data and a solver-free verifier accompany the squared-metric certificate.

A transfer theorem for bounded payment deficits

Let F\mathcal{F} be a finite facility set with nonnegative opening costs ff. A feasible open set SS has service cost C(S)≥0C(S) \ge0. We assume that adding facilities preserves feasibility and that CC is polynomial-time computable, nonincreasing, and supermodular on supersets of a feasible initial set. In diminishing-savings notation, this means

C(X)−C(X∪{i})≥C(Y)−C(Y∪{i})for feasible X⊆Y, i∉Y.C(X) - C(X \cup\{i\}) \ge C(Y) - C(Y \cup\{i\}) \quad\text{for feasible } X \subseteq Y,\ i \notin Y.

The theorem separates two obligations: prove this diminishing-savings property, and construct a quota-feasible initializer with the joint cost bound below. For our three models, the first obligation follows from the same coverage argument.

Reselection through threshold coverage. For a fixed eligibility relation, define dj(S)=min⁡{cij:i∈S, i eligible for j}d_j(S) = \min\{c_{ij} : i \in S,\ i\text{ eligible for }j\}, with minimum +∞+\infty when the set is empty. Let Cp(S)C_p(S) be the sum of the pp smallest dj(S)d_j(S). A set is feasible precisely when at least pp of these values are finite. The function is computed by scanning eligible edges and sorting. For Nu(S)={j:dj(S)≤u}N_u(S) = \{j : d_j(S) \le u\},

Cp(S)=∫0∞[p−min⁡{p,∣Nu(S)∣}] du.(3)C_p(S) = \int_0^\infty[p - \min\{p, |N_u(S)|\}]\,du. \tag*{(3)}

Each Nu(S)N_u(S) is a union of fixed neighborhoods. The marginal gain in capped coverage decreases when SS grows. Integrating gives supermodularity of CpC_p; on feasible supersets the integral is finite. The proof uses neither triangle inequalities nor complete eligibility.

Seeds, exceptions, and the certificate. Fix integers h≥1h \ge1 and b≥0b \ge0. For each hh-element seed set HH, retain

IH=H∪{i:fi≤τ},τ=min⁡i∈Hfi,P=f(H).I_H = H \cup\{i : f_i \le\tau\}, \qquad\tau= \min_{i \in H} f_i, \qquad P = f(H).

An initializer either discards the branch or returns a feasible S0⊇HS_0 \supseteq H and E⊆S0∖HE \subseteq S_0 \setminus H with ∣E∣≤b|E| \le b. Set wi=0w_i = 0 on H∪EH \cup E and wi=fiw_i = f_i elsewhere, and include every zero-ww facility in S0S_0. Starting at S0S_0, repeatedly add an unopened facility maximizing (C(S)−C(S∪{i}))/wi(C(S) - C(S \cup\{i\}))/w_i whenever this ratio exceeds one. All unopened facilities have positive wiw_i. Evaluate every output using f(S)+C(S)f(S) + C(S), and also evaluate every feasible facility set of size less than hh.

Theorem 2.1 (Bounded-deficit transfer). Assume the initializer runs in polynomial time, and that feasibility and service cost can be evaluated in polynomial time for sets of size less than hh. Fix A,B,t≥1A, B, t \ge1 and

a=max⁡{A+ln⁡t, 1+(B−1)/t}>1.a = \max\{A + \ln t,\ 1 + (B - 1)/t\} > 1.

For a fixed optimum O⋆O^\star of size at least hh, suppose its hh most expensive facilities define a nondiscarded branch in which O⋆O^\star remains feasible and the initializer satisfies

tw(S0)+C(S0)≤At(F⋆−P)+BC⋆,F⋆=f(O⋆),C⋆=C(O⋆).(4)t w(S_0) + C(S_0) \le At(F^\star- P) + BC^\star,\qquad F^\star= f(O^\star),\qquad C^\star= C(O^\star). \tag*{(4)}

If h(a−1)≥bh(a - 1) \ge b, this algorithm is an aa-approximation, in polynomial time for fixed h,bh, b. The conclusion also holds with any larger aa satisfying these inequalities.

Proof. If ∣O⋆∣<h|O^\star| < h, direct enumeration finds an optimum. Otherwise work in its good seed branch and put R=F⋆−PR = F^\star- P. Since some reference facilities may also be exempted, w(O⋆)≤Rw(O^\star) \le R. Supermodularity and monotonicity give

∑i∈O⋆∖S[C(S)−C(S∪{i})]≥C(S)−C(S∪O⋆)≥C(S)−C⋆.\sum_{i \in O^\star\setminus S} [C(S) - C(S \cup\{i\})] \ge C(S) - C(S \cup O^\star) \ge C(S) - C^\star.

If D=C(S)−C⋆>R>0D = C(S) - C^\star> R > 0, the best density is at least D/R>1D/R > 1. For a step costing vv and reducing the gap to D′D', therefore v≤R(D−D′)/Dv \le R(D-D')/D. Summing steps above RR by integration gives a logarithm. If the first crossing moves from s>Rs > R to d≤Rd \le R, combine its opening cost with the remaining gap:

v+d≤R+d(1−R/s)≤R+Rln⁡(s/R).v+d \le R+d(1-R/s) \le R+R\ln(s/R).

A crossing exists because there are finitely many additions and greedy cannot stop above the threshold. Later additions reduce the total accounted cost. Writing F0=w(S0)F_0=w(S_0) and C0=C(S0)C_0=C(S_0) yields

w(Sg)+C(Sg)≤F0+C⋆+R+Rln⁡((C0−C⋆)/R)w(S_g)+C(S_g) \le F_0+C^\star+R+R\ln((C_0-C^\star)/R)

when C0>C⋆+RC_0>C^\star+R, and at most F0+C0F_0+C_0 otherwise. Substitute (4) and maximize 1+ln⁡x−x/t1+\ln x-x/t over x>1x>1. Its maximum is ln⁡t\ln t, attained at x=tx=t (or approached at the endpoint when t=1t=1). The other case uses 1−1/t≤ln⁡t1-1/t\le\ln t. This proves

w(Sg)+C(Sg)≤(A+ln⁡t)R+(1+B−1t)C⋆≤a(OPT−P).(5)w(S_g)+C(S_g) \le(A+\ln t)R+\left(1+\frac{B-1}{t}\right)C^\star\le a(\mathrm{OPT}-P). \tag*{(5)}

For R=0R=0, all reference facilities have zero accounted cost and belong to S0S_0, so C0≤C⋆C_0\le C^\star. Substitution into F0+C0F_0+C_0 gives the same bound. Appendix C gives the full discrete calculation.

Restoring HH and EE adds at most P+bτP+b\tau, while P≥hτP\ge h\tau. Hence

f(Sg)+C(Sg)≤aOPT−(a−1)P+bτ≤aOPT+[b−h(a−1)]τ≤aOPT.f(S_g)+C(S_g) \le a\mathrm{OPT}-(a-1)P+b\tau\le a\mathrm{OPT}+[b-h(a-1)]\tau\le a\mathrm{OPT}.

The number of seed branches and direct candidates is polynomial for fixed hh; there are at most ∣F∣|F| additions per branch. All choices use computable costs, not the reference optimum.

The theorem is an interface for initializers. Its parameters make the three applications easy to compare:

ModelAABBttSeeds hhExceptions bb
Metric1.111.78188/12521
Priority131173/50021
Squared metric1.450013.403220543/1000011

Table 1 (PDF p. 6).

The coefficient tt multiplies accounted opening cost in the certificate. For the priority initializer it is three times the growth-process scaling, because cleanup charges connection costs by a factor of three. The following sections establish each row: first the metric quota prefix, then the cleanup needed for priority constraints, and finally the local certificate needed for squared costs.

Metric facility location: a quota prefix of JMS

In the metric case, we obtain the initializer by stopping reassigning JMS at the quota and applying its local cost bound to the optimum’s clients. This section gives the complete transfer at the level of the cost certificate; Appendices A–F provide the event and finite-certificate details.

Let F,J\mathcal{F},\mathcal{J} be finite facility and client sets, with metric connection costs cijc_{ij} and quota pp. Return the empty solution for p=0p=0. For p>0p>0, use two seeds, enumerate singleton solutions as well, and set gi=0g_i=0 on HH and gi=ρfig_i=\rho f_i elsewhere, where ρ=188/125\rho=188/125.

Growth and truncation. Run reassigning JMS on the pruned candidate set. An unconnected client’s budget grows with time. Its budget αj\alpha_j freezes at first connection; a connected client’s current distance rjr_j can decrease through reassignment. A closed facility receives offers (t−cij)+(t-c_{ij})^+ from unconnected clients and (rj−cij)+(r_j-c_{ij})^+ from connected clients. When offers pay its fee, open it and connect or reassign the positive contributors. A client also connects when the clock reaches its distance to an already open facility. Open zero-cost facilities at time zero and process tied events in fixed order.

Check the quota after each atomic event. At the first event connecting at least pp clients, remove any excess only from the newly connected batch. Let KK be the retained clients, S0S_0 the open facilities, and EE the final opening facility when deletion was needed, or the empty set otherwise. Keep EE open. Set w=0w=0 on H∪EH\cup E and w=fw=f elsewhere, then run the common augmentation procedure. Appendix A specifies all event rules.

A local budget comparison. For every facility ii and every client subset VV of the same complete JMS run,

∑j∈Vαjfull≤1.11gi+1.78∑j∈Vcij.(6)\sum_{j\in V}\alpha_j^{\mathrm{full}}\leq1.11g_i+1.78\sum_{j\in V}c_{ij}. \tag*{(6)}

The arbitrary-star analysis is due to JMS and the coefficients to MYZ [JMM+03, MYZ06]; Appendix E gives a finite proof with exact constants. Complete the original prefix without deleting clients or changing fees. The retained KK consists of pp smallest frozen budgets in that continuation. Applying (6) to the reference optimum’s assignment groups gives

L:=∑j∈Kαj≤1.11g(O⋆)+1.78C⋆.L:=\sum_{j\in K}\alpha_j\leq1.11g(O^\star)+1.78C^\star.

One unpaid opening. At each JMS event, opening costs plus current connection costs equal the sum of connected clients’ frozen budgets. If the removed clients form a set DD and the final facility is ℓ\ell, their deleted opening contributions sum to

δ=∑j∈D(T−cℓj)≤gℓ.\delta=\sum_{j\in D}(T-c_{\ell j})\leq g_\ell.

Subtracting their budgets and connections from the event identity gives g(S0)+∑j∈Krj=L+δg(S_0)+\sum_{j\in K}r_j=L+\delta. Exempting ℓ\ell and choosing the cheapest pp clients therefore yields

g(S0∖E)+Cp(S0)≤L.g(S_0\setminus E)+C_p(S_0)\leq L.

The same inequality follows directly when there is no deletion. In the good seed branch, g(O⋆)=ρ(F⋆−P)g(O^\star)=\rho(F^\star-P) and g(S0∖E)=ρw(S0)g(S_0\setminus E)=\rho w(S_0). This is exactly the transfer certificate with A=1.11A=1.11, B=1.78B=1.78, t=ρt=\rho, b=1b=1.

Theorem 3.1. Metric facility location with outliers has a deterministic polynomial-time 571/376-approximation serving exactly pp clients.

Proof. For ρ=188/125\rho=188/125, put a=571/376a=571/376. The exact comparisons are

1.11+ln⁡ρ<a=1+0.78/ρ,3/2<a<1.52.1.11+\ln\rho<a=1+0.78/\rho,\qquad3/2<a<1.52.

For example, with z=63/313z=63/313, the positive series for the logarithm gives ln⁡ρ≤2(z+z3/(3(1−z2)))=6005349/14711000\ln\rho\leq2(z+z^3/(3(1-z^2)))=6005349/14711000; its gap to a−1.11a-1.11 is 727/1838875>0727/1838875>0. The transfer theorem applies with h=2,b=1h=2,b=1. The full accounting and rational implementation appear in Appendices B and F.

Priority facility location: preserving legal connections

Priority constraints preserve the service-cost structure from Section 2 but change which reassignments are legal. The initializer must preserve that eligibility through its cleanup.

A candidate is a location–level pair: facility ii has level sis_i, and client jj requires ℓj\ell_j. An edge is eligible when si≥ℓjs_i \ge\ell_j; its cost is the metric distance between the two locations. We use the model of [5], including nondecreasing fees with level at a fixed location. If several levels are opened at one location, the highest can serve all their clients, so the output can be consolidated without increasing cost.

The initializer retains contributions after clients freeze. This makes its price comparison straightforward, but can pay several tentative facilities with the same money. A cleanup in decreasing service level removes that overlap and ensures that reassignment remains legal. These two properties supply the certificate needed by the transfer theorem.

Theorem 4.1. For the priority model above there is a deterministic polynomial-time algorithm with cost at most aPa_P OPT, where

aP=max⁡{1+ln⁡1173500, 1+10001173}<1.853.a_P = \max\left\{1 + \ln\frac{1173}{500},\ 1 + \frac{1000}{1173}\right\} < 1.853.

It respects the exact service quota and returns zero cost when OPT=0\mathrm{OPT}=0.

Proof. For p=0p=0 return the empty solution. Enumerate all single-facility candidates and all pairs HH. For a pair put P=f(H)P=f(H), τ=min⁡h∈Hfh\tau=\min_{h\in H} f_h, and retain HH and all facilities of original price at most τ\tau. Discard a branch if fewer than pp clients have any eligible facility. Set ρP=391/500\rho_P=391/500, g=0g=0 on HH, and gi=ρPfig_i=\rho_P f_i otherwise.

Growth and exact-quota truncation. Open all zero-gg facilities at time zero. Unfrozen client prices grow with the common clock; frozen prices stay fixed. On an eligible edge put βij=(αj−cij)+\beta_{ij}=(\alpha_j-c_{ij})_+, retaining this contribution after freezing. Open a closed facility when its total contribution equals its fee, freezing its active positive contributors. Freeze an active client separately when its clock reaches its distance to an open eligible facility. Process simultaneous events one at a time in fixed order and test the quota after each event. At the first attainment of at least pp, remove excess clients only from the final event’s newly frozen clients. Let KK be the pp retained clients and EE the last opening facility if deletion occurred, or the empty set otherwise. Do not change prices or supports after deletion.

The price comparison. For every retained candidate, ∑jβij≤gi\sum_j \beta_{ij}\le g_i. A closed facility cannot cross its opening threshold. At an opening, all active positive contributors freeze. Subsequent active clients freeze no later than their distance to that open facility; thus its support and contributions never grow again. Zero-cost facilities have no positive contributors. The clients in KK have pp smallest stopping prices, including ties. Consequently every eligible comparison solution serving pp clients at cost CrC^r satisfies

L:=∑j∈Kαj≤Cr+g(O).L := \sum_{j\in K}\alpha_j \le C^r + g(O).

This is valid even when the comparison clients differ from KK.

Cleanup and legal reassignment. Let Bi={j:βij>0}B_i=\{j:\beta_{ij}>0\} for each opened facility, including deleted clients. Scan facilities by nonincreasing service level and retain a facility precisely when its support is disjoint from all previously retained supports. Call the retained set QQ. A client supports at most one member of QQ. For j∈Kj\in K set (αjf,αjc)=(βij,cij)(\alpha_j^f,\alpha_j^c)=(\beta_{ij},c_{ij}) if such i∈Qi\in Q exists; otherwise use (0,αj)(0,\alpha_j). In both cases the two components sum to αj\alpha_j.

Put S0=Q∪H∪E∪{i:gi=0}S_0 = Q \cup H \cup E \cup\{i : g_i = 0\} and set wi=0w_i = 0 on H∪EH \cup E, wi=fiw_i = f_i otherwise. Every positive contributor of a facility opened before the final event froze before that event and remains in KK. Thus each paid member of QQ is completely funded by KK. Disjoint supports imply

ρPw(S0)≤∑j∈KαjF.\rho_P w(S_0) \le\sum_{j \in K} \alpha_j^F.

A positive contributor to QQ connects directly at cost αjC\alpha_j^C. Otherwise let aa witness the first freezing of jj. Its opening time obeys ta≤αjt_a \le\alpha_j and caj≤αjc_{aj} \le\alpha_j. If aa was discarded, a retained facility bb of level sb≥sas_b \ge s_a shares a positive contributor j′j'. This contributor froze by tat_a, so

αj′≤ta≤αj,caj′,cbj′<αj′.\alpha_{j'} \le t_a \le\alpha_j,\qquad c_{aj'},c_{bj'} < \alpha_{j'}.

The metric path j,a,j′,bj,a,j',b gives cbj≤3αjc_{bj} \le3\alpha_j, and bb is eligible for jj. The level order of cleanup is what guarantees eligibility. If a∈Qa \in Q connect directly. Therefore

Cp(S0)≤3∑j∈KαjC.C_p(S_0) \le3\sum_{j \in K} \alpha_j^C.

Combining the two payments and the comparison price bound, for t=3ρP=1173/500t = 3\rho_P = 1173/500,

tw(S0)+Cp(S0)≤tf(O∖H)+3Cr(H⊆O).tw(S_0) + C_p(S_0) \le tf(O \setminus H) + 3C^r \qquad(H \subseteq O).

Applying the transfer theorem. Choose the branch whose seeds are the two most expensive facilities of a fixed optimum. All optimal facilities survive, P≥2τP \ge2\tau, and R=F∗−P≥0R = F^* - P \ge0. Theorem 2.1, with A=1A = 1, B=3B = 3, gives

w(Sg)+Cp(Sg)≤(1+ln⁡t)R+(1+2/t)C∗≤aP(OPT⁡−P).w(S_g) + C_p(S_g) \le(1+\ln t)R + (1+2/t)C^* \le a_P(\operatorname{OPT}-P).

Every zero-ww facility is initially included. The R=0R = 0 case is included in that theorem. For z=673/1673z = 673/1673, the positive logarithmic series gives

ln⁡t≤2(z+z3/3)+2z55(1−z2)=U:=2342547054287459327463497192705000<8531000.\ln t \le2(z+z^3/3)+\frac{2z^5}{5(1-z^2)} = U := \frac{23425470542874593}{27463497192705000} < \frac{853}{1000}.

Also 1000/1173<U1000/1173 < U and aP>3/2a_P > 3/2. The exception has original price e≤τe \le\tau, so restoring original fees gives

f(Sg)+Cp(Sg)≤aPOPT⁡−(aP−1)P+e≤aPOPT⁡+(3−2aP)τ≤aPOPT⁡.f(S_g) + C_p(S_g) \le a_P\operatorname{OPT}-(a_P-1)P+e \le a_P\operatorname{OPT}+(3-2a_P)\tau\le a_P\operatorname{OPT}.

One-facility optima were explicitly enumerated. At any location retain just the highest opened level: this facility was already paid for, and it can serve all clients of the deleted lower levels at the same distance. Nonnegative fees ensure no cost increase.

There are O(m2)O(m^2) branches, at most m+nm+n growth events and mm greedy additions per branch. Between distance breakpoints the growth contribution is affine with integer slope at most nn. Event times require rational operations and division by such an integer; common denominator bit length grows by at most O((m+n)log⁡(n+1))O((m+n)\log(n+1)) beyond input length. Eligibility, cleanup and client selection are polynomial. Thus the statement holds in the rational bit model.

Squared-metric facility location: certifying the local bound

The squared-metric application changes a different part of the initializer. All connections are eligible, so the JMS event accounting and quota truncation from § 3 apply directly. The finite input matrix now satisfies the square-root triangle inequality stated in the introduction. To obtain the joint certificate, we replace the metric local budget bound by the following inequality.

Lemma 5.1 (Squared-metric local certificate). In any complete reassigning JMS run with opening costs gg, for every candidate facility ii and every client subset VV,

∑j∈Vαjfull≤Agi+B∑j∈Vcij,A=1.45001,B=3.4032.\sum_{j \in V} \alpha_j^{\mathrm{full}} \le A g_i + B \sum_{j \in V} c_{ij}, \qquad A = 1.45001,\qquad B = 3.4032.

Proof overview. Order VV by frozen price and put dj=cijd_j = c_{ij}. The same-run constraints are monotonicity of prices and reassignment distances, a local offer budget, and

αl≤rjl+dj+dl(j<l).\sqrt{\alpha_l} \le\sqrt{r_{jl}} + \sqrt{d_j} + \sqrt{d_l}\qquad(j < l).

These are the squared-metric factor-revealing constraints of [3]. For arbitrary ∣V∣|V|, replicate every client kk times and divide the resulting sequence into kk equal blocks. Averaging preserves the budget by convexity of the positive-part function and preserves the triangle constraint by concavity of (x+y+z)2(\sqrt{x}+\sqrt{y}+\sqrt{z})^2. Thus a fixed-size upper-bound program controls every subset size.

For k=400k = 400, a rational nonnegative combination of valid rows yields coefficients 1.450000003915 and 3.403166095612, which are bounded by the stated A,BA,B. The rows, their multipliers, and a solver-free verifier are provided with the paper. Appendix § 12 proves the same-run constraints and finite reduction; Appendix § 13 gives the exact coefficient checks, including all rounding residuals. □

From the certificate to a quota. Use the metric prefix procedure with one seed H={h}H = \{h\}, keeping all facilities of original fee at most fhf_h. Set gh=0g_h = 0 and gi=ρfig_i = \rho f_i otherwise, with ρ=20543/10000\rho= 20543/10000. Stop at the first quota-reaching event, remove excess new clients, and exempt its final facility when needed. The retained-budget comparison and deleted-contribution identity in § 3 do not use triangle inequalities. With Lemma 5.1, they give

ρw(S0)+Cp(S0)≤Aρ(F⋆−P)+BC⋆.\rho w(S_0) + C_p(S_0) \le A\rho(F^\star- P) + BC^\star.

The greedy service-cost analysis is unchanged as well. This proves the initialization requirements of the transfer theorem with one exception.

Theorem 5.2. Squared-metric facility location with outliers has a deterministic polynomial-time (43399/20000)(43399/20000)-approximation serving exactly pp clients.

Proof. Let a=43399/20000=2.16995a = 43399/20000 = 2.16995 and z=(ρ−1)/(ρ+1)=10543/30543z = (\rho- 1)/(\rho+ 1) = 10543/30543. Exact rational comparison gives

A+2∑u=019z2u+12u+1+2z4141(1−z2)<a,1+B−1ρ=4457520543<a.A + 2 \sum_{u=0}^{19} \frac{z^{2u+1}}{2u+1} + \frac{2z^{41}}{41(1-z^2)} < a,\qquad1 + \frac{B-1}{\rho} = \frac{44575}{20543} < a.

The first expression bounds A+ln⁡ρA + \ln\rho from above. Since a>2a > 2, a single seed absorbs the one exception: h(a−1)≥bh(a - 1) \ge b for h=b=1h = b = 1. Apply Theorem 2.1. Its zero-residual case includes an optimum using only the seed. Event times and density comparisons are rational; computing square roots and solving the certificate program are not steps of the approximation algorithm. □

Metric algorithm: event rules and cost accounts

Let F\mathcal{F} and J\mathcal{J} be finite facility and client sets, with m=∣F∣≥1m = |\mathcal{F}| \ge1 and n=∣J∣n = |\mathcal{J}|. Facility ii has opening cost fi>0f_i > 0. Facilities and clients lie in a common metric space; cijc_{ij} denotes their distance, and distinct input objects may be colocated. All distances are finite. The integer quota satisfies 0≤p≤n0 \le p \le n. For p=0p = 0, the algorithm returns the empty solution, so assume p≥1p \ge1 below.

For nonempty S⊆FS \subseteq\mathcal{F}, define

dj(S)=min⁡i∈Scij,Cp(S)=min⁡K⊆J∣K∣=p∑j∈Kdj(S),Δi(S)=Cp(S)−Cp(S∪{i}).(7)d_j(S) = \min_{i \in S} c_{ij}, \qquad C_p(S) = \min_{\substack{K \subseteq\mathcal{J}\\|K|=p}} \sum_{j \in K} d_j(S), \qquad\Delta_i(S) = C_p(S) - C_p(S \cup\{i\}). \tag*{(7)}

Sorting the distances computes Cp(S)C_p(S) and a served set attaining it. Write v(S)=∑i∈Sviv(S) = \sum_{i \in S} v_i for any facility-cost vector vv. Fix

ρ=188125,a=571376.(8)\rho= \frac{188}{125}, \qquad a = \frac{571}{376}. \tag*{(8)}

All ties are resolved using a fixed deterministic ordering of facilities, clients, and event types, independent of the unknown optimum.

A prefix of reassigning JMS

Run the reassigning JMS process [JMM+03, Algorithm 2] on a nonempty candidate set II with fixed nonnegative opening costs gg. Let SS be the open facilities, UU the connected clients, and tt the clock. An unconnected client has budget tt. Its budget αj\alpha_j freezes when it first connects. A connected client has a current assigned distance rjr_j, which can decrease after reassignment. Its frozen budget and current distance must be kept distinct.

Initially, open every zero-gg facility and set U=∅U = \varnothing at time zero. An unconnected client does not connect to a positive-distance facility merely because that facility is free. For each closed facility ii, client jj offers

bij(t)={(t−cij)+,j∉U,(rj−cij)+,j∈U.(9)b_{ij}(t) = \begin{cases} (t-c_{ij})_+, & j \notin U,\\ (r_j-c_{ij})_+, & j \in U. \end{cases} \tag*{(9)}

Advance the clock until an event is possible, and process events as follows.

  1. When ∑jbij(t)=gi\sum_j b_{ij}(t) = g_i for a closed facility, open it and connect or reassign every client with a strictly positive offer. Newly connected clients freeze at αj=t\alpha_j = t; all clients assigned in this event receive current distance rj=cijr_j = c_{ij}.

  1. When an unconnected client satisfies t=cijt = c_{ij} for an open facility, connect that client and freeze its budget at tt.

Recompute offers and event eligibility after each event. A client with zero offer at an opening is handled by a single-client event, if needed. Check the quota immediately after each event, even when other events have the same timestamp. Stop at the first event with ∣U∣≥p|U| \ge p.

Let TT be the stopping time and S0S_0 the open set. If ∣U∣=p|U| = p, set K=UK = U and E=∅E = \varnothing. Otherwise the last event opened a facility ℓ\ell. Remove exactly ∣U∣−p|U|-p clients from that event’s newly connected batch, and call the retained set KK. Set E={ℓ}E = \{\ell\}. The facility ℓ\ell remains open.

Enumeration and augmentation

For each pair H⊆FH \subseteq\mathcal{F}, set

P=f(H),τ=min⁡h∈Hfh,IH=H∪{i∈F:fi≤τ}.(10)P = f(H), \qquad\tau= \min_{h \in H} f_h, \qquad I_H = H \cup\{i \in\mathcal{F}: f_i \le\tau\}. \tag*{(10)}
CostMeaningDefinition in a pair branch
fif_iOriginal opening costInput; used to select the output
gig_iJMS opening cost0 on HH, and ρfi\rho f_i elsewhere
wiw_iAugmentation cost0 on H∪EH \cup E, and fif_i elsewhere

Table 2. The metric never changes. The exceptional facility is kept open; only its cost account changes after the prefix is formed.

Run the prefix procedure on IHI_H with costs gi=0g_i=0 for i∈Hi\in H and gi=ρfig_i=\rho f_i otherwise. After it returns (S0,K,E)(S_0,K,E), fix residual costs wi=0w_i=0 for i∈H∪Ei\in H\cup E and wi=fiw_i=f_i otherwise. Every zero-ww facility is already in S0S_0: zero original costs and seeds were opened initially, and E⊆S0E\subseteq S_0.

Starting from S0S_0, repeatedly add a facility in IH∖SI_H\setminus S of maximum density Δi(S)/wi\Delta_i(S)/w_i if that density exceeds one. The denominator is positive for every unopened candidate. At each step, CpC_p is recomputed over all clients. The set KK from the prefix proof is not held fixed during augmentation.

Algorithm 1: Exact-quota facility location.

  1. Evaluate each singleton facility set, serving its pp cheapest clients.

  2. For each pair HH, form IHI_H and gg, run the quota prefix to obtain (S0,K,E)(S_0,K,E), and fix ww. Run maximum-density augmentation from S0S_0, reselecting clients through CpC_p, to obtain SgS_g.

  3. Return the candidate minimizing f(S)+Cp(S)f(S)+C_p(S), with a served set attaining Cp(S)C_p(S).

No branch is selected using an optimum or a reference cost. The word “prepay” refers to the accounting in the proof; the returned solution pays every original opening cost.

A certificate for the quota prefix

The proof uses a local property of a complete JMS run. Here a star means one candidate facility together with any subset of clients, regardless of how those clients are assigned by the algorithm.

Lemma B.1 (JMS–MYZ local bound). Complete a JMS run under the event rules above, with costs gg, and let αjfull\alpha_j^{\mathrm{full}} be its frozen budgets. For every candidate facility ii and every client subset VV,

∑j∈Vαjfull≤111100gi+8950∑j∈Vcij.(11)\sum_{j\in V}\alpha_j^{\mathrm{full}} \le\frac{111}{100}g_i+\frac{89}{50}\sum_{j\in V}c_{ij}. \tag*{(11)}

The subset is selected for analysis from one run on all clients. JMS’s arbitrary-star construction [JMM+03, Section 5.1] and the coefficients of MYZ [6 Lemma 4] give this interface. Appendix E proves the required statement directly, including equal freeze times, zero costs, and an explicit finite version of the numerical certificate.

Lemma B.2 (Event accounting). After every JMS event,

g(S)+∑j∈Urj=∑j∈Uαj.(12)g(S)+\sum_{j\in U}r_j=\sum_{j\in U}\alpha_j. \tag*{(12)}

Proof. The identity holds at time zero. A single-client event adds its connection distance to both sides. At an opening of ii, let NN be the newly connected clients and BB the reassigned old clients. Tightness gives

gi=∑j∈N(t−cij)+∑j∈B(rˉj−cij).g_i=\sum_{j\in N}(t-c_{ij})+\sum_{j\in B}(\bar r_j-c_{ij}).

The increase in the left side of (12) is consequently gi+∑j∈Ncij+∑j∈B(cij−rˉj)=∣N∣tg_i+\sum_{j\in N}c_{ij}+\sum_{j\in B}(c_{ij}-\bar r_j)=|N|t. This is exactly the increase in frozen budgets.

Lemma B.3 (One exceptional opening). Let (S0,K,E)(S_0,K,E) be any quota prefix. If OO is a reference facility set with an assignment of pp clients of connection cost CrefC^{\mathrm{ref}} in the same candidate instance, then

g(S0∖E)+Cp(S0)≤111100g(O)+8950Cref.(13)g(S_0\setminus E)+C_p(S_0)\leq\frac{111}{100}g(O)+\frac{89}{50}C^{\mathrm{ref}}. \tag*{(13)}

Proof. Continue the original state to a complete JMS run, before removing clients or changing any costs. Put L=∑j∈KαjL=\sum_{j\in K}\alpha_j. Every client connected before time TT is retained. Clients removed at time TT have budget TT, and still-unconnected clients eventually freeze at a time at least TT. Thus KK is a set of pp smallest complete-run budgets. If KrefK^{\mathrm{ref}} is the reference client set, Lemma B.1, applied to its disjoint assignment groups, gives

L≤∑j∈Krefαjfull≤111100g(O)+8950Cref.(14)L\leq\sum_{j\in K^{\mathrm{ref}}}\alpha_j^{\mathrm{full}}\leq\frac{111}{100}g(O)+\frac{89}{50}C^{\mathrm{ref}}. \tag*{(14)}

Unused reference facilities only add nonnegative cost on the right.

All connection distances in the following accounting refer to the stopping state, denoted by rj(T)r_j(T), rather than to the complete continuation. If no clients are removed, Lemma B.2 and Cp(S0)≤∑j∈Krj(T)C_p(S_0)\leq\sum_{j\in K}r_j(T) prove the claim. Otherwise let DD be the removed clients and ℓ\ell the last facility. Each j∈Dj\in D first connects in this event, so its budget is TT and its distance is cℓjc_{\ell j}. Define its total opening contribution by

δ=∑j∈D(T−cℓj).\delta=\sum_{j\in D}(T-c_{\ell j}).

These are a subset of the nonnegative contributions opening ℓ\ell, including any savings from old clients. Hence 0≤δ≤gℓ0\leq\delta\leq g_\ell. Removing the clients’ budgets and distances from (12) gives

g(S0)+∑j∈Krj(T)=L+δ.g(S_0)+\sum_{j\in K}r_j(T)=L+\delta.

Keeping ℓ\ell open and reselecting the cheapest pp clients now yields

g(S0∖E)+Cp(S0)≤L+δ−gℓ≤L.g(S_0\setminus E)+C_p(S_0)\leq L+\delta-g_\ell\leq L.

Combine this with (14).

The reference solution in a good branch

Fix one optimum throughout the analysis, with facilities O⋆O^\star, served clients K⋆K^\star, and opening and connection costs F⋆,C⋆F^\star,C^\star. In particular, OPT=F⋆+C⋆\mathrm{OPT}=F^\star+C^\star; C⋆C^\star need not be the smallest connection cost among all feasible facility sets. Suppose ∣O⋆∣≥2|O^\star|\geq2 and let HH be its two most expensive facilities. They define a branch of the enumeration. Every facility of O⋆O^\star remains in IHI_H.

Define the fixed residual reference budget and the algorithm’s initial costs by

R=F⋆−P,F0=w(S0),C0=Cp(S0).(15)R=F^\star-P,\qquad F_0=w(S_0),\qquad C_0=C_p(S_0). \tag*{(15)}

The quantity RR belongs to the reference solution and does not change during augmentation. In contrast, F0F_0 is the algorithm’s cost before augmentation. Since g(O⋆)=ρRg(O^\star)=\rho R and g(S0∖E)=ρw(S0)g(S_0\setminus E)=\rho w(S_0), Lemma B.3 gives the initialization certificate

ρF0+C0≤111100ρR+8950C⋆.(16)\rho F_0+C_0\le\frac{111}{100}\rho R+\frac{89}{50}C^\star. \tag*{(16)}

Moreover,

w(O⋆)=R−f(E∩O⋆)≤R.(17)w(O^\star)=R-f(E\cap O^\star)\le R. \tag*{(17)}

The possible inequality is useful: RR is an upper bound on the reference opening cost under ww, not a definition of that cost.

Greedy augmentation with changing clients

Throughout this section the residual costs ww and the eligibility relation are fixed. The argument applies to any feasible initial set, including the priority model. All zero-ww facilities are in a nonempty initial set S0S_0. Let F0=w(S0)F_0=w(S_0) and C0=Cp(S0)C_0=C_p(S_0), and write Fg=w(Sg)F_g=w(S_g) and Cg=Cp(Sg)C_g=C_p(S_g) for the final costs. In particular, Fg−F0F_g-F_0 is the sum of the additional opening costs, rather than FgF_g itself.

A comparison at the same current set

Lemma C.1 (Reselection is supermodular). The function CpC_p is nonincreasing. For feasible A⊆BA\subseteq B and i∉Bi\notin B, we have Δi(A)≥Δi(B)\Delta_i(A)\ge\Delta_i(B).

Proof. For a cost threshold u≥0u\ge0, let Nu(S)={j:dj(S)≤u}N_u(S)=\{j:d_j(S)\le u\} and Hu(S)=min⁡{p,∣Nu(S)∣}H_u(S)=\min\{p,\lvert N_u(S)\rvert\}. The cheapest pp distances satisfy

Cp(S)=∫0∞[p−Hu(S)] du.(18)C_p(S)=\int_0^\infty[p-H_u(S)]\,\mathrm{d}u. \tag*{(18)}

Indeed, the number of these distances exceeding uu is p−min⁡{p,∣Nu(S)∣}p-\min\{p,\lvert N_u(S)\rvert\}. This remains true at ties, which do not affect the integral. On supersets of a feasible initial set, the pp smallest distances are finite, so the integrand eventually vanishes.

Let Du(i)={j:i is eligible for j, cij≤u}D_u(i)=\{j:i\text{ is eligible for }j,\ c_{ij}\le u\}. Adding ii increases HuH_u by

min⁡{∣Du(i)∖Nu(S)∣, (p−∣Nu(S)∣)+}.\min\{\lvert D_u(i)\setminus N_u(S)\rvert,\ (p-\lvert N_u(S)\rvert)_+\}.

Both arguments of this minimum can only decrease when SS grows. Thus HuH_u is submodular, and integrating its marginal gains proves the claimed inequality. Monotonicity follows directly from (7). □\square

No metric property was used here. The point is that the client set is already optimized inside CpC_p, so this argument permits a different served set after each facility addition.

Corollary C.2 (Reference marginal bound). If a facility set OO admits a service assignment of pp clients with connection cost at most C⋆C^\star, then, for every feasible SS,

∑i∈O∖SΔi(S)≥Cp(S)−Cp(S∪O)≥Cp(S)−C⋆.(19)\sum_{i\in O\setminus S}\Delta_i(S)\ge C_p(S)-C_p(S\cup O)\ge C_p(S)-C^\star. \tag*{(19)}

Proof. Add the facilities of O∖SO\setminus S one at a time. Their successive savings telescope to Cp(S)−Cp(S∪O)C_p(S)-C_p(S\cup O). Each is at most the corresponding saving measured at the original set SS, by Lemma C.1. The union can use the reference assignment, giving the second inequality. □\square

The discrete threshold crossing

Assume w(O)≤Rw(O) \le R for the reference set in Corollary C.2. For now suppose R>0R > 0. If the current connection cost CC exceeds C⋆+RC^\star+ R, some unopened reference facility has density at least (C−C⋆)/R>1(C - C^\star)/R > 1. To see this, combine (19) with w(O∖S)≤Rw(O \setminus S) \le R and use a weighted average; every unopened facility has positive cost. Therefore greedy cannot stop above this threshold. If the chosen facility costs vv and the new connection cost is C′C', then

v≤RC−C′C−C⋆.(20)v \le R \frac{C-C'}{C-C^\star}. \tag*{(20)}

Lemma C.3 (Cumulative augmentation cost). If R>0R > 0 and C0>C⋆+RC_0 > C^\star+ R, then

Fg+Cg≤F0+C⋆+R+Rln⁡C0−C⋆R.(21)F_g + C_g \le F_0 + C^\star+ R + R \ln\frac{C_0-C^\star}{R}. \tag*{(21)}

If C0≤C⋆+RC_0 \le C^\star+ R, then Fg+Cg≤F0+C0F_g + C_g \le F_0 + C_0.

Proof. Write D=C−C⋆D = C - C^\star. For a step staying above the threshold, with D>D′>RD > D' > R, equation (20) gives

v≤RD−D′D≤∫D′DRx dx.v \le R \frac{D-D'}{D} \le\int_{D'}^D \frac{R}{x}\,dx.

There are finitely many additions, and the algorithm cannot stop with D>RD > R. Thus, when D0=C0−C⋆>RD_0 = C_0 - C^\star> R, a first crossing exists. Denote the gap just before it by s>Rs > R, and just after it by d≤Rd \le R. Integrating over all preceding steps bounds their total opening cost by Rln⁡(D0/s)R\ln(D_0/s).

The crossing step needs a separate bound because dd may be zero or negative. Using (20) and 1−R/s>01 - R/s > 0, its opening cost satisfies

v+d≤R+d(1−R/s)≤R+R(1−R/s)≤R+Rln⁡(s/R).\begin{aligned} v+d &\le R+d(1-R/s)\\ &\le R+R(1-R/s)\\ &\le R+R\ln(s/R). \end{aligned}

We combine vv with dd, not with the full remaining connection cost. The latter is C⋆+dC^\star+ d. At the crossing, total cost is therefore at most

F0+Rln⁡(D0/s)+v+C⋆+d≤F0+C⋆+R+Rln⁡(D0/R).F_0+R\ln(D_0/s)+v+C^\star+d \le F_0+C^\star+R+R\ln(D_0/R).

Every subsequent accepted addition costs less than its connection saving, so total residual cost strictly decreases. The same monotonicity proves the second case when the initial state is already below the threshold.

Using the initialization certificate

The next lemma explains why the opening and connection costs of the initial solution should be bounded together. A larger C0C_0 leaves a smaller allowable F0F_0, and this compensates for a longer augmentation phase.

Lemma C.4 (From initialization to final cost). Suppose A,B≥1A, B \ge1, ρ≥1\rho\ge1, and

ρF0+C0≤AρR+BC⋆.(22)\rho F_0+C_0 \le A\rho R+BC^\star. \tag*{(22)}

With the reference assumptions above, including w(O)≤Rw(O) \le R, greedy returns

Fg+Cg≤(A+ln⁡ρ)R+(1+B−1ρ)C⋆.(23)F_g+C_g \le(A+\ln\rho)R+\left(1+\frac{B-1}{\rho}\right)C^\star. \tag*{(23)}

This includes R=0R = 0.

Proof. First let R>0R > 0 and x=(C0−C∗)/R>1x = (C_0-C^*)/R > 1. The certificate gives F0≤(A−x/ρ)R+(B−1)C∗/ρF_0 \le(A-x/\rho)R+(B-1)C^*/\rho. Substituting into Lemma C.3 yields

Fg+Cg≤(A+1+ln⁡x−x/ρ)R+(1+B−1ρ)C∗.F_g+C_g \le(A+1+\ln x-x/\rho)R+\left(1+\frac{B-1}{\rho}\right)C^*.

The function 1+ln⁡x−x/ρ1+\ln x-x/\rho is maximized at x=ρx=\rho, where its value is ln⁡ρ\ln\rho. This proves (23) in the first case.

If R>0R>0 but C0≤C∗+RC_0\le C^*+R, monotonicity of total cost gives

Fg+Cg≤F0+C0≤AR+BρC∗+(1−1/ρ)C0≤(A+1−1/ρ)R+(1+B−1ρ)C∗.\begin{aligned} F_g+C_g &\le F_0+C_0\\ &\le AR+\frac{B}{\rho}C^*+(1-1/\rho)C_0\\ &\le(A+1-1/\rho)R+\left(1+\frac{B-1}{\rho}\right)C^*. \end{aligned}

Use 1−1/ρ≤ln⁡ρ1-1/\rho\le\ln\rho.

Finally, if R=0R=0, then w(O)=0w(O)=0 and hence O⊆S0O\subseteq S_0. Thus C0≤C∗C_0\le C^*. The same first two lines above imply

Fg+Cg≤BρC∗+(1−1/ρ)C0≤(1+B−1ρ)C∗.F_g+C_g\le\frac{B}{\rho}C^*+(1-1/\rho)C_0\le\left(1+\frac{B-1}{\rho}\right)C^*.

This case uses neither division by RR nor a logarithm of a gap.

Restoring costs and proving the approximation

Return to the fixed optimum and its good pair branch. Equations (16) and (17) supply the hypotheses of Lemma C.4 with A=1.11A=1.11 and B=1.78B=1.78. Our rational parameters satisfy

1.11+ln⁡ρ<a=1+0.78ρ,32<a<3825.(24)1.11+\ln\rho<a=1+\frac{0.78}{\rho},\qquad\frac{3}{2}<a<\frac{38}{25}. \tag*{(24)}

For completeness, set z=(ρ−1)/(ρ+1)=63/313z=(\rho-1)/(\rho+1)=63/313. The logarithm series gives

ln⁡ρ≤2(z+z33(1−z2))=600534914711000,a−111100−600534914711000=7271838875>0.\ln\rho\le2\left(z+\frac{z^3}{3(1-z^2)}\right)=\frac{6005349}{14711000},\qquad a-\frac{111}{100}-\frac{6005349}{14711000}=\frac{727}{1838875}>0.

The other comparisons in (24) are rational. It follows that

w(Sg)+Cp(Sg)≤a(R+C∗)=a(OPT−P).(25)w(S_g)+C_p(S_g)\le a(R+C^*)=a(\mathrm{OPT}-P). \tag*{(25)}

Both HH and EE remain open. If E={ℓ}E=\{\ell\}, then ℓ∉H\ell\notin H, because the seeds were opened initially, whereas ℓ\ell opened at the final overflow event. Pruning guarantees fℓ≤τf_\ell\le\tau. In either case put e=f(E)≤τe=f(E)\le\tau. The original cost is exactly

f(Sg)+Cp(Sg)=w(Sg)+Cp(Sg)+P+e.(26)f(S_g)+C_p(S_g)=w(S_g)+C_p(S_g)+P+e. \tag*{(26)}

Combining (25)–(26) and using P≥2τP\ge2\tau gives

f(Sg)+Cp(Sg)≤a(OPT−P)+P+τ=a OPT−(a−1)P+τ≤a OPT+(3−2a)τ≤a OPT.\begin{aligned} f(S_g)+C_p(S_g)&\le a(\mathrm{OPT}-P)+P+\tau\\ &=a\,\mathrm{OPT}-(a-1)P+\tau\\ &\le a\,\mathrm{OPT}+(3-2a)\tau\le a\,\mathrm{OPT}. \end{aligned}

The sign of −(a−1)-(a-1) is essential: prepaying two reference facilities creates enough slack to pay for the one exceptional facility. If an optimum uses one facility, its singleton candidate is already evaluated. Every candidate serves exactly pp clients, and selection uses original costs. If OPT =0=0, nonnegativity and the same upper bound force the output cost to be zero.

There are O(m2)O(m^2) pair branches. Each contains at most mm opening events, nn first connections, and mm greedy additions. Event times are obtained from piecewise-linear equations with slopes at most nn; all current connection costs are input distances. Appendix F gives the rational bit-complexity argument. This completes the proof of Theorem 3.1.

A finite proof of the local JMS–MYZ bound

We prove Lemma B.1 on the precise class of arrays obtained from JMS trajectories. The factor-revealing constraints and multiplier construction are due to JMS and MYZ [JMM+03, MYZ06]. We use the parameters in the 2006 version of MYZ, give the finite-size error explicitly, and justify replication for the trajectory class. This appendix is independent of a numerical LP solver.

From one run to an arbitrary star

Fix a candidate facility and a nonempty subset of kk clients. Write ff for its opening cost in this run and djd_j for its distance to client jj. Order the subset so that α1≤⋯≤αk\alpha_1 \le\cdots\le\alpha_k, breaking ties arbitrarily. For j<ij<i, let rj,ir_{j,i} be client jj's current connection distance just before clock time αi\alpha_i if αj<αi\alpha_j < \alpha_i; if αj=αi\alpha_j=\alpha_i, put rj,i=αjr_{j,i}=\alpha_j. These are auxiliary values for the star analysis, not new states of the algorithm.

The following constraints hold:

0≤α1≤⋯≤αk,dj,f,rj,i≥0,(27)0 \le\alpha_1 \le\cdots\le\alpha_k,\qquad d_j,f,r_{j,i}\ge0, \tag*{(27)}
rj,i≥rj,i+1(j<i<k),(28)r_{j,i}\ge r_{j,i+1}\qquad(j<i<k), \tag*{(28)}
αi≤rj,i+dj+di(j<i),(29)\alpha_i\le r_{j,i}+d_j+d_i\qquad(j<i), \tag*{(29)}
∑j<i(rj,i−dj)++∑j≥i(αi−dj)+≤f(1≤i≤k),(30)\sum_{j<i}(r_{j,i}-d_j)_+ + \sum_{j\ge i}(\alpha_i-d_j)_+ \le f\qquad(1\le i\le k), \tag*{(30)}
rj,i≤αj(j<i).(31)r_{j,i}\le\alpha_j\qquad(j<i). \tag*{(31)}

Current distances only decrease and never exceed the first connection budget; this proves (28) and (31), including the transition from equal to later freeze times. For (29), if jj is already assigned to an open facility hh, then client ii, still unconnected just before αi\alpha_i, has αi≤chi≤chj+dj+di\alpha_i\le c_{hi}\le c_{hj}+d_j+d_i by the metric inequality. At a tied freeze time the inequality holds because rj,i=αir_{j,i}=\alpha_i.

If the reference facility is still closed just before αi\alpha_i, the left side of (30) is its offer from this subset in that left-limit state. It is at most the offer from all clients, which cannot exceed ff before an opening event. All clients with freeze time αi\alpha_i are unconnected in this left-limit state. If the facility opened strictly earlier, already connected clients have current distance at most djd_j, and still-unconnected clients have clock at most djd_j. Every term is then zero. Zero-cost facilities fall into this second case for positive clock times; at time zero every term is zero directly. This proves the budget row. An empty subset satisfies the desired bound trivially.

We will prove that every finite array satisfying (27)–(31) obeys

∑j=1kαj≤111100f+8950∑j=1kdj.(32)\sum_{j=1}^{k}\alpha_j \le\frac{111}{100}f+\frac{89}{50}\sum_{j=1}^{k}d_j. \tag*{(32)}

The additional trajectory condition (31) is used only when reducing a small array to a large one.

Weighted budget rows

First consider an array of size N≥200000N \ge200000, with 100000100000 dividing NN. Set

p1=2251000,p2=7911000,p3=30499100000,p4=6984100000,p_1 = \frac{225}{1000}, \qquad p_2 = \frac{791}{1000}, \qquad p_3 = \frac{30499}{100000}, \qquad p_4 = \frac{6984}{100000},

and define integer breakpoints kr=prNk_r = p_rN for r=1,2,3r = 1, 2, 3, together with t=N−k3t = N - k_3, h=N−k2h = N - k_2, and q=p4Nq = p_4N. Define

si=max⁡{0,max⁡ℓ≥i(αℓ−dℓ)}.s_i = \max\left\{0,\max_{\ell\ge i}(\alpha_\ell-d_\ell)\right\}.

Then sis_i is nonnegative and nonincreasing, αi≤si+di\alpha_i \le s_i+d_i, and rj,i≥si−djr_{j,i} \ge s_i-d_j for j<ij<i. The latter follows by combining (28) with (29) for every ℓ≥i\ell\ge i; the extra candidate zero is valid because rj,i≥0r_{j,i} \ge0.

For any ℓ≥i\ell\ge i, the iith budget row implies

(ℓ−i+1)αi≤f+∑j=iℓdj−∑j<i(rj,i−dj)+.(33)(\ell-i+1)\alpha_i \le f+\sum_{j=i}^{\ell}d_j-\sum_{j<i}(r_{j,i}-d_j)_+. \tag*{(33)}

Use the following choices of ℓ\ell and row multipliers:

Row indicesℓ\ellMultiplier
1≤i≤k11 \le i \le k_1k2k_21/(k2−i+1)1/(k_2-i+1)
k1<i≤k3k_1 < i \le k_3NN1/(N−i+1)1/(N-i+1)
k3<i≤tk_3 < i \le tNN1/t1/t
t<i≤k2t < i \le k_2NNq/((N−i)(N−i+1))q/((N-i)(N-i+1))

The first two groups have left coefficient one. In the third and fourth groups, complete that coefficient to one using αi≤si+di\alpha_i \le s_i+d_i, with respective missing coefficients (i−k3−1)/t(i-k_3-1)/t and 1−q/(N−i)1-q/(N-i). Both are nonnegative. For i>k2i > k_2, use αi≤sk2+1+di\alpha_i \le s_{k_2+1}+d_i.

To bound the negative terms in (33), use

(rj,i−dj)+≥(si−2dj)+≥12si−dj(r_{j,i}-d_j)_+ \ge(s_i-2d_j)_+ \ge\frac{1}{2}s_i-d_j

in the first group, and (rj,i−dj)+≥si−2dj(r_{j,i}-d_j)_+ \ge s_i-2d_j in the next two. In the fourth group retain the stronger bound (rj,i−dj)+≥(sk2+1−2dj)+(r_{j,i}-d_j)_+ \ge(s_{k_2+1}-2d_j)_+.

Write Hb=∑i=1b1/iH_b=\sum_{i=1}^{b}1/i and H0=0H_0=0, and abbreviate

U=Hk2−Hk2−k1,V=HN−k1−Ht,U=H_{k_2}-H_{k_2-k_1}, \qquad V=H_{N-k_1}-H_t,
W=(t−k3)/t,Z=q(1/h−1/k3),ζ=U+V+W+Z.(34)W=(t-k_3)/t, \qquad Z=q(1/h-1/k_3), \qquad\zeta=U+V+W+Z. \tag*{(34)}

In the fourth group, drop negative terms for j>tj>t. For k3<j≤tk_3<j\le t, replace the retained positive part by sk2+1−2djs_{k_2+1}-2d_j. Adding the weighted rows gives

∑iαi−ζf≤∑jλj(0)dj+∑j=1k2μjsj+[h−(t−k3)Z]sk2+1−Z∑j=1k3(sk2+1−2dj)+,(35)\sum_i\alpha_i-\zeta f\le\sum_j\lambda_j^{(0)}d_j+\sum_{j=1}^{k_2}\mu_js_j+[h-(t-k_3)Z]s_{k_2+1} -Z\sum_{j=1}^{k_3}(s_{k_2+1}-2d_j)_+, \tag*{(35)}

where direct finite summation yields

λj(0)={U+2V+2W,j≤k1,U+V+HN−j−Ht+2W,k1<j≤k3,U+V+2W+2Z−1/t,k3<j≤t,U+V+W+1−q/k3,t<j≤k2,V+W+1+Z,j>k2.(36)\lambda^{(0)}_j = \begin{cases} U+2V+2W, & j\le k_1,\\ U+V+H_{N-j}-H_t+2W, & k_1<j\le k_3,\\ U+V+2W+2Z-1/t, & k_3<j\le t,\\ U+V+W+1-q/k_3, & t<j\le k_2,\\ V+W+1+Z, & j>k_2. \end{cases} \tag*{(36)}

and

μj={−(j−1)/(2(k2−j+1)),j≤k1,−(j−1)/(N−j+1),k1<j≤k3,−k3/t,k3<j≤t,1−q/(N−j),t<j≤k2.(37)\mu_j = \begin{cases} -(j-1)/(2(k_2-j+1)), & j\le k_1,\\ -(j-1)/(N-j+1), & k_1<j\le k_3,\\ -k_3/t, & k_3<j\le t,\\ 1-q/(N-j), & t<j\le k_2. \end{cases} \tag*{(37)}

For example, the first group’s distance coefficient for every j≤k2j\le k_2 is UU: rows i≤ji\le j contribute from their distance sum, and rows i>ji>j contribute from the relaxed negative offer. The other coefficients follow by the same separation of these two contributions.

Raise the third distance coefficient by 1/t1/t, which is valid because dj≥0d_j\ge0, and put λT=U+V+2W+2Z\lambda_T=U+V+2W+2Z. The bounds proved below give V≤2ZV\le2Z. Therefore, for j≤k3j\le k_3,

δj=λT−λj(0)2Z∈[0,1].\delta_j=\frac{\lambda_T-\lambda^{(0)}_j}{2Z}\in[0,1].

Apply (x−2dj)+≥δj(x−2dj)(x-2d_j)_+\ge\delta_j(x-2d_j) in the last term of (35). Every distance coefficient for j≤tj\le t becomes λT\lambda_T. The tail coefficient becomes

μk2+1=h−tZ+NV−k3+k12.(38)\mu_{k_2+1}=h-tZ+\frac{NV-k_3+k_1}{2}. \tag*{(38)}

Here the finite identity ∑j=k1+1k3(HN−j−Ht)=(N−k1)V−(k3−k1)\sum_{j=k_1+1}^{k_3}(H_{N-j}-H_t)=(N-k_1)V-(k_3-k_1) accounts for the second group. We have established

∑iαi≤ζf+∑iλidi+∑i=1k2+1μisi,(39)\sum_i\alpha_i\le\zeta f+\sum_i\lambda_i d_i+\sum_{i=1}^{k_2+1}\mu_i s_i, \tag*{(39)}

where λi=λT\lambda_i=\lambda_T for i≤ti\le t, and the last two cases of (36) give the remaining λi\lambda_i.

Nonpositive prefix sums and exact constants

Let Mb=∑i=1bμiM_b=\sum_{i=1}^{b}\mu_i. Equation (37) is nonpositive up to tt, and nonnegative from t+1t+1 to k2k_2, since q<hq<h. It is enough to check Mk2≤0M_{k_2}\le0 and Mk2+1≤0M_{k_2+1}\le0. Summing (37)–(38) gives

Mk2=−12k2U+12k1−NV+k3−k1−k3W+k2−t−q(Hk3−1−Hh−1),(40)M_{k_2}=-\frac{1}{2}k_2U+\frac{1}{2}k_1-NV+k_3-k_1-k_3W+k_2-t-q(H_{k_3-1}-H_{h-1}), \tag*{(40)}
Mk2+1=32k3−k3W−tZ−12k2U−12NV−q(Hk3−1−Hh−1).(41)M_{k_2+1}=\frac{3}{2}k_3-k_3W-tZ-\frac{1}{2}k_2U-\frac{1}{2}NV-q(H_{k_3-1}-H_{h-1}). \tag*{(41)}

In particular, the last harmonic difference has endpoints k3−1k_3-1 and h−1h-1, as required by summing 1/(N−i)1/(N-i) for t<i≤k2t<i\le k_2.

Define the corresponding continuous quantities

u=ln⁡p2p2−p1,v=ln⁡1−p11−p3,w=1−2p31−p3,z=p41−p2−p4p3,L=ln⁡p31−p2.u=\ln\frac{p_2}{p_2-p_1},\quad v=\ln\frac{1-p_1}{1-p_3},\quad w=\frac{1-2p_3}{1-p_3},\quad z=\frac{p_4}{1-p_2}-\frac{p_4}{p_3},\quad L=\ln\frac{p_3}{1-p_2}.
ExpressionLower endpointUpper endpoint
v−2zv-2z−0.101406334524-0.101406334524−0.101406334523-0.101406334523
u+v+w+zu+v+w+z1.1099840316311.1099840316311.1099840316321.109984031632
u+v+2w+2zu+v+2w+2z1.7763273782951.7763273782951.7763273782961.776327378296
u+v+w+1−p4/p3u+v+w+1-p_4/p_31.7758213522051.7758213522051.7758213522061.775821352206
v+w+1+zv+w+1+z1.7752801420661.7752801420661.7752801420671.775280142067
TbT_b−0.150379625875-0.150379625875−0.150379625874-0.150379625874
TeT_e−0.000001517538-0.000001517538−0.000001517537-0.000001517537

Table 3. Exact enclosures for the seven conditions in the finite certificate.

and

Tb=−12p1+p2+2p3−1−12p2u−v−p3w−p4L,T_b=-\frac{1}{2}p_1+p_2+2p_3-1-\frac{1}{2}p_2u-v-p_3w-p_4L,
Te=−12p2u−12v+32p3−p3w−(1−p3)z−p4L.T_e=-\frac{1}{2}p_2u-\frac{1}{2}v+\frac{3}{2}p_3-p_3w-(1-p_3)z-p_4L.

For integers n>m≥1n>m\ge1, integration of 1/x1/x gives

0≤ln⁡(n/m)−(Hn−Hm)≤1/m−1/n,Hn−1−Hm−1≥ln⁡(n/m).(42)0\le\ln(n/m)-(H_n-H_m)\le1/m-1/n,\qquad H_{n-1}-H_{m-1}\ge\ln(n/m). \tag*{(42)}

Consequently U≤uU\le u, V≤vV\le v, W=wW=w, Z=zZ=z, and

Mk2≤NTb+Eb,Eb=p12(p2−p1)+p3−p1(1−p3)(1−p1)<0.35,(43)M_{k_2}\le NT_b+E_b,\qquad E_b=\frac{p_1}{2(p_2-p_1)}+\frac{p_3-p_1}{(1-p_3)(1-p_1)}<0.35, \tag*{(43)}
Mk2+1≤NTe+Ee,Ee=p12(p2−p1)+p3−p12(1−p3)(1−p1)<0.274.(44)M_{k_2+1}\le NT_e+E_e,\qquad E_e=\frac{p_1}{2(p_2-p_1)}+\frac{p_3-p_1}{2(1-p_3)(1-p_1)}<0.274. \tag*{(44)}

Table 3 records rational interval bounds, with decimal endpoints interpreted exactly. They are certified by the following finite formula. For each rational x>1x>1, set y=(x−1)/(x+1)y=(x-1)/(x+1) and use

L48(x)=2∑j=047y2j+12j+1,L48(x)≤ln⁡x≤L48(x)+2y9797(1−y2).(45)L_{48}(x)=2\sum_{j=0}^{47}\frac{y^{2j+1}}{2j+1},\qquad L_{48}(x)\le\ln x\le L_{48}(x)+\frac{2y^{97}}{97(1-y^2)}. \tag*{(45)}

Every entry follows by rational arithmetic and outward interval propagation. Thus the numerical signs do not depend on floating-point rounding.

For every allowed N≥200000N\ge200000, the upper bounds in (43) and (44) are negative; in particular,

200000(−0.000001517537)+0.274<0.200000(-0.000001517537)+0.274<0.

All prefix sums MbM_b are therefore nonpositive. Summation by parts gives

∑i=1k2+1μisi=∑i=1k2Mi(si−si+1)+Mk2+1sk2+1≤0.\sum_{i=1}^{k_2+1}\mu_i s_i=\sum_{i=1}^{k_2}M_i(s_i-s_{i+1})+M_{k_2+1}s_{k_2+1}\le0.

The same table gives V≤v<2z=2ZV\le v<2z=2Z, ζ<1.11\zeta<1.11, and λi<1.7764<1.78\lambda_i<1.7764<1.78 for every ii. Equation (39) proves (32) for these large arrays, including zero distances and zero opening cost.

All finite star sizes

Take any kk-client array satisfying (27)–(31). Replace each client by Q=200000Q = 200000 consecutive copies, keep its α\alpha and dd values, and replace ff by QfQf. For two copies of the same original client jj, set the auxiliary r′r' value to αj\alpha_j; between copies of different original clients j<ij < i, set it to rj,ir_{j,i}.

The order and triangle constraints persist. Along a row, the transition from its own copy block to a later block is nonincreasing precisely because rj,i≤αjr_{j,i} \le\alpha_j; later transitions use (28). For a budget row inside the copy block of client ii, its earlier copies and its not-yet-counted copies together contribute exactly Q(αi−di)+Q(\alpha_i-d_i)_+. Every other block contributes QQ times its original contribution. The row is therefore at most QfQf. The enlarged array has N=Qk≥200000N = Qk \ge200000 and 100000∣N100000 \mid N. Applying the large-array bound and dividing by QQ proves (32) for every finite kk, and completes Lemma B.1. The copies exist only in this proof; the algorithm never constructs them.

Implementation and rational bit complexity

We spell out why the event description defines a polynomial-time algorithm. Assume the input costs and distances are nonnegative rationals in binary. Zero-cost facilities are opened at initialization. At any later state, offers from connected clients are fixed until an event, while an unconnected client’s offer to ii is the piecewise-linear function (t−cij)+(t-c_{ij})_+. Sorting its distance breakpoints permits exact computation of the next tightening time for each closed facility. Single-client events are found from the distances to already open facilities. The earliest eligible event is processed according to the fixed tie order, after which offers are recomputed.

Between events every relevant offer function is continuous and nondecreasing. An opening or connection does not increase any other facility’s offers: a newly connected client replaces budget tt by a distance at most tt, and a reassigned client’s distance decreases. Consequently no closed facility acquires an unprocessed offer strictly larger than its opening cost. There are at most mm openings and nn first connections in a complete run; reassignments occur within openings. As long as a client remains unconnected, a future connection or opening event exists, since the candidate set is nonempty and all distances and costs are finite.

For the bit bound, let DD be 125 times the product of all input denominators. It is a common denominator for all input distances and all scaled costs gig_i, including the factor ρ=188/125\rho= 188/125. Its bit length is at most the sum of the input denominator lengths plus a constant. Every current connection distance is an input distance. On a linear piece, a tightening time solves bt=a/Dbt = a/D with integer 1≤b≤n1 \le b \le n and an integer aa of polynomial bit length. Thus event times have polynomial bit length; denominators do not recursively accumulate previous event denominators. The other event times are input distances. Exact comparison also resolves simultaneous events and zero offers.

There are O(m2)O(m^2) pair branches and mm singleton candidates. Greedy augmentation adds at most mm facilities per branch. For any current set, each candidate marginal is obtained by updating the nn nearest-facility distances and sorting them to sum the cheapest pp. Density comparisons can be performed by cross multiplication. All sums, comparisons, and branch evaluations have polynomial bit complexity. This proves the running-time claim without an oracle for continuous optimization or logarithms.

Same-run local interface for squared costs

Fix a full A2/JMS run, a comparison facility hh, and any nonempty client subset, sorted by its frozen prices. Write dj=chjd_j = c_{hj} and f=ghf = g_h. For equal frozen prices set rjl=αjr_{jl} = \alpha_j; otherwise use the connection cost of jj just before the entire timestamp αl\alpha_l. Then

αl≤αl+1,0≤rjl≤αj,rjl≥rj,l+1,(46)\alpha_l \le\alpha_{l+1}, \qquad0 \le r_{jl} \le\alpha_j,\qquad r_{jl} \ge r_{j,l+1}, \tag*{(46)}
αl≤rjl+dj+dl,(47)\sqrt{\alpha_l} \le\sqrt{r_{jl}}+\sqrt{d_j}+\sqrt{d_l}, \tag*{(47)}
∑j<l(rjl−dj)++∑j≥l(αl−dj)+≤f.(48)\sum_{j<l}(r_{jl}-d_j)_+ + \sum_{j\ge l}(\alpha_l-d_j)_+ \le f. \tag*{(48)}

To prove (47) for unequal prices, jj is connected to an already open facility aa, while ll remains active; hence αl≤cal\alpha_l \le c_{al} and the squared three-hop inequality applies through j,hj,h. Equal prices are immediate. For (48), unopened facilities receive offers at most their fees; restricting to a client subset only drops nonnegative terms. If hh is open, all these positive parts vanish. Equal-price auxiliary variables reproduce the left-limit offers, not post-event distances.

Lemma G.1 (Finite transfer to a fixed-dimensional certificate). Fix k≥2k \ge2. Let UP⁡(k)\operatorname{UP}(k) consist of (46), (47), nonnegativity, and the budgets

∑a<b(rab−da)++∑a>b(αb−da)+≤f.\sum_{a<b}(r_{ab}-d_a)_+ + \sum_{a>b}(\alpha_b-d_a)_+ \le f.

If every point in this system satisfies ∑b=1kαb≤Af+B∑b=1kdb\sum_{b=1}^{k}\alpha_b \le Af+B\sum_{b=1}^{k}d_b, then the same local inequality holds for every finite subset of every full A2A2 trajectory.

Proof. For a subset of size nn, replicate each client kk times consecutively, keeping its α,d\alpha,d and multiplying ff by kk. Between copies of the same client put r=αr=\alpha; between distinct originals keep the original rr. The cap rjl≤αjr_{jl}\le\alpha_j ensures monotonicity at a replication boundary. Every budget is exactly kk times the original budget.

Partition the resulting knkn entries into kk consecutive blocks of size nn. Average α,d\alpha,d over their blocks, rr over each pair of blocks, and divide the replicated ff by nn. The ordering constraints and cap survive averaging. The function

G(x,y,z)=x+y+z+2xy+2xz+2yzG(x,y,z)=x+y+z+2\sqrt{xy}+2\sqrt{xz}+2\sqrt{yz}

is concave on the nonnegative orthant, so Jensen preserves (47). For each block, omit all within-block terms in (48), average the remaining rows and divide by nn. Convexity of the positive-part function yields precisely the displayed UP⁡\operatorname{UP} budget. Every objective total has been multiplied by the same k/nk/n, proving the claim. If all dd vanish in the original nn-client system, (47) and its last budget directly give f≥nαn≥∑αf\ge n\alpha_n\ge\sum\alpha; no normalization by zero is needed.

Exact finite-certificate protocol

For positive integers u,v,wu,v,w and q=u+v+wq=u+v+w, squared three-hop constraints imply the rational row

αl−qurjl−qvdl−qwdj≤0.\alpha_l-\frac{q}{u}r_{jl}-\frac{q}{v}d_l-\frac{q}{w}d_j\le0.

by weighted Cauchy–Schwarz. Other valid rows are ordering, caps, and any subset expansion of a UP⁡\operatorname{UP} budget. More generally, for 0≤ej≤h0\le e_j\le h, a weighted budget row is valid:

∑j<lej(rjl−dj)+∑j>lej(αl−dj)−hf≤0.\sum_{j<l}e_j(r_{jl}-d_j)+\sum_{j>l}e_j(\alpha_l-d_j)-hf\le0.

Indeed each signed term is at most its positive part, and their weighted sum is at most hh times the full positive-part budget. A finite list of nonnegative rational row multipliers is summed using exact fraction arithmetic. To repair rounding deficits, write D=∑djD = \sum d_j. The full UP constraints imply rjl≤f+dj≤f+Dr_{jl} \le f + d_j \le f + D, α1≤f+d2\alpha_1 \le f + d_2, and, for l>1l > 1,

αl≤3r1l+3d1+3dl≤3f+6D.\alpha_l \le3r_{1l} + 3d_1 + 3d_l \le3f + 6D.

Hence all α\alpha and rr variables are bounded by 3f+6D3f + 6D. A column deficit ϵ\epsilon can be paid by the valid row ϵ(v−3f−6D)≤0\epsilon(v - 3f - 6D) \le0. After adding every such row, require all α\alpha coefficients to be at least one and all rr coefficients nonnegative. The exact negative facility coefficient and the largest negative distance coefficient give certified A,BA, B. No solver tolerance is discarded. The independent verifier rebuilds the rows, rather than trusting a stored solver status or objective.

Lemma H.1 (Independently certified numerical inequality). Every feasible point of UP(400)(400) satisfies

∑j=1400αj≤290000000783200000000000f+850791523903250000000000∑j=1400dj.\sum_{j=1}^{400} \alpha_j \le\frac{290000000783}{200000000000}f + \frac{850791523903}{250000000000}\sum_{j=1}^{400} d_j.

Consequently the same-run local certificate holds with the simpler constants A=145001/100000=1.45001A = 145001/100000 = 1.45001 and B=2127/625=3.4032B = 2127/625 = 3.4032.

Proof. The supplementary file square-k400-certificate.json.gz contains 123414 nonnegative rational weighted rows: 363 α\alpha monotonicity rows, 75746 rr monotonicity rows, 46954 weighted-Cauchy rows, and 351 weighted budget rows. The independent standard-library verifier reconstructs every row and checks all 80601 columns. There are no cap rows. Upward-rounded repairs on 342 α\alpha columns have total weight 261/200000000000; there are no rr deficits. Adding the valid residual-payment rows described above and rounding the distance coefficient upward gives precisely the displayed inequality. Thus no floating tolerance or solver objective is used as proof. The finite-transfer lemma then applies to every client-subset size.

Proof data. The accompanying supplementary files contain the certificate, verify_square_certificate.py, and instructions for replaying the exact check using only the Python standard library. The certificate records rational row multipliers; the verifier reconstructs and sums the rows and pays all residual column deficits by the bounds proved above. These files are part of the finite numerical proof of Lemma 5.1. The mathematical derivation of each allowed row family is given here.

References

  1. [1]Moses Charikar, Samir Khuller, David M. Mount, and Giri Narasimhan. Algorithms for facility location problems with outliers. In Proceedings of the Twelfth Annual ACM–SIAM Symposium on Discrete Algorithms (SODA), pages 642–651, 2001. Author version.DOI
  2. [2]Rajni Dabas, Samir Khuller, and Emilie Rivkin. Serving clients fairly: On facility location and k-median with fair outliers. In 7th Symposium on Foundations of Responsible Computing (FORC 2026), volume 368 of LIPIcs, pages 9:1–9:19, 2026. doi:10.4230/LIPIcs.FORC.2026.9.DOI
  3. [3]Cristina G. Fernandes, Luis A. A. Meira, Flavio K. Miyazawa, and Lehilton L. C. Pedrosa. A systematic approach to bound factor-revealing LPs and its application to the metric and squared metric facility location problems. Mathematical Programming, 153:655–685, 2015. doi:10.1007/s10107-014-0821-x. The constraint numbering used here follows the author version, arXiv:1111.1672v3, 2013.DOI
  4. [5]Hang Luo, Lu Han, Tianping Shuai, and Fengmin Wang. Approximation and heuristic algorithms for the priority facility location problem with outliers. Tsinghua Science and Technology, 29(6):1694–1702, 2024. doi:10.26599/TST.2023.9010152.DOI
  5. [6]Mohammad Mahdian, Yinyu Ye, and Jiawei Zhang. Approximation algorithms for metric facility location problems. SIAM Journal on Computing, 36(2):411–432, 2006. doi:10.1137/S0097539703435716. The local numerical certificate follows Appendix A of the 2006 author version, https://web.stanford.edu/~yyye/myz-final.pdf.DOI
  6. [7]Jianfeng Ren and Xiaoyun Tian. Squared metric facility location problem with outliers. Operations Research Transactions, 25(1):114–122, 2021. In Chinese. doi:10.15960/j.cnki.issn.1007-6093.2021.01.011.
  7. [8]Li Zhang, Jing Yuan, and Qiaoliang Li. An approximation algorithm for k-level squared metric facility location problem with outliers. Optimization Letters, 19:139–149, 2025. Published online 4 April 2024. doi:10.1007/s11590-024-02107-y.

Paper details

vlnc:W_6fynrcy4
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents