| paper | d4-conf-wine-2025-0024 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
other→other discrete result → its continuous mirror
Answer: The smallest universal simultaneous approximation factor is $\rho_*=(5+\sqrt{17})/4$. · discrete side: other · adjudication: proved
full proof & adversarial review →
Theorem 4.7
statement extracted from the paper’s text layer
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)\).
Client types are locations in the paper's finite metric, each carrying rational mass; the facility slots and committee choices remain discrete. Sum objectives become mass-weighted per-capita costs, while max objectives range over every type of positive mass.
The mirror covers Theorem 4.7's lower bound for simultaneous Sum-Sum and Max-Sum approximation; it leaves the paper's other objective pairs, upper bounds, and efficient computation questions open.
The strongest mirror is the paper’s simultaneous approximation problem with a continuous population. Its novelty would be the complexity analysis of that population model, not the move to a continuum itself.
Let \((X,d)\) be a finite metric space, \(\mathcal F\) a multiset of facility slots, and \(\mathcal T\) a finite set of client types. A type specifies a location, hence its distances to all possible facilities. The population is a rational distribution \(\mu\) on \(\mathcal T\), with positive mass for each type in its support. A feasible committee \(A\) selects \(k\) slots from \(\mathcal F\). Define
\(\mathrm{SS}_\mu(A)=\sum_{t\in\mathcal T}\mu_t\sum_{a\in A}d(t,a)\),
\(\mathrm{MS}_\mu(A)=\max_{t\in\operatorname{supp}\mu}\sum_{a\in A}d(t,a)\),
\(\mathrm{SM}_\mu(A)=\sum_{t\in\mathcal T}\mu_t\max_{a\in A}d(t,a)\), and
\(\mathrm{MM}_\mu(A)=\max_{t\in\operatorname{supp}\mu}\max_{a\in A}d(t,a)\).
These are the paper’s four objectives with client sums normalized to per-capita costs; that normalization does not change approximation ratios. Max objectives range over every positive-mass type, however small its mass.
The population regime is credible for a municipality choosing service locations, or for the paper’s spatial-voting interpretation: many residents occupy a few recurring neighborhoods, and residents of each type have identical distances to the available locations. In the paper’s lower-bound examples, \(\tau=2\) while the number of residents can grow without bound. Even a rare type can contain many residents: take mass \(\epsilon=1/q\) and a population of \(qr\), giving that type \(r\) residents. The selectable facilities remain discrete, as in the paper.
Lead — Continuous Simultaneous Sum-Sum/Max-Sum Committee. An instance consists of the finite metric, \(\mathcal F\), \(k\geq3\), and rational \(\mu\). Given a factor \(\rho\), decide whether there is a feasible \(A\) satisfying both \(\mathrm{SS}_\mu(A)\leq\rho\,\mathrm{OPT}_{SS}\) and \(\mathrm{MS}_\mu(A)\leq\rho\,\mathrm{OPT}_{MS}\); a yes-solution is such a committee. Equivalently, one can ask for a committee minimizing the maximum of those two normalized costs.
The anchor is Theorem 4.7, proved in this paper: *for \(k\geq3\), no deterministic algorithm can simultaneously approximate Max-Sum and Sum-Sum within a factor better than \((4+\sqrt 7)/3\).* Its witness has client locations \(A,C\), facility slots at \(B,D\), three slots at each, and distances \(d(A,B)=d(B,C)=1\), \(d(C,D)=(\sqrt 7-2)/3\). Give the two client types masses \(\epsilon\) and \(1-\epsilon\). As \(\epsilon\) tends to zero, placing all facilities at \(D\) is best for Sum-Sum, while placing them all at \(B\) is best for Max-Sum; no choice of the three slots beats the stated simultaneous bound. For any factor strictly below the bound, a sufficiently small positive rational \(\epsilon\) preserves the obstruction. The paper’s construction uses algebraic distances; rational approximations preserve any strict sub-bound obstruction.
I expect this lower-bound guarantee to persist in the continuous model: empirical discrete populations embed as rational type masses, and the witness itself needs only two types. That is a Class-B-like transfer of the approximation barrier, though it does not establish NP-hardness or a \(P\ne NP\) result. This mirror covers the Sum-Sum/Max-Sum lower-bound result, not the paper’s other objective pairs.
Second anchor — Continuous Simultaneous Sum-Max/Max-Max Committee. Use the same input, with the decision question whether a committee simultaneously achieves factor \(\rho\) for \(\mathrm{SM}_\mu\) and \(\mathrm{MM}_\mu\). The anchor is Theorem 4.8, also proved here: *no deterministic algorithm has a simultaneous approximation bound better than \(1+\sqrt 2\) for Max-Max and Sum-Max.* Its witness puts the two client types at \(A,C\), with masses \(\epsilon,1-\epsilon\), and offers \(k\) facility slots at each of \(B,D\); the line distances are \(d(A,B)=d(B,C)=1\) and \(d(C,D)=\sqrt 2-1\). At small positive \(\epsilon\), all slots at \(D\) favor Sum-Max, while all slots at \(B\) favor Max-Max. Any mixed choice still exposes the rare type to the distant \(D\) slot, yielding the lower bound. Again, the continuous version retains this obstruction with only two positive-mass types. The same approximation-barrier classification is the honest expectation; the theorem does not settle the runtime of finding committees that attain the paper’s upper bounds.
The authors should recognize both questions: they keep the metric, feasible committees, per-client costs, and simultaneous objective intact. Only the list of repeated clients becomes a distribution over indistinguishable client types. Further work would ask for the complexity of these threshold problems in facility-set size, support size \(\tau\), and mass bit length, and whether the paper’s existence bounds can be attained efficiently from compressed inputs.
My weakest point is that these anchors are approximation-ratio impossibility results, not complexity-class hardness theorems. The paper itself says efficient computation for many of its bounds remains open. Also, the lower-bound sequences rely on a low-mass type that still counts fully in the max objective. That is faithful to the paper’s egalitarian objective and every type retains positive mass, but it makes the result a sharp mirror of these max-based trade-offs rather than evidence that population continuization generally preserves computational hardness.
The strongest case against is that Theorems 4.7 and 4.8 are geometric limits on what any committee can achieve, not runtime lower bounds. Their proofs use tiny instances and show that every feasible placement has a bad ratio. Replacing client counts with rational masses therefore reproduces the same obstruction, but does not by itself chart the complexity of finding a good committee. The paper also leaves efficient computation open. So these theorems are weak anchors for ChoCo’s computational programme: the continuous versions need a separate question about algorithms, parameterized by support size and input bit length.
That objection does not defeat the best version of the first mirror. For Theorem 4.7, take two client types at \(A\) and \(C\), with masses \(\epsilon\) and \(1-\epsilon\), and the same finite facility slots. For any target factor strictly below \((4+\sqrt 7)/3\), a sufficiently small positive rational \(\epsilon\) preserves the obstruction. Normalizing client sums to per-capita costs leaves approximation ratios unchanged. This is a credible high-multiplicity regime: many residents can share each location, and the unusual type can still represent many people. The mirror is faithful, even if the theorem’s witness says little about algorithmic complexity.
The second anchor survives the same challenge. In Theorem 4.8, a positive-mass type remains in the support, so the Max-Max cost still sees it fully, however small its mass. Choose a fixed rational \(\epsilon>0\) small enough for the desired strict lower bound, and the paper’s two-location construction carries over. This support-based maximum is also faithful to the paper’s egalitarian objective. Its weakness is instability as \(\epsilon\) tends to zero: the maximum can jump when a type disappears from the support. But that is a limitation of taking a measure limit, not a reason the fixed-distribution problem is ill-posed.
Thus I can argue that the proponent has not shown that these theorems themselves yield new computational results. I cannot honestly argue that no worthwhile continuous mirror exists. The finite metric, discrete facility choices, and repeated client locations give a sensible population model for both anchors; the remaining algorithmic questions are natural. The negative case is weak precisely where it needs to be strongest: neither anchor can be dismissed without ruling out the better, fixed-positive-mass formulation.
The adversarial triple: the proponent anchors on up to three named results; the opponent sees that case and must defeat every anchor; the judge decides which case convinced it. These are the pipeline’s own outputs, generated by tools/triple_run.py — no human edited them. The paper’s own text is not reproduced here beyond the quoted statement above.