| paper | d4-conf-atal-2023-0533 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
Answer: Exact minimization is polynomial-time solvable in \(n,m,k,\tau,L\). · discrete side: polynomial · adjudication: proved
full proof & adversarial review →
Theorem 10
statement extracted from the paper’s text layer
Given a weighted road graph \(G\), ordered PoI categories \(V_1,\ldots,V_k\), and a finite support \(T\) of origin–destination types \(t=(o_t,d_t)\) with positive binary-rational masses \(\mu_t\) summing to \(1\), find a valid itinerary \(P=(v_1,\ldots,v_k)\) minimizing \(J_\mu(P)=\sum_{t\in T}\mu_t\left[d_G(o_t,v_1)+\sum_{j=1}^{k-1}d_G(v_j,v_{j+1})+d_G(v_k,d_t)\right]\).
The population is a distribution \(\mu\) over origin–destination types; each unit follows an integral route along the same chosen ordered itinerary \(P\). The decision is the itinerary, and the objective is mean travel distance \(J_\mu(P)\); shortest road routes connect its stops.
The mirror covers Theorem 10’s optimal sequenced-GTP objective. It leaves the paper’s minimum-envy and price-of-fairness results, including Lemmas 3–7, aside.
My lead is Mass-Sequenced GTP\(_\infty\), mirroring the paper’s sequenced trip-planning objective.
The anchor is Theorem 10, proved in this paper. It states that 4partiteGTP finds an optimal path for sequenced GTP in \(O(n^3)\) time under the paper’s parameterization. The output is a valid path visiting one PoI from each category in the prescribed order, minimizing the agents’ total travel distance. The theorem’s algorithm reduces the route choices to a four-partite graph and computes the cost of each candidate path.
A plausible high-multiplicity regime is a regional supply-chain operation: many shipment units come from a relatively small set of producer locations and go to a small set of destinations, while planners choose a common sequence of facility categories. That interpretation is close to one the paper itself gives. A type is a complete origin–destination pair \(t=(o_t,d_t)\); \(\mu_t\) is the fraction of shipment mass with that pair. There may be many units but only \(\tau\) distinct types. Every unit still follows an integral route; only the population is represented by masses.
Precisely, the instance gives a weighted road graph \(G\), ordered PoI categories \(V_1,\ldots,V_k\), and a finite support \(T\) of origin–destination types with positive binary-rational masses \(\mu_t\) summing to \(1\). For a valid itinerary \(P=(v_1,\ldots,v_k)\), let \(d_G\) be shortest-path distance and define
\[
D_t(P)=d_G(o_t,v_1)+\sum_{j=1}^{k-1}d_G(v_j,v_{j+1})+d_G(v_k,d_t).
\]
The question is to return a valid itinerary minimizing
\[
J_\mu(P)=\sum_{t\in T}\mu_tD_t(P),
\]
with shortest road routes between its stops. This is the per-unit average version of the paper’s objective: for a discrete population with \(b\) agents and \(\mu_t=n_t/b\), \(J_\mu\) is exactly the total distance divided by \(b\), so the minimizing itinerary is unchanged.
I expect this mirror to be tractable. After shortest-path distances are computed, the contribution from the first stop depends on the origin marginal masses, the last stop on the destination marginal masses, and the intermediate itinerary contributes its shared route distance. A layered dynamic program over the ordered categories can compute the best intermediate route for each first-and-last-stop pair; scoring those pairs uses the weighted type masses. This is polynomial in the graph and category sizes, \(\tau\), and the bit length \(L\). The discrete-to-continuous dictionary is also direct: rational masses can be scaled to integer multiplicities, while the weighted formulation avoids expanding a large population into individual rows.
The supplied paper says broadly that GTP is NP-hard, but it gives no numbered hardness result for that claim, and its sequenced problem is the one Theorem 10 solves. I would not use that introductory statement as a hardness anchor.
This case covers Theorem 10’s aggregate-efficiency result only. It does not claim to continue the paper’s envy objective or its price-of-fairness lemmas. My weakest point is that the anchor is the paper’s baseline sequenced-GTP algorithm, not its central fairness contribution; moreover, its algorithm is already polynomial, so this mirror offers high-multiplicity compression rather than a new tractability result. A natural follow-up is whether the paper’s Pareto-restricted minimum-envy objective admits an algorithm polynomial in \(\tau\), and what price-of-fairness bound applies when types have unequal masses.
The strongest objection is that the supply-chain story adds a substantial assumption: every unit must follow the same ordered sequence of facility categories, and units with the same origin and destination must be interchangeable in every respect that affects travel. Real shipments often have different processing requirements, capacities, or handling constraints. Adding those differences to the type definition could make the support large and weaken the high-multiplicity premise.
But that objection does not defeat the mirror. The paper itself offers a supply-chain interpretation, and a cohort of otherwise identical travelers or shipments with repeated origin–destination pairs is plausible. For that regime, the proposed type \(t=(o_t,d_t)\) is complete, each unit still takes an integral route, and the objective is exactly the paper’s total distance divided by population size.
There is a narrower reason to question the programme’s investment: the continuous objective collapses to weighted origin and destination marginals. If \(\alpha_o=\sum_d\mu_{od}\) and \(\beta_d=\sum_o\mu_{od}\), then for itinerary \(P=(v_1,\ldots,v_k)\),
\[
J_\mu(P)=
\sum_o\alpha_o\,d_G(o,v_1)
+\sum_{j=1}^{k-1}d_G(v_j,v_{j+1})
+\sum_d\beta_d\,d_G(v_k,d).
\]
The origin–destination pairing does not affect this aggregate objective. Weighted sums can therefore replace the paper’s sums over named agents, giving a compact high-multiplicity input and a polynomial algorithm. That looks like a simple extension of Theorem 10, rather than a new optimization challenge.
Still, simplicity and a likely tractable answer do not make the question ill-posed, and high-multiplicity compression is part of the programme. This anchor has no evident identity, degeneracy, or prior-art objection: the population masses are meaningful, the result is computational, and the paper does not already formulate the continuous-population problem. Its mirror may be a modest contribution, but I cannot honestly argue that it is not worthwhile in every plausible scenario. The proponent’s Theorem 10 anchor survives; the negative case 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.