| paper | d4-journals-mss-2017-0003 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
P→P discrete result → its continuous mirror
Answer: Exactly polynomial-time solvable; the threshold decision version belongs to \(\mathrm{P}\). · discrete side: polynomial · adjudication: proved_with_minor_gaps
full proof & adversarial review →
Theorem 1
statement extracted from the paper’s text layer
Given rational target positions \(x_1<\cdots<x_\tau\) and positive rational masses \(\mu_i\) summing to \(1\), find the minimum of \(\sum_{i=1}^{\tau}\int_{\mathbb R}|x_i-y|\,d\pi_i(y)\) over nonnegative assignment measures satisfying \(\pi_i(\mathbb R)=\mu_i\) and \(\sum_i\pi_i(B)\leq |B|\) for every measurable set \(B\), where \(|B|\) is its length.
A continuum population with mass \(\mu_i\) at each target type \(x_i\), assigned to service positions on \(\mathbb R\) with capacity density \(1\). Each \(\pi_i\) records the mass of type \(i\) sent to each position; minimize total distance.
The paper does not establish that discrete instances with targets and slots scaled by \(1/n\) converge to this capacity-density model, or give an error bound for that convergence.
fatal: False
The mirror covers the deterministic aggregate-gap optimization anchored by Theorem 1, with Theorem 2 providing its running-time guarantee. It leaves the probabilistic-assignment methods and gap-egalitarian results aside.
The strongest mirror is Continuous Aggregate-Gap Line Assignment. Its lead anchor is the paper’s Neat Shifting result, proved here: Theorem 1 says the Neat Shifting Algorithm returns an assignment minimizing the sum of agents’ distances from their targets; Theorem 2 says that algorithm runs in \(O(n^3)\) time. Together, these establish a polynomial-time algorithm for the paper’s deterministic aggregate-gap problem, even though the line has arbitrarily many available slots. The mirror concerns that underlying assignment problem, not the algorithm itself. The paper has no comparable named hardness result of its own; the hardness results mentioned in its related work concern other problems or are cited from elsewhere.
For the continuous problem, the instance is a finite list of target positions \(x_1<\cdots<x_\tau\) on the line and rational masses \(\mu_i>0\) summing to \(1\). A type consists of a target position and the identical distance-based preferences of everyone in that type. The society has mass \(\mu_i\) of type \(i\). Service positions form a continuum with capacity density \(1\): for every measurable set \(B\), at most \(\lambda(B)\) mass can be assigned into \(B\), where \(\lambda\) is length. An assignment is a tuple of measures \((\pi_i)\), where \(\pi_i\) says how much type-\(i\) mass is sent to each service position, satisfying \(\pi_i(\mathbb R)=\mu_i\) and \(\sum_i\pi_i(B)\leq\lambda(B)\). The objective is to minimize
\[
\sum_{i=1}^{\tau}\int_{\mathbb R}|x_i-y|\,d\pi_i(y).
\]
A solution is an optimal tuple of assignment measures and its cost. Because the population is atomless, each individual receives one service position; it is the type-level aggregate that is represented by measures.
A plausible regime is a high-volume appointment or service system. Large cohorts request the same preferred time or position, while each service slot can serve only one client. As volume grows, the schedule grows at matching scale. Rescaling the discrete line by \(1/n\) makes each discrete slot have capacity \(1/n\); those slot capacities approach unit density, while the empirical distribution of targets approaches the input masses \(\mu_i\). The average rescaled gap has the same minimizers as the discrete sum of gaps. Thus the model preserves the paper’s line, targets, one-agent-per-slot constraint, and distance objective while making population mass the object being assigned.
I expect this problem to be Class A, tractable. In an optimal assignment, crossing assignments can be uncrossed, so sort the population by target and let \(q\in[0,1]\) denote cumulative mass. If \(a(q)\) is the resulting step function of targets and \(y(q)\) is the assigned position, the capacity constraint for a monotone assignment is that \(y(q)-q\) be nondecreasing. The objective becomes \(\int_0^1|a(q)-y(q)|\,dq\), a one-dimensional isotonic optimization problem with only \(\tau\) target blocks. That gives a concrete route to an exact algorithm polynomial in \(\tau\) and the input bit length, though the finite rational representation and its bit complexity would need to be proved. This claim does not follow automatically from the paper’s \(O(n^3)\) bound.
The mirror covers the deterministic aggregate-gap result only. It does not claim to continuize the paper’s probabilistic-assignment methods, its gap-egalitarian objective, or its fairness properties. It raises useful follow-up questions: whether scaled discrete optima converge to continuous optima, at what rate rounding affects the value, and whether a continuous analogue of gap egalitarianism has an efficient exact algorithm.
The weakest point is that the paper’s result is algorithmic rather than a hardness anchor, so this mirror does not test whether discrete hardness dissolves in the continuum. Also, capacity density \(1\) is a co-modification of the slot model, and a strict reader could regard the result as a new capacity-density variant. The case for acceptance is that this change follows directly from the scaling limit of the paper’s one-agent-per-slot constraint; it retains the authors’ central assignment question rather than replacing it with fractional outcomes for a finite electorate.
The best case against the aggregate-gap mirror is that its computational novelty may be thin. Theorems 1 and 2 already give an exact polynomial-time algorithm for the discrete problem. The proposed mirror would take its one-dimensional distance objective and one-agent-per-slot constraint into a continuum-capacity transport model, where sorting and monotonicity appear to reduce the problem to isotonic optimization. The likely contribution is then a scaling theorem and a finite-support implementation bound, rather than a new complexity phenomenon.
There is established neighboring machinery: capacity-constrained optimal transport studies mass couplings with density bounds, and Hartmann and Schuhmacher give an algorithm for a \(p=1\) semi-discrete transport problem. Neither is the exact proposed model—their measure orientations or constraints differ—so this is not evidence that the mirror is already done. It does, however, make the route to an answer look like a fairly direct application of known transport ideas. [Korman and McCann](https://arxiv.org/abs/1201.6404); [Hartmann and Schuhmacher](https://arxiv.org/abs/1706.07650).
The mirror also depends on a scaling regime: targets must be interpreted on a growing line, and slot capacity must scale into a density. That is a coherent co-modification for a high-volume service system, but it means the paper’s result alone does not supply the promised discrete-to-continuous dictionary. The authors would need to show that the scaled discrete optimum converges to this particular capacity model, with a useful error bound. Until then, the model is plausible but its connection to the paper’s instances is a separate result to establish.
This is the strongest negative case I can make, and it is not strong enough to defeat the anchor. The target groups are genuine high-multiplicity types, identities do not enter aggregate gap minimization, and scaling slot capacity with population is allowed by the programme’s scope. The paper has a named algorithmic result, and a continuum question for it is well posed. Calling the mirror unworthy because its answer may be easy, or because it preserves tractability, would not meet the programme’s standard. The honest conclusion is that the case against is weak.
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.