Facility Location Problems with Capacity Constraints: Two Facilities and Beyond

There is a credible continuous mirror, but it is concentrated in the paper’s second framework: two capacitated facilities with abundant capacity. I would not try to continuize every theorem. The strongest case is for the Extended InnerGap mechanism and its Maximum Cost guarantee.

The paper has no named NP-hardness, membership-in-\(\mathrm{P}\), or parameterized-complexity theorem. Its relevant named computational results are mechanism-design and approximation theorems, proved in this paper: Theorems 8–10, together with Mechanism 3.

The mirror is the following. A type is a location \(q_t\) on the line, with all agents of that type having the same distance cost \(d(q_t,y)=|q_t-y|\). An instance is \(T=\{q_1<\cdots<q_\tau\}\subseteq\mathbb{Q}\), a rational mass vector \(\mu\in\mathbb{Q}^{\tau}\) with \(\sum_t\mu_t=1\), and two rational capacity fractions \(\kappa_1,\kappa_2\) satisfying \(1/2\le \kappa_i<1\) and \(\kappa_1+\kappa_2\ge1\). Thus \(\mu_t\) is the fraction of the population at location type \(q_t\), while \(\kappa_i\) is facility \(i\)’s capacity as a fraction of the population.

This is a natural high-multiplicity regime for two large service centres, clinics, warehouses, or servers along a corridor. There may be millions of residents or jobs, but only \(\tau\) relevant location classes—say neighbourhoods, industrial zones, or postcode cells—with \(\tau\ll N\). A rational instance \(\mu_t=N_t/N\) is exactly the finite election-style clone population in which \(N_t\) agents share type \(q_t\). The facilities, capacities, absolute-distance costs, and assignment problem are unchanged; only the population representation has become mass.

Let \(Q_\mu\) be the quantile function of the reported distribution, and put \(\bar\kappa=\max\{\kappa_1,\kappa_2\}\), \(a=Q_\mu(1-\bar\kappa)\), \(b=Q_\mu(\bar\kappa)\), and \(z=(a+b)/2\). Define \(\ell=\mu([a,z])\) and \(r=\mu((z,b])\), splitting atoms at a cut only as bookkeeping when necessary. The continuous Extended InnerGap rule places the larger-capacity facility at \(a\) when \(\ell\ge r\), and at \(b\) otherwise. Every type mass is assigned to its nearer facility, with mass at a tie split to satisfy capacities.

Formally, an output is facility locations \(y_1,y_2\), a capacity assignment \(\pi\), and mass flows \(\rho_{tj}\) satisfying \(\sum_j\rho_{tj}=\mu_t\), \(\sum_t\rho_{tj}\le\kappa_{\pi(j)}\), and \(\rho_{tj}>0\) only when \(j\) is a nearest facility for \(q_t\). Its costs are \(\mathrm{SC}=\sum_{t,j}\rho_{tj}|q_t-y_j|\) and \(\mathrm{MC}=\max_{\rho_{tj}>0}|q_t-y_j|\).

My lead anchor is the MC part of Theorem 9, proved in this paper: “\(\mathrm{ar}_{MC}(\mathrm{EIG})=2\).” The corresponding problem is:

“Given \((T,\mu,\kappa_1,\kappa_2)\), compute the continuous EIG outcome and determine its approximation ratio against the optimal feasible two-facility mass assignment, where the optimum is \(\mathrm{OPT}_{MC}(\mu)=\min_{y,\pi,\rho}\max_{\rho_{tj}>0}|q_t-y_j|\).”

A solution consists of the EIG output, an optimal benchmark, and a proof that \(\mathrm{MC}_{EIG}(\mu)\le2\,\mathrm{OPT}_{MC}(\mu)\), together with a family approaching equality. I expect this to be Class A. Quantiles and the EIG rule are computable by sorting the \(\tau\) types and scanning cumulative masses. The optimal benchmark is a constant-facility interval-covering and capacitated-flow problem on a line, so it should also be solvable in time polynomial in \(\tau\) and the encoding length. The population multiplicity has disappeared without removing the paper’s actual facility-location question.

The second anchor is Theorem 8, also proved here: “The EIG is strong GSP, hence truthful.” Its continuous problem is the following mechanism-design version. Given \(T,\kappa_1,\kappa_2\), construct a deterministic direct rule \(F\) mapping every rational reported mass distribution \(\hat\mu\) to a feasible pair of facilities and an assignment flow, such that no positive-mass coalition can replace its true subdistribution \(\eta\le\mu\) by another reported subdistribution and make every coalition member weakly better off while making a positive-mass subset strictly better off.

This is the non-vacuous continuum analogue of group strategyproofness. An individual atomless agent has zero influence on \(\mu\), so individual truthfulness alone would be vacuous; positive-mass coalition deviations retain the strategic content. For rational masses, the instance can be replicated into \(N\) clones, and the quantile rule is exactly the finite EIG rule up to tie bookkeeping. The paper’s threshold-crossing proof should therefore extend to this mass formulation. This is again expected Class A: the mechanism is explicitly computable, and the proof depends on the two quantile boundaries rather than on indivisibility of named agents.

A third, supporting anchor is the MC part of Theorem 10, proved in the paper, which states that every truthful deterministic mechanism has approximation ratio at least \(2\). The continuous question is to determine

\[ \inf_F\sup_\mu \frac{\mathrm{MC}_F(\mu)}{\mathrm{OPT}_{MC}(\mu)} \]

over deterministic, clone-consistent truthful mass mechanisms for the same two-capacity regime. Here “clone-consistent” means that rational mass vectors represent replicated finite populations and the rule respects that high-multiplicity interpretation. The expected answer is exactly \(2\): Theorem 10 supplies the lower bound, while Theorem 9 supplies the matching EIG upper bound. The finite lower-bound construction moves a boundary agent; in the clone limit this becomes a vanishing mass perturbation, while the ratio remains \(2\). This is a fully solved Class A characterization, not a claim of continuum-specific hardness.

I would deliberately not anchor on the paper’s Social Cost formula in Theorem 9. Its bound contains the raw population parameter \(n\), and its behaviour under normalization and passage to arbitrary mass distributions is less clean. Nor would I claim that Theorems 1–7 automatically transfer: the \(m\)-facility PMM/PIPM construction requires a more careful quantile-block formulation. The mirror above covers Mechanism 3 and the MC portions of Theorems 8–10 emphatically.

The weakest point is the strategic one. In a genuinely atomless population, unilateral truthfulness becomes trivial, and positive-mass group strategyproofness is not literally the same quantifier as the paper’s finite-agent notion. The defence is that this is precisely what the high-multiplicity bridge requires: finite rational masses are clone populations, and the continuous rule is the limit object whose quantile inequalities govern all those finite instances. A referee could reasonably demand a formal clone-consistency definition and a proof that Theorem 8 survives fractional coalition masses. That is a real obligation, but it is a technical boundary of the mirror, not evidence that the underlying facility-location problem has ceased to be the same problem.