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 for metric facility location with outliers, strictly less than for priority facility location with outliers, and 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 , the objective is to minimize these two costs while serving at least clients. With nonnegative costs, an optimum can be chosen to serve exactly .
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
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:
Metric facility location with outliers, with approximation factor .
Priority metric facility location with outliers, with approximation factor strictly less than .
Squared-metric facility location with outliers, with approximation factor .
Each algorithm connects exactly 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.
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 , let be the cost of connecting the cheapest 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 be their total original cost and put . Here and are the opening and connection components of that optimum. After truncation, exempt at most additional facilities and let denote the opening costs with seeds and exceptions set to zero. For the initial facility set and constants , , , the required certificate is
The coefficients , measure the initializer’s losses, and weights its opening cost. For a JMS prefix, the retained clients have the 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, 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 and integrating the remaining deficit gives . 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 satisfying
This is the step that lets a changing served set inherit an opening/connection tradeoff.
Restore the unpaid costs. When seeds are the most expensive optimum facilities, pruning more expensive nonseeds makes each exception cost at most , the cheapest seed cost. Thus . If both coefficients in (2) are at most , restoring original costs gives
The condition 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 exceptions and 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 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 , 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 be a finite facility set with nonnegative opening costs . A feasible open set has service cost . We assume that adding facilities preserves feasibility and that is polynomial-time computable, nonincreasing, and supermodular on supersets of a feasible initial set. In diminishing-savings notation, this means
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 , with minimum when the set is empty. Let be the sum of the smallest . A set is feasible precisely when at least of these values are finite. The function is computed by scanning eligible edges and sorting. For ,
Each is a union of fixed neighborhoods. The marginal gain in capped coverage decreases when grows. Integrating gives supermodularity of ; on feasible supersets the integral is finite. The proof uses neither triangle inequalities nor complete eligibility.
Seeds, exceptions, and the certificate. Fix integers and . For each -element seed set , retain
An initializer either discards the branch or returns a feasible and with . Set on and elsewhere, and include every zero- facility in . Starting at , repeatedly add an unopened facility maximizing whenever this ratio exceeds one. All unopened facilities have positive . Evaluate every output using , and also evaluate every feasible facility set of size less than .
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 . Fix and
For a fixed optimum of size at least , suppose its most expensive facilities define a nondiscarded branch in which remains feasible and the initializer satisfies
If , this algorithm is an -approximation, in polynomial time for fixed . The conclusion also holds with any larger satisfying these inequalities.
Proof. If , direct enumeration finds an optimum. Otherwise work in its good seed branch and put . Since some reference facilities may also be exempted, . Supermodularity and monotonicity give
If , the best density is at least . For a step costing and reducing the gap to , therefore . Summing steps above by integration gives a logarithm. If the first crossing moves from to , combine its opening cost with the remaining gap:
A crossing exists because there are finitely many additions and greedy cannot stop above the threshold. Later additions reduce the total accounted cost. Writing and yields
when , and at most otherwise. Substitute (4) and maximize over . Its maximum is , attained at (or approached at the endpoint when ). The other case uses . This proves
For , all reference facilities have zero accounted cost and belong to , so . Substitution into gives the same bound. Appendix C gives the full discrete calculation.
Restoring and adds at most , while . Hence
The number of seed branches and direct candidates is polynomial for fixed ; there are at most 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:
| Model | Seeds | Exceptions | |||
| Metric | 1.11 | 1.78 | 188/125 | 2 | 1 |
| Priority | 1 | 3 | 1173/500 | 2 | 1 |
| Squared metric | 1.45001 | 3.4032 | 20543/10000 | 1 | 1 |
Table 1 (PDF p. 6).
The coefficient 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 be finite facility and client sets, with metric connection costs and quota . Return the empty solution for . For , use two seeds, enumerate singleton solutions as well, and set on and elsewhere, where .
Growth and truncation. Run reassigning JMS on the pruned candidate set. An unconnected client’s budget grows with time. Its budget freezes at first connection; a connected client’s current distance can decrease through reassignment. A closed facility receives offers from unconnected clients and 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 clients, remove any excess only from the newly connected batch. Let be the retained clients, the open facilities, and the final opening facility when deletion was needed, or the empty set otherwise. Keep open. Set on and elsewhere, then run the common augmentation procedure. Appendix A specifies all event rules.
A local budget comparison. For every facility and every client subset of the same complete JMS run,
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 consists of smallest frozen budgets in that continuation. Applying (6) to the reference optimum’s assignment groups gives
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 and the final facility is , their deleted opening contributions sum to
Subtracting their budgets and connections from the event identity gives . Exempting and choosing the cheapest clients therefore yields
The same inequality follows directly when there is no deletion. In the good seed branch, and . This is exactly the transfer certificate with , , , .
Theorem 3.1. Metric facility location with outliers has a deterministic polynomial-time 571/376-approximation serving exactly clients.
Proof. For , put . The exact comparisons are
For example, with , the positive series for the logarithm gives ; its gap to is . The transfer theorem applies with . 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 has level , and client requires . An edge is eligible when ; 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 OPT, where
It respects the exact service quota and returns zero cost when .
Proof. For return the empty solution. Enumerate all single-facility candidates and all pairs . For a pair put , , and retain and all facilities of original price at most . Discard a branch if fewer than clients have any eligible facility. Set , on , and otherwise.
Growth and exact-quota truncation. Open all zero- facilities at time zero. Unfrozen client prices grow with the common clock; frozen prices stay fixed. On an eligible edge put , 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 , remove excess clients only from the final event’s newly frozen clients. Let be the retained clients and 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, . 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 have smallest stopping prices, including ties. Consequently every eligible comparison solution serving clients at cost satisfies
This is valid even when the comparison clients differ from .
Cleanup and legal reassignment. Let 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 . A client supports at most one member of . For set if such exists; otherwise use . In both cases the two components sum to .
Put and set on , otherwise. Every positive contributor of a facility opened before the final event froze before that event and remains in . Thus each paid member of is completely funded by . Disjoint supports imply
A positive contributor to connects directly at cost . Otherwise let witness the first freezing of . Its opening time obeys and . If was discarded, a retained facility of level shares a positive contributor . This contributor froze by , so
The metric path gives , and is eligible for . The level order of cleanup is what guarantees eligibility. If connect directly. Therefore
Combining the two payments and the comparison price bound, for ,
Applying the transfer theorem. Choose the branch whose seeds are the two most expensive facilities of a fixed optimum. All optimal facilities survive, , and . Theorem 2.1, with , , gives
Every zero- facility is initially included. The case is included in that theorem. For , the positive logarithmic series gives
Also and . The exception has original price , so restoring original fees gives
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 branches, at most growth events and greedy additions per branch. Between distance breakpoints the growth contribution is affine with integer slope at most . Event times require rational operations and division by such an integer; common denominator bit length grows by at most 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 , for every candidate facility and every client subset ,
Proof overview. Order by frozen price and put . The same-run constraints are monotonicity of prices and reassignment distances, a local offer budget, and
These are the squared-metric factor-revealing constraints of [3]. For arbitrary , replicate every client times and divide the resulting sequence into equal blocks. Averaging preserves the budget by convexity of the positive-part function and preserves the triangle constraint by concavity of . Thus a fixed-size upper-bound program controls every subset size.
For , a rational nonnegative combination of valid rows yields coefficients 1.450000003915 and 3.403166095612, which are bounded by the stated . 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 , keeping all facilities of original fee at most . Set and otherwise, with . 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
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 -approximation serving exactly clients.
Proof. Let and . Exact rational comparison gives
The first expression bounds from above. Since , a single seed absorbs the one exception: for . 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 and be finite facility and client sets, with and . Facility has opening cost . Facilities and clients lie in a common metric space; denotes their distance, and distinct input objects may be colocated. All distances are finite. The integer quota satisfies . For , the algorithm returns the empty solution, so assume below.
For nonempty , define
Sorting the distances computes and a served set attaining it. Write for any facility-cost vector . Fix
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 with fixed nonnegative opening costs . Let be the open facilities, the connected clients, and the clock. An unconnected client has budget . Its budget freezes when it first connects. A connected client has a current assigned distance , which can decrease after reassignment. Its frozen budget and current distance must be kept distinct.
Initially, open every zero- facility and set at time zero. An unconnected client does not connect to a positive-distance facility merely because that facility is free. For each closed facility , client offers
Advance the clock until an event is possible, and process events as follows.
When for a closed facility, open it and connect or reassign every client with a strictly positive offer. Newly connected clients freeze at ; all clients assigned in this event receive current distance .
When an unconnected client satisfies for an open facility, connect that client and freeze its budget at .
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 .
Let be the stopping time and the open set. If , set and . Otherwise the last event opened a facility . Remove exactly clients from that event’s newly connected batch, and call the retained set . Set . The facility remains open.
Enumeration and augmentation
For each pair , set
| Cost | Meaning | Definition in a pair branch |
| Original opening cost | Input; used to select the output | |
| JMS opening cost | 0 on , and elsewhere | |
| Augmentation cost | 0 on , and 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 with costs for and otherwise. After it returns , fix residual costs for and otherwise. Every zero- facility is already in : zero original costs and seeds were opened initially, and .
Starting from , repeatedly add a facility in of maximum density if that density exceeds one. The denominator is positive for every unopened candidate. At each step, is recomputed over all clients. The set from the prefix proof is not held fixed during augmentation.
Algorithm 1: Exact-quota facility location.
Evaluate each singleton facility set, serving its cheapest clients.
For each pair , form and , run the quota prefix to obtain , and fix . Run maximum-density augmentation from , reselecting clients through , to obtain .
Return the candidate minimizing , with a served set attaining .
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 , and let be its frozen budgets. For every candidate facility and every client subset ,
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,
Proof. The identity holds at time zero. A single-client event adds its connection distance to both sides. At an opening of , let be the newly connected clients and the reassigned old clients. Tightness gives
The increase in the left side of (12) is consequently . This is exactly the increase in frozen budgets.
Lemma B.3 (One exceptional opening). Let be any quota prefix. If is a reference facility set with an assignment of clients of connection cost in the same candidate instance, then
Proof. Continue the original state to a complete JMS run, before removing clients or changing any costs. Put . Every client connected before time is retained. Clients removed at time have budget , and still-unconnected clients eventually freeze at a time at least . Thus is a set of smallest complete-run budgets. If is the reference client set, Lemma B.1, applied to its disjoint assignment groups, gives
Unused reference facilities only add nonnegative cost on the right.
All connection distances in the following accounting refer to the stopping state, denoted by , rather than to the complete continuation. If no clients are removed, Lemma B.2 and prove the claim. Otherwise let be the removed clients and the last facility. Each first connects in this event, so its budget is and its distance is . Define its total opening contribution by
These are a subset of the nonnegative contributions opening , including any savings from old clients. Hence . Removing the clients’ budgets and distances from (12) gives
Keeping open and reselecting the cheapest clients now yields
Combine this with (14).
The reference solution in a good branch
Fix one optimum throughout the analysis, with facilities , served clients , and opening and connection costs . In particular, ; need not be the smallest connection cost among all feasible facility sets. Suppose and let be its two most expensive facilities. They define a branch of the enumeration. Every facility of remains in .
Define the fixed residual reference budget and the algorithm’s initial costs by
The quantity belongs to the reference solution and does not change during augmentation. In contrast, is the algorithm’s cost before augmentation. Since and , Lemma B.3 gives the initialization certificate
Moreover,
The possible inequality is useful: is an upper bound on the reference opening cost under , not a definition of that cost.
Greedy augmentation with changing clients
Throughout this section the residual costs and the eligibility relation are fixed. The argument applies to any feasible initial set, including the priority model. All zero- facilities are in a nonempty initial set . Let and , and write and for the final costs. In particular, is the sum of the additional opening costs, rather than itself.
A comparison at the same current set
Lemma C.1 (Reselection is supermodular). The function is nonincreasing. For feasible and , we have .
Proof. For a cost threshold , let and . The cheapest distances satisfy
Indeed, the number of these distances exceeding is . This remains true at ties, which do not affect the integral. On supersets of a feasible initial set, the smallest distances are finite, so the integrand eventually vanishes.
Let . Adding increases by
Both arguments of this minimum can only decrease when grows. Thus is submodular, and integrating its marginal gains proves the claimed inequality. Monotonicity follows directly from (7).
No metric property was used here. The point is that the client set is already optimized inside , so this argument permits a different served set after each facility addition.
Corollary C.2 (Reference marginal bound). If a facility set admits a service assignment of clients with connection cost at most , then, for every feasible ,
Proof. Add the facilities of one at a time. Their successive savings telescope to . Each is at most the corresponding saving measured at the original set , by Lemma C.1. The union can use the reference assignment, giving the second inequality.
The discrete threshold crossing
Assume for the reference set in Corollary C.2. For now suppose . If the current connection cost exceeds , some unopened reference facility has density at least . To see this, combine (19) with and use a weighted average; every unopened facility has positive cost. Therefore greedy cannot stop above this threshold. If the chosen facility costs and the new connection cost is , then
Lemma C.3 (Cumulative augmentation cost). If and , then
If , then .
Proof. Write . For a step staying above the threshold, with , equation (20) gives
There are finitely many additions, and the algorithm cannot stop with . Thus, when , a first crossing exists. Denote the gap just before it by , and just after it by . Integrating over all preceding steps bounds their total opening cost by .
The crossing step needs a separate bound because may be zero or negative. Using (20) and , its opening cost satisfies
We combine with , not with the full remaining connection cost. The latter is . At the crossing, total cost is therefore at most
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 leaves a smaller allowable , and this compensates for a longer augmentation phase.
Lemma C.4 (From initialization to final cost). Suppose , , and
With the reference assumptions above, including , greedy returns
This includes .
Proof. First let and . The certificate gives . Substituting into Lemma C.3 yields
The function is maximized at , where its value is . This proves (23) in the first case.
If but , monotonicity of total cost gives
Use .
Finally, if , then and hence . Thus . The same first two lines above imply
This case uses neither division by 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 and . Our rational parameters satisfy
For completeness, set . The logarithm series gives
The other comparisons in (24) are rational. It follows that
Both and remain open. If , then , because the seeds were opened initially, whereas opened at the final overflow event. Pruning guarantees . In either case put . The original cost is exactly
Combining (25)–(26) and using gives
The sign of 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 clients, and selection uses original costs. If OPT , nonnegativity and the same upper bound force the output cost to be zero.
There are pair branches. Each contains at most opening events, first connections, and greedy additions. Event times are obtained from piecewise-linear equations with slopes at most ; 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 clients. Write for its opening cost in this run and for its distance to client . Order the subset so that , breaking ties arbitrarily. For , let be client 's current connection distance just before clock time if ; if , put . These are auxiliary values for the star analysis, not new states of the algorithm.
The following constraints hold:
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 is already assigned to an open facility , then client , still unconnected just before , has by the metric inequality. At a tied freeze time the inequality holds because .
If the reference facility is still closed just before , 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 before an opening event. All clients with freeze time are unconnected in this left-limit state. If the facility opened strictly earlier, already connected clients have current distance at most , and still-unconnected clients have clock at most . 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
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 , with dividing . Set
and define integer breakpoints for , together with , , and . Define
Then is nonnegative and nonincreasing, , and for . The latter follows by combining (28) with (29) for every ; the extra candidate zero is valid because .
For any , the th budget row implies
Use the following choices of and row multipliers:
| Row indices | Multiplier | |
The first two groups have left coefficient one. In the third and fourth groups, complete that coefficient to one using , with respective missing coefficients and . Both are nonnegative. For , use .
To bound the negative terms in (33), use
in the first group, and in the next two. In the fourth group retain the stronger bound .
Write and , and abbreviate
In the fourth group, drop negative terms for . For , replace the retained positive part by . Adding the weighted rows gives
where direct finite summation yields
and
For example, the first group’s distance coefficient for every is : rows contribute from their distance sum, and rows contribute from the relaxed negative offer. The other coefficients follow by the same separation of these two contributions.
Raise the third distance coefficient by , which is valid because , and put . The bounds proved below give . Therefore, for ,
Apply in the last term of (35). Every distance coefficient for becomes . The tail coefficient becomes
Here the finite identity accounts for the second group. We have established
where for , and the last two cases of (36) give the remaining .
Nonpositive prefix sums and exact constants
Let . Equation (37) is nonpositive up to , and nonnegative from to , since . It is enough to check and . Summing (37)–(38) gives
In particular, the last harmonic difference has endpoints and , as required by summing for .
Define the corresponding continuous quantities
| Expression | Lower endpoint | Upper endpoint |
Table 3. Exact enclosures for the seven conditions in the finite certificate.
and
For integers , integration of gives
Consequently , , , , and
Table 3 records rational interval bounds, with decimal endpoints interpreted exactly. They are certified by the following finite formula. For each rational , set and use
Every entry follows by rational arithmetic and outward interval propagation. Thus the numerical signs do not depend on floating-point rounding.
For every allowed , the upper bounds in (43) and (44) are negative; in particular,
All prefix sums are therefore nonpositive. Summation by parts gives
The same table gives , , and for every . Equation (39) proves (32) for these large arrays, including zero distances and zero opening cost.
All finite star sizes
Take any -client array satisfying (27)–(31). Replace each client by consecutive copies, keep its and values, and replace by . For two copies of the same original client , set the auxiliary value to ; between copies of different original clients , set it to .
The order and triangle constraints persist. Along a row, the transition from its own copy block to a later block is nonincreasing precisely because ; later transitions use (28). For a budget row inside the copy block of client , its earlier copies and its not-yet-counted copies together contribute exactly . Every other block contributes times its original contribution. The row is therefore at most . The enlarged array has and . Applying the large-array bound and dividing by proves (32) for every finite , 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 is the piecewise-linear function . 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 by a distance at most , 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 openings and 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 be 125 times the product of all input denominators. It is a common denominator for all input distances and all scaled costs , including the factor . 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 with integer and an integer 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 pair branches and singleton candidates. Greedy augmentation adds at most facilities per branch. For any current set, each candidate marginal is obtained by updating the nearest-facility distances and sorting them to sum the cheapest . 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 , and any nonempty client subset, sorted by its frozen prices. Write and . For equal frozen prices set ; otherwise use the connection cost of just before the entire timestamp . Then
To prove (47) for unequal prices, is connected to an already open facility , while remains active; hence and the squared three-hop inequality applies through . Equal prices are immediate. For (48), unopened facilities receive offers at most their fees; restricting to a client subset only drops nonnegative terms. If 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 . Let consist of (46), (47), nonnegativity, and the budgets
If every point in this system satisfies , then the same local inequality holds for every finite subset of every full trajectory.
Proof. For a subset of size , replicate each client times consecutively, keeping its and multiplying by . Between copies of the same client put ; between distinct originals keep the original . The cap ensures monotonicity at a replication boundary. Every budget is exactly times the original budget.
Partition the resulting entries into consecutive blocks of size . Average over their blocks, over each pair of blocks, and divide the replicated by . The ordering constraints and cap survive averaging. The function
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 . Convexity of the positive-part function yields precisely the displayed budget. Every objective total has been multiplied by the same , proving the claim. If all vanish in the original -client system, (47) and its last budget directly give ; no normalization by zero is needed.
Exact finite-certificate protocol
For positive integers and , squared three-hop constraints imply the rational row
by weighted Cauchy–Schwarz. Other valid rows are ordering, caps, and any subset expansion of a budget. More generally, for , a weighted budget row is valid:
Indeed each signed term is at most its positive part, and their weighted sum is at most 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 . The full UP constraints imply , , and, for ,
Hence all and variables are bounded by . A column deficit can be paid by the valid row . After adding every such row, require all coefficients to be at least one and all coefficients nonnegative. The exact negative facility coefficient and the largest negative distance coefficient give certified . 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 satisfies
Consequently the same-run local certificate holds with the simpler constants and .
Proof. The supplementary file square-k400-certificate.json.gz contains 123414 nonnegative rational weighted rows: 363 monotonicity rows, 75746 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 columns have total weight 261/200000000000; there are no 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]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]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]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
- [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
- [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
- [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.
- [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.