Answer: The smallest universal simultaneous approximation factor is $\rho_*=(5+\sqrt{17})/4$.
Theorem 4.7 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateNo deterministic algorithm can approximate both $\cms$ and $\css$ simultaneously within a factor of better than $(4+\sqrt{7})/3$ for $k \geq 3$.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite metric space, a multiset of facility slots, an integer \(k\geq 3\), and a rational distribution \(\mu\) over client-location types, does there exist a feasible committee \(A\) such that \(\mathrm{SS}_{\mu}(A)\leq \rho\min_B\mathrm{SS}_{\mu}(B)\) and \(\mathrm{MS}_{\mu}(A)\leq \rho\min_B\mathrm{MS}_{\mu}(B)\)? Here \(\mathrm{SS}_{\mu}(A)=\sum_t\mu_t\sum_{a\in A}d(t,a)\), and \(\mathrm{MS}_{\mu}(A)=\max_{t\in\operatorname{supp}\mu}\sum_{a\in A}d(t,a)\).
Input: a finite metric space \((M,d)\), given by its nonnegative binary-rational distance matrix, and an explicit list \(F\) of \(m\) facility slots, each located at a point of \(M\); several slots may share a location. Let \(3\leq k\leq m\).
A society is given by its support: the list of the \(\tau\) client-location types with positive mass, each with its mass as a binary rational. Here \(\tau\) is the support size, not the number of possible types; \(\sum_t\mu_t=1\).
A feasible committee selects exactly \(k\) distinct slots from \(F\). Write \(\ell(a)\) for slot \(a\)'s location; sums count every selected slot, including colocated slots.
Define \(\mathrm{SS}_{\mu}(A)=\sum_t\mu_t\sum_{a\in A}d(t,\ell(a))\) and \(\mathrm{MS}_{\mu}(A)=\max_{t\in\operatorname{supp}\mu}\sum_{a\in A}d(t,\ell(a))\).
For \(\rho\geq1\), simultaneous feasibility means \(\mathrm{SS}_{\mu}(A)\leq\rho\min_B\mathrm{SS}_{\mu}(B)\) and \(\mathrm{MS}_{\mu}(A)\leq\rho\min_B\mathrm{MS}_{\mu}(B)\), with both minima over feasible committees. These inequalities also define feasibility when an optimum is zero.
State any running times in \(m,\tau,|M|,k\) and the total input bit length \(L\).
What is the smallest universal simultaneous approximation factor \(\rho\geq1\) for which every such instance admits a feasible committee satisfying both inequalities?
For finite client lists, the universal factor is at least \((4+\sqrt7)/3\) and at most \(1+\sqrt{5/3}\); the lower bound concerns existence, without a computational restriction. [Verified source](https://arxiv.org/html/2507.17063v1).
No separate result settling the sharp factor for rational client distributions was located.
The smallest universal simultaneous approximation factor is
$$
\boxed{\rho_*=\frac{5+\sqrt{17}}4}.
$$
The proof gives a universal upper bound and a matching limiting family with $k=3$, $m=5$, and $\tau=2$. Thus it closes the interval stated in the question. For comparison, the previously cited bounds appear in [Han–Anshelevich, Section 4.1](https://arxiv.org/html/2507.17063v1#S4.SS1).
For any set $D$ of slots, including sets of size other than $k$, define
$$
c_t(D)=\sum_{a\in D}d(t,\ell(a)),
\qquad
S(D)=\sum_t\mu_t c_t(D).
$$
For a feasible committee, write
$$
Z(D)=\max_{t\in\operatorname{supp}\mu}c_t(D).
$$
Let
$$
s=\min_{|D|=k}S(D),
\qquad
z=\min_{|D|=k}Z(D).
$$
If $s=0$, an attaining committee has $d(t,\ell(a))=0$ for every support location $t$ and every selected slot $a$: all masses are positive, and all summands are nonnegative. That committee also has $Z(D)=0$. Conversely, a committee with $Z(D)=0$ has $S(D)=0$. Thus the two optima vanish together, and a common zero-cost committee satisfies both inequalities with factor $1$.
Henceforth assume $s,z>0$.
For each slot define its weighted cost
$$
w_a=\sum_t\mu_t d(t,\ell(a)).
$$
Then $S(D)=\sum_{a\in D}w_a$. Choose a Sum-Sum optimal committee $O$ and a Max-Sum optimal committee $B$. Put
$$
x=\frac{S(B)}s.
$$
Because a weighted average never exceeds the maximum,
$$
1\leq x,
\qquad
S(B)\leq Z(B)=z,
\qquad
\frac{s}{z}\leq\frac1x.
$$
All intersections and differences below concern distinct slots, so colocated slots cause no ambiguity.
Set
$$
U=O\cap B,\qquad
P=O\setminus U,\qquad
Q=B\setminus U,
\qquad
p=|P|=|Q|,
\qquad
u=S(U).
$$
Suppose $p>0$. For each integer $j$ with $1\leq j\leq p$, let:
Define
$$
A_j=U\cup X_j\cup Y_j,
\qquad
\alpha=\frac jp.
$$
These unions are disjoint and have exactly $k$ slots.
The sum of the cheapest $j$ among $p$ nonnegative numbers is at most $j/p$ times their total. Therefore
$$
S(X_j)\leq\alpha(s-u),
\qquad
S(Y_j)\leq(1-\alpha)(S(B)-u).
$$
Consequently,
$$
S(A_j)
\leq\alpha s+(1-\alpha)S(B),
$$
and hence
$$
\frac{S(A_j)}s
\leq x-\alpha(x-1).
$$
To control Max-Sum, first observe that the triangle inequality, averaged over the society, gives
$$
d(\ell(a),\ell(b))
\leq
\sum_t\mu_t\bigl(d(\ell(a),t)+d(t,\ell(b))\bigr)
=w_a+w_b.
$$
Since $|X_j|=|R_j|=j$, choose any bijection $\pi:X_j\to R_j$. For every support location $t$,
$$
d(t,\ell(a))
\leq d(t,\ell(\pi(a)))+w_a+w_{\pi(a)}.
$$
Summing over the replacement slots yields
$$
c_t(A_j)\leq c_t(B)+S(X_j)+S(R_j).
$$
Using $S(R_j)\leq S(Q)=S(B)-u$, we obtain
$$
Z(A_j)
\leq z+\alpha(s-u)+S(B)-u
\leq z+\alpha s+S(B).
$$
Thus
$$
\frac{Z(A_j)}z\leq2+\frac{\alpha}{x}.
$$
We have proved the two bounds
$$
\boxed{
\frac{S(A_j)}s\leq x-\frac jp(x-1),
\qquad
\frac{Z(A_j)}z\leq2+\frac{j}{px}.
}
$$
For $j=p$, the committee is $O$. In particular,
$$
\frac{Z(O)}z\leq2+\frac1x.
$$
The committee $B$ has simultaneous factor $x$.
Write
$$
C=\frac{5+\sqrt{17}}4.
$$
It satisfies
$$
2C^2-5C+1=0,
\qquad
C>\frac94,
\qquad
(C-2)(2C-1)=1.
$$
We distinguish the number $p$ of differing slots.
Here $O=B$, so this committee optimizes both objectives.
Let $P=\{a\}$ and $c=|U|=k-1\geq2$. For every support location $t$, averaging the triangle inequality over the slots in $U$ gives
$$
d(t,\ell(a))
\leq
\frac{c_t(U)}c+
\frac1c\sum_{q\in U}d(\ell(q),\ell(a)).
$$
The weighted triangle inequality proved above implies
$$
\sum_{q\in U}d(\ell(q),\ell(a))
\leq u+cw_a.
$$
Therefore
$$
c_t(O)
\leq
\left(1+\frac1c\right)c_t(U)+\frac uc+w_a
\leq
\frac32 z+s.
$$
The last inequality uses $c_t(U)\leq c_t(B)\leq z$, $c\geq2$, and $u/c+w_a\leq u+w_a=s$.
It follows that
$$
\frac{Z(O)}z\leq\frac32+\frac1x.
$$
If $x\leq2$, choose $B$. If $x>2$, choose $O$, whose Max-Sum ratio is less than $2$. Thus this case admits factor $2<C$.
The mixed committee $A_1$ satisfies
$$
\frac{S(A_1)}s\leq\frac{1+x}{2},
\qquad
\frac{Z(A_1)}z\leq2+\frac1{2x}.
$$
Put
$$
T=2C-1=\frac1{C-2}.
$$
Since $C>1$, we have $T>C$.
If $x\leq C$, choose $B$.
If $C<x<T$, choose $A_1$. Its Sum-Sum ratio satisfies
$$
\frac{1+x}{2}<\frac{1+T}{2}=C.
$$
Also $x>C>T/2$, so its Max-Sum ratio satisfies
$$
2+\frac1{2x}<2+\frac1T=C.
$$
If $x\geq T$, choose $O$. Its Max-Sum ratio satisfies
$$
2+\frac1x\leq2+\frac1T=C.
$$
Thus this case admits factor $C$, including the boundary values.
In fact, this case admits factor
$$
H=\frac94<C.
$$
If $x\leq H$, choose $B$. If $x\geq4$, choose $O$, since
$$
2+\frac1x\leq\frac94.
$$
It remains to treat $H<x<4$. Define
$$
a=\frac{x-H}{x-1},
\qquad
b=\frac x4.
$$
A mixture with $\alpha=j/p$ satisfies both required bounds whenever
$$
a\leq\alpha\leq b.
$$
Indeed, these inequalities respectively imply
$$
x-\alpha(x-1)\leq H,
\qquad
2+\frac{\alpha}{x}\leq H.
$$
We now verify that this interval contains an admissible multiple of $1/p$. With $y=x-1>0$,
$$
b-a
=\frac14\left(y+\frac5y-3\right)
\geq\frac{2\sqrt5-3}{4}
>\frac13.
$$
The first inequality follows from
$$
y+\frac5y-2\sqrt5
=\left(\sqrt y-\frac{\sqrt5}{\sqrt y}\right)^2\geq0.
$$
For the strict inequality, $6\sqrt5>13$ follows by squaring, since $180>169$.
Because $p\geq3$, the interval has length greater than $1/p$. Take
$$
j=\lceil pa\rceil.
$$
Then
$$
a\leq\frac jp<a+\frac1p<b.
$$
Moreover, $a>0$ and $b<1$, so $1\leq j\leq p-1$. The corresponding feasible committee $A_j$ has both ratios at most $H$.
These cases prove that every instance admits simultaneous factor $C$.
The lower bound uses $k=3$, $m=5$, and two positive-mass client locations.
Let
$$
h_*=3(C-2)=\frac34(\sqrt{17}-3).
$$
The identity $(C-2)(2C-1)=1$ gives
$$
\frac3{h_*}=2C-1,
\qquad
\frac{h_*+3}{2h_*}=C.
$$
For parameters $h>0$ and $0<\varepsilon<1$, consider the four line locations
$$
-h,\qquad 0,\qquad 3,\qquad 4,
$$
with the ordinary distance metric. Place client mass $1-\varepsilon$ at $0$ and mass $\varepsilon$ at $4$. Provide:
Assume
$$
h+6\varepsilon<3.
$$
The individual client distances and weighted slot costs are
$$
\begin{array}{c|ccc}
&q&a&b\\ \hline
\text{distance from }0&0&h&3\\
\text{distance from }4&4&4+h&1\\
w&4\varepsilon&h+4\varepsilon&3-2\varepsilon
\end{array}
$$
The assumed inequality makes the three cheapest slots precisely $q,a,a$. Hence
$$
s=2h+12\varepsilon.
$$
Every feasible committee has one of the following five types. Direct summation gives
$$
\begin{array}{c|cc}
\text{committee type}&S&Z\\ \hline
qaa&2h+12\varepsilon&12+2h\\
qab&h+3+6\varepsilon&9+h\\
qbb&6&6\\
aab&2h+3+6\varepsilon&9+2h\\
abb&h+6&6+h
\end{array}
$$
The table exhausts all possibilities because there is only one $q$ slot and only two slots of each other type. Since $h>0$, it also proves
$$
z=6.
$$
For clarity, in the last row both clients have cost $6+h$; in the other rows the displayed maximum follows directly from the individual distances above.
Now let $h\to h_*$ and $\varepsilon\to0$ through positive values. The limiting approximation ratios are
$$
\begin{array}{c|ccc}
\text{committee type}
&S/s&Z/z&\text{simultaneous factor}\\ \hline
qaa&1&C&C\\
qab&C&(C+1)/2&C\\
qbb&2C-1&1&2C-1\\
aab&C+1/2&C-1/2&C+1/2\\
abb&2C-1/2&C/2&2C-1/2
\end{array}
$$
All entries follow by substituting $3/h_*=2C-1$ and $h_*/3=C-2$. Since $C>1$, the minimum of the five limiting simultaneous factors is exactly $C$.
The irrational parameter is used only to describe the limit. For integers $n\geq3$, choose
$$
h_n=\frac{\lfloor2^n h_*\rfloor}{2^n},
\qquad
\varepsilon_n=2^{-n}.
$$
Here $0<h_*<1$, so
$$
h_n+6\varepsilon_n<1+\frac68<3.
$$
Every distance and both masses are dyadic rationals. Thus these are admissible inputs with
$$
|M|=4,\qquad \tau=2,\qquad m=5,\qquad k=3.
$$
At every stage, both client masses are positive; the client at $4$ remains in the Max-Sum support.
The Sum-Sum optimum tends to $2h_*>0$, while the Max-Sum optimum remains $6$. Consequently, every ratio in the five-row table converges to its displayed limit. For finitely many quantities, taking their minimum preserves convergence: explicitly,
$$
\left|\min_i v_{i,n}-\min_i v_i\right|
\leq\max_i|v_{i,n}-v_i|.
$$
Therefore the best simultaneous factor of these instances tends to $C$.
For every $\rho<C$, a sufficiently large $n$ consequently gives an admissible instance on which every committee has simultaneous factor greater than $\rho$. This proves the matching universal lower bound.
The upper proof is constructive once a Max-Sum optimal committee $B$ is available.
Compute the $m$ weights $w_a$ in $O(m\tau)$ rational arithmetic operations and choose the $k$ cheapest slots to obtain $O$. If its cost is zero, return it immediately, before forming any ratios.
Otherwise, enumerate all $\binom mk$ committees to obtain $B$. Computing each committee’s client costs takes $O(k\tau)$ rational arithmetic operations. Form the mixed committees from Section 2 and choose the best among them, $O$, and $B$, using exact rational ratio comparisons. The proof guarantees that the chosen committee has factor at most $C$.
A conservative bit-time bound, including reading the distance matrix, is
$$
O\!\left(
\left[
|M|^2+m\tau+m\log m+\binom mk\,k\tau
\right]L^3
\right).
$$
To justify the bit bound, common denominators for the input masses and distances have $O(L)$ bits. Objective values and the cross-products used to compare ratios therefore also have $O(L)$ bits. Elementary exact arithmetic fits within the displayed conservative bound.
This algorithm is exponential in general; the sharp factor proved above concerns existence without a computational restriction.
⟨structured verdict parsed — rendered above⟩
The argument establishes the claimed sharp universal factor
$$
\rho_*=\frac{5+\sqrt{17}}4.
$$
I found no mathematical errors or gaps requiring clarification. The proof covers zero optima, colocated slots, all possible intersection sizes, and the binary-rational input restriction. Its algorithm is exponential; it does not establish a polynomial-time complexity classification.
The feasible family is finite and nonempty because $k\leq m$, so both minima are attained.
If $S(D)=0$, positivity of every listed mass and nonnegativity of distances imply that every selected slot has zero distance from every support location. Hence $Z(D)=0$. Conversely, $Z(D)=0$ implies $S(D)=0$. The two optimal values therefore vanish together, and the stated common zero-cost committee handles the inequalities exactly as required.
All subsequent divisions occur under the explicit assumption $s,z>0$.
The identities and inequalities
$$
S(D)=\sum_{a\in D}w_a,\qquad
x=\frac{S(B)}s\geq1,\qquad
S(B)\leq z,\qquad
\frac{s}{z}\leq\frac1x
$$
are valid. The weighted-average inequality uses precisely the stated normalization $\sum_t\mu_t=1$.
Since $O$ and $B$ each contain $k$ distinct slots, their differences $P$ and $Q$ have equal cardinality. The sets forming $A_j$ are disjoint and contribute exactly $k$ slots. This remains valid when different slots share a location.
The cheapest-subset inequalities apply to the nonnegative slot costs and give
$$
S(A_j)\leq\alpha s+(1-\alpha)S(B).
$$
Thus the stated Sum-Sum ratio bound is correct.
Averaging the metric triangle inequality over the normalized masses gives
$$
d(\ell(a),\ell(b))\leq w_a+w_b.
$$
This inequality applies to arbitrary slots, including colocated ones.
The bijection between $X_j$ and $R_j$ exists because both have cardinality $j$. Summing the corresponding triangle inequalities correctly gives
$$
c_t(A_j)\leq c_t(B)+S(X_j)+S(R_j).
$$
Nonnegativity justifies $S(R_j)\leq S(Q)$. Consequently,
$$
Z(A_j)\leq z+\alpha s+S(B).
$$
Dividing by $z$ and using $S(B)/z\leq1$ and $s/z\leq1/x$ establishes
$$
\frac{Z(A_j)}z\leq2+\frac{\alpha}{x}.
$$
Both boxed bounds therefore hold throughout the stated range, including $j=p$, where $A_p=O$.
The displayed identities for
$$
C=\frac{5+\sqrt{17}}4
$$
are correct, including $C>9/4$ and $(C-2)(2C-1)=1$.
$$
c_t(U)\leq z,\qquad
1+\frac1c\leq\frac32,\qquad
\frac uc+w_a\leq u+w_a=s.
$$
Thus $Z(O)/z\leq3/2+1/x$. Choosing $B$ for $x\leq2$ and $O$ for $x>2$ proves the claimed factor $2$.
$$
T=2C-1=\frac1{C-2}
$$
satisfies $T>C$ and $T/2<C$. For $C<x<T$, these inequalities justify both estimates for $A_1$. For $x\geq T$, the estimate for $O$ is valid. The boundary values $x=C$ and $x=T$ are explicitly covered by the adjacent choices.
The interval-width computation is correct:
$$
b-a=\frac14\left(y+\frac5y-3\right)
\geq\frac{2\sqrt5-3}{4}>\frac13.
$$
The square identity proves the first inequality, and the stated squaring argument proves the strict second inequality.
Since $p\geq3$, the ceiling choice satisfies
$$
a\leq\frac{\lceil pa\rceil}{p}<a+\frac1p<b.
$$
Moreover, $a>0$ and $b<1$ imply that the resulting integer lies between $1$ and $p-1$. Thus it indexes an admissible committee.
The cases exhaust all possibilities and establish the universal factor $C$.
The four locations are distinct for $h>0$, and ordinary line distance is a metric. The five slots satisfy the required multiplicity model.
All entries in the individual-distance and weighted-cost table are correct. The assumption $h+6\varepsilon<3$ implies
$$
w_q<w_a<w_b,
$$
so $qaa$ is Sum-Sum optimal and
$$
s=2h+12\varepsilon.
$$
The five committee types exhaust every selection of three slots: each of the two repeated types has multiplicity at most two, and $q$ has multiplicity at most one.
Direct checking confirms every objective entry:
$$
\begin{array}{c|cc}
\text{type}&S&Z\\ \hline
qaa&2h+12\varepsilon&12+2h\\
qab&h+3+6\varepsilon&9+h\\
qbb&6&6\\
aab&2h+3+6\varepsilon&9+2h\\
abb&h+6&6+h
\end{array}
$$
In particular, both clients have cost $6+h$ for $abb$. Every other displayed maximum also selects the correct client cost. Since $h>0$, the table establishes $z=6$.
The identities involving $h_*=3(C-2)$ are correct. Substitution verifies every entry in the limiting-ratio table. In particular, the limiting simultaneous factors are
$$
C,\quad C,\quad 2C-1,\quad C+\frac12,\quad 2C-\frac12.
$$
Their minimum is $C$.
For every $n\geq3$, the specified $h_n$ is positive, is dyadic rational, and converges to $h_*$. The displayed bound ensures $h_n+6\varepsilon_n<3$. All line distances and masses are therefore admissible binary rationals.
Both masses remain strictly positive at every finite stage. Thus the client at $4$ remains in the Max-Sum support, even though its mass tends to zero. The proof correctly evaluates the limit of the finite-instance objectives.
Because $s_n$ converges to the positive number $2h_*$, every ratio converges. The stated finite-minimum inequality correctly transfers convergence to the best simultaneous factor. Hence, for every $\rho<C$, some admissible finite instance has no committee satisfying both inequalities with factor $\rho$.
This proves the required universal lower bound; attainment of the limiting instance is unnecessary.
Choosing the $k$ cheapest weighted slots correctly computes $O$. Exhaustive enumeration computes an exact Max-Sum optimizer $B$, and the candidate family contains every committee used in the upper-bound case analysis. Exact rational comparisons suffice to select the best simultaneous factor; no comparison with an irrational threshold is required.
The arithmetic-operation counts are valid. Sorting and evaluating the mixed candidates fit within the displayed conservative bound. Common denominators for the explicitly encoded distances and masses have $O(L)$ bits; their products, objective numerators, and ratio-comparison cross-products also have $O(L)$ bits. Thus the stated bit-time bound is a valid conservative bound:
$$
O\!\left(
\left[
|M|^2+m\tau+m\log m+\binom mk\,k\tau
\right]L^3
\right).
$$
The cited prior interval agrees with the [referenced source](https://arxiv.org/html/2507.17063v1#S4.SS1). The new argument is self-contained and does not rely on an unstated theorem from that source.
No additional clarification is needed to verify the argument.
⟨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.