Answer: \(\mathrm{FP}\); \(\sup_I\min_{A\in F}R_I(A)=\beta_3=(3+\sqrt{5})/2\)
Theorem 3.4 — class: algorithmic
Given explicit finite facilities F, finite complete client types T with rational distances d(t,A), rational mass distribution μ, and rational 0<λ<ρ≤1, output a facility A minimizing the maximum of Cλμ(A)/OPTλ and Cρμ(A)/OPTρ, where Cθμ(A) is the total distance of the worst θ mass and OPTθ is its minimum over F; determine the tight worst-case guarantee f(ρ/λ).
Let \(T\cup F\) be a finite metric space with an explicitly given rational distance matrix, and let \(\mu\in\Delta(T)\cap\mathbb{Q}^{T}\). For rational \(0<\lambda_1<\lambda_2<\lambda_3\leq1\), define \(C^\mu_\lambda(A)=\max\{\sum_{t\in T}z_t d(t,A):0\leq z_t\leq\mu_t,\ \sum_{t\in T}z_t=\lambda\}\) and \(C^{\mu,*}_\lambda=\min_{B\in F}C^\mu_\lambda(B)\).
Restrict to instances with \(C^{\mu,*}_{\lambda_i}>0\), and put \(R_I(A)=\max_{i\in\{1,2,3\}}C^\mu_{\lambda_i}(A)/C^{\mu,*}_{\lambda_i}\).
Is computing a facility minimizing \(R_I(A)\) polynomial-time solvable, or NP-hard?
Is \(\sup_I\min_{A\in F}R_I(A)=\beta_3\), where \(\beta_3=\frac{3+\sqrt{5}}{2}\)?
For unit-mass discrete clients, equivalently \(\mu_t=1/n\) and \(\lambda_i=k_i/n\), the worst-case simultaneous ratio for three centrum objectives is exactly \(\beta_3\): a \(\beta_3\) upper bound holds, and an instance forces ratio at least \(\beta_3\) for every facility.
No result for the exact rational-mass formulation above was verified.
Let \(m=|T|\) and \(q_t(A)=d(t,A)\). The facility minimizing \(R_I(A)\) is computable exactly in polynomial time. Moreover,
\[ \sup_I\min_{A\in F}R_I(A)=\beta_3=\frac{3+\sqrt5}{2}. \]
The supremum need not be attained by any rational instance.
Fix \(A\in F\) and \(0<\lambda\leq1\). Order the clients as \(t_1,\ldots,t_m\) so that
\[ q_{t_1}(A)\geq q_{t_2}(A)\geq\cdots\geq q_{t_m}(A). \]
Write \(S_j=\sum_{\ell=1}^j\mu_{t_\ell}\), \(S_0=0\), and let \(r\) be the least index satisfying \(S_r\geq\lambda\). Then
\[ C^\mu_\lambda(A) = \sum_{\ell<r}\mu_{t_\ell}q_{t_\ell}(A) + \bigl(\lambda-S_{r-1}\bigr)q_{t_r}(A). \]
Indeed, for every feasible \(z\),
\[ \sum_{\ell=1}^m z_{t_\ell}q_{t_\ell}(A) = \lambda q_{t_r}(A) + \sum_{\ell<r}z_{t_\ell}\bigl(q_{t_\ell}(A)-q_{t_r}(A)\bigr) + \sum_{\ell>r}z_{t_\ell}\bigl(q_{t_\ell}(A)-q_{t_r}(A)\bigr). \]
For \(\ell<r\), the coefficient is nonnegative, so \(z_{t_\ell}\leq\mu_{t_\ell}\) gives an upper bound. For \(\ell>r\), the coefficient is nonpositive, so the corresponding sum is at most zero. This proves that every feasible \(z\) has value at most the displayed formula.
Equality is attained by taking \(z_{t_\ell}=\mu_{t_\ell}\) for \(\ell<r\), \(z_{t_r}=\lambda-S_{r-1}\), and \(z_{t_\ell}=0\) for \(\ell>r\). Thus the formula is exact.
For each \(A\in F\), sort the values \(d(t,A)\) once. The three values \(C^\mu_{\lambda_i}(A)\) can then be obtained by scanning the resulting cumulative masses.
After computing these quantities for all \(A\in F\), compute
\[ D_i=C^{\mu,*}_{\lambda_i} =\min_{B\in F}C^\mu_{\lambda_i}(B) \]
for each \(i\in\{1,2,3\}\). By hypothesis, every \(D_i\) is positive. Hence exact rational comparison determines
\[ R_I(A)=\max_{i\in\{1,2,3\}} \frac{C^\mu_{\lambda_i}(A)}{D_i} \]
and then an \(A\in F\) minimizing this value.
The algorithm uses \(O(|F||T|\log|T|)\) rational-arithmetic operations. Products and sums of polynomially many binary-encoded rationals have polynomially bounded bit length, and ratios are compared by exact cross-multiplication. Therefore the algorithm runs in polynomial bit complexity. In particular, the search problem belongs to \(\mathrm{FP}\).
Fix an arbitrary rational-mass instance \(I\). Choose a positive integer \(N\) clearing all denominators of the numbers \(\mu_t\) and \(\lambda_i\). Thus
\[ n_t=N\mu_t\in\mathbb Z_{\geq0}, \qquad k_i=N\lambda_i\in\mathbb Z, \]
and \(\sum_t n_t=N\). Since the \(\lambda_i\) are strictly increasing, \(1\leq k_1<k_2<k_3\leq N\).
Create \(n_t\) unit-mass client copies of every \(t\). To avoid using a pseudometric with zero distance between copies, fix \(\varepsilon>0\), attach every copy of \(t\) to the original point \(t\) by an edge of length \(\varepsilon\), and use the induced shortest-path metric on the copies and \(F\). Explicitly,
\[ d_\varepsilon((t,j),A)=d(t,A)+\varepsilon. \]
This is a genuine metric: it is the restriction of the metric obtained by attaching distinct leaves to the original metric space.
Give every copy mass \(1/N\). Aggregating the variables of all copies of \(t\) shows that, for every \(A\in F\),
\[ C^{\mathrm{copy}}_{k_i/N}(A) = C^\mu_{\lambda_i}(A)+\varepsilon\lambda_i. \]
The aggregation is exact: copy-level feasible variables sum to some \(z_t\leq n_t/N=\mu_t\), while every such \(z_t\) can be distributed among the \(n_t\) copies, each having capacity \(1/N\). The additional distance \(\varepsilon\) contributes exactly \(\varepsilon\sum_tz_t=\varepsilon\lambda_i\).
Consequently,
\[ C^{\mathrm{copy},*}_{k_i/N} = C^{\mu,*}_{\lambda_i}+\varepsilon\lambda_i. \]
Applying the supplied unit-mass three-centrum theorem gives
\[ \min_{A\in F} \max_i \frac{C^\mu_{\lambda_i}(A)+\varepsilon\lambda_i} {C^{\mu,*}_{\lambda_i}+\varepsilon\lambda_i} \leq\beta_3. \]
Every denominator is positive at \(\varepsilon=0\). Because \(F\) and the set of levels are finite, the left-hand side is a continuous function of \(\varepsilon\). Letting \(\varepsilon\downarrow0\) yields
\[ \min_{A\in F}R_I(A)\leq\beta_3. \]
Thus
\[ \sup_I\min_{A\in F}R_I(A)\leq\beta_3. \]
The potentially exponential numerical value of \(N\) causes no computational problem: cloning is used only in this existential proof, while the algorithm in Section 2 operates directly on the binary-encoded rational masses.
Take the supplied tight unit-mass instance \(I_0\), with its three positive optimal costs, for which every facility has simultaneous ratio at least \(\beta_3\). Its masses \(1/n\) and levels \(k_i/n\) are rational. It remains only to ensure that its distance matrix may be required to be rational and a genuine metric.
For a fixed mass vector and fixed levels, define
\[ G(d)=\min_{A\in F}\max_i \frac{C^{\mu,d}_{\lambda_i}(A)} {C^{\mu,d,*}_{\lambda_i}}. \]
If two client-facility distance matrices differ entrywise by at most \(\eta\), then, for every \(A\) and \(i\),
\[ \left| C^{\mu,d}_{\lambda_i}(A) - C^{\mu,d'}_{\lambda_i}(A) \right| \leq\lambda_i\eta. \]
This follows because every feasible \(z\) has total mass \(\lambda_i\). Taking minima over \(A\) gives the same bound for the optimal costs. Since the three optimal costs of \(I_0\) are positive, all relevant ratios, finite maxima, and finite minima are continuous in a neighbourhood of its distance matrix. Hence \(G\) is continuous there.
Rational genuine metrics are dense among finite real metrics, and also among finite pseudometrics after an arbitrarily small perturbation. To see this, let \(\delta(x,y)=1\) for \(x\neq y\) and \(\delta(x,x)=0\). For \(\alpha>0\),
\[ d^\alpha=d+\alpha\delta \]
has positive distance between distinct labels and triangle-inequality slack at least \(\alpha\) on every triple of pairwise distinct points. Approximate each off-diagonal entry of \(d^\alpha\), symmetrically, by a rational number with error less than \(\alpha/4\). Every triangle inequality remains valid because its slack changes by less than \(3\alpha/4\), and all off-diagonal entries remain positive. Letting \(\alpha\downarrow0\) produces rational genuine metrics converging to \(d\).
Therefore, for every \(\xi>0\), there is an admissible rational-metric instance \(I_\xi\) with
\[ \min_{A\in F}R_{I_\xi}(A)>\beta_3-\xi. \]
It follows that
\[ \sup_I\min_{A\in F}R_I(A)\geq\beta_3. \]
Together with the upper bound,
\[ \boxed{ \sup_I\min_{A\in F}R_I(A) = \beta_3 = \frac{3+\sqrt5}{2} }. \]
Finally, every individual rational instance has rational tail costs and hence a rational value \(\min_A R_I(A)\). Since \(\beta_3\) is irrational, the supremum is not attained by any instance having entirely rational input data.
⟨structured verdict parsed — rendered above⟩
The prover resolves both questions correctly:
\(\beta_3=(3+\sqrt5)/2\).
The argument rigorously transfers both the upper and lower bounds from the supplied unit-mass result. No substantive gaps or false statements were found.
The sorting formula is correct. Since \(\sum_t\mu_t=1\) and \(0<\lambda\leq1\), the crossing index \(r\) exists. Minimality of \(r\) gives
\[ 0\leq \lambda-S_{r-1}\leq\mu_{t_r}, \]
so the proposed maximizing vector is feasible.
The upper-bound decomposition correctly uses:
The displayed feasible vector attains the bound, including when distances are tied or some client masses are zero. Thus the formula is exact.
For every explicitly listed facility, sorting the client distances and scanning cumulative masses computes all three objectives exactly.
The denominators \(D_i\) are positive by the problem hypothesis, so all ratios and comparisons are well-defined. Since the input contains only polynomially many binary-encoded rationals, exact additions, multiplications, and cross-multiplications retain polynomial bit length. Therefore enumeration over \(F\) gives an exact polynomial-time algorithm.
The claimed membership in \(\mathrm{FP}\) follows.
Choosing \(N\) to clear all denominators correctly produces integers \(n_t=N\mu_t\) and \(k_i=N\lambda_i\), with
\[ 1\leq k_1<k_2<k_3\leq N. \]
The leaf construction produces a genuine metric and ensures
\[ d_\varepsilon((t,j),A)=d(t,A)+\varepsilon. \]
The aggregation argument is exact in both directions: copy-level mass aggregates to a feasible original vector, and every original feasible vector can be distributed among the copies. Consequently,
\[ C^{\mathrm{copy}}_{k_i/N}(A) = C^\mu_{\lambda_i}(A)+\varepsilon\lambda_i. \]
Taking minima over the same facility set gives the corresponding identity for optimal costs.
The supplied unit-mass theorem applies to this genuine finite metric. The minimum of finitely many maxima of continuous rational functions is continuous near \(\varepsilon=0\), since all limiting denominators are positive. Passing to the limit therefore proves the upper bound.
The observation that \(N\) may be numerically large does not affect the algorithmic result because cloning is used only for the mathematical transfer.
The objective changes by at most \(\lambda_i\eta\) when every relevant distance changes by at most \(\eta\). This follows directly from the fixed total selected mass \(\lambda_i\). The same estimate survives minimization over facilities.
Because the tight unit-mass instance has positive optimal costs, all ratios remain continuous in a sufficiently small neighborhood. Finite maxima and minima preserve continuity.
The density argument is correct. For distinct points,
\[ d^\alpha(x,y)=d(x,y)+\alpha \]
adds at least \(\alpha\) of triangle slack to every pairwise-distinct triangle. A symmetric rational perturbation of less than \(\alpha/4\) per edge changes a triangle slack by less than \(3\alpha/4\), preserving every triangle inequality and positivity of off-diagonal distances.
Thus admissible rational genuine metrics can approach the tight unit-mass instance closely enough to obtain values arbitrarily near \(\beta_3\) from below. This proves the matching supremum lower bound.
For a rational input, every tail cost, optimal cost, ratio, finite maximum, and finite minimum is rational. Since \(\beta_3=(3+\sqrt5)/2\) is irrational, no rational instance attains the supremum. This conclusion is correct.
⟨structured verdict parsed — rendered above⟩
Tier: machine-proved, adversarially reviewed by an independent model. No human has checked this proof. Generated from pipeline artifacts by tools/atlas_build.py.