| paper | d4-conf-atal-2018-0127 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
NP-hard→NP-hard discrete result → its continuous mirror
Answer: NP-hard for every fixed \(p\in(1,\infty)\) and every \(g\in\{T,E,D\}\), even when \(\tau=2\) and \(\mu_1=\mu_2=\tfrac12\). · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 12
statement extracted from the paper’s text layer
Given jobs with positive integer durations and a distribution \(\mu\) over supported preferred orderings, choose a permutation \(\pi\) minimizing \((\sum_t \mu_t f_t^g(\pi)^p)^{1/p}\), for fixed \(p>1\) and \(g\in\{T,E,D\}\). Here \(f_t^g(\pi)=\sum_j g(C_j(\pi),C_j(t))\), where \(C_j(t)\) is job \(j\)'s completion time in type \(t\)'s preferred ordering. Theorem 12 establishes NP-hardness already for two types of mass \(1/2\) each.
A society is a rational distribution \(\mu\) over complete preferred job orderings; each type's mass is its population share. The decision is one integral, gap-free job permutation \(\pi\), and the objective is the mass-weighted \(L_p\) norm of each type's total tardiness, earliness, or absolute deviation from its preferred schedule. The discrete two-agent case is recovered with two types of mass \(1/2\), up to the common factor \(n^{-1/p}\).
The mirror covers Theorem 12's hardness for the \(L_p\)-T, \(L_p\)-E, and \(L_p\)-D objectives. It leaves the paper's other complexity results, axiomatic properties, and experiments outside its scope.
The lead mirror is Continuous Sum-Tardiness Collective Scheduling. Fix jobs \(J\) with positive integer processing times \(p_j\). A type \(t\) is a complete preferred ordering of those jobs; a society is a list of the \(\tau\) supported types with rational masses \(\mu_t\) summing to \(1\). The decision is still a single, gap-free permutation \(\pi\). Write \(C_j(\pi)\) for job \(j\)’s completion time in that permutation. Type \(t\)’s preferred ordering gives its due date \(C_j(t)\), so its total tardiness is \(T_t(\pi)=\sum_{j\in J}\max(0,C_j(\pi)-C_j(t))\). The problem is to output a permutation minimizing \(\sum_t\mu_t T_t(\pi)\). The instance is the jobs and durations plus the supported orderings and their binary-rational masses; the solution is an optimal schedule.
This fits a city phasing public works for a large population. Residents with the same preferred ordering of phases are one type; their mass is their share of the population. A city may have millions of residents but comparatively few distinct orderings, especially when residents express preferences through shared templates or constituency groups. Job durations are common physical facts, and the per-person tardiness measure stays the paper’s measure. The authors motivate collective scheduling with public works and a large audience, so this is a plausible high-multiplicity regime for their problem.
The lead anchor is Theorem 8, proved in the paper by reduction from 3-Partition. It states that finding a collective schedule minimizing total tardiness, \(\Sigma\)-T, is strongly NP-hard in the paper’s single-processor setting. A finite profile with \(n_t\) agents of each type maps to \(\mu_t=n_t/n\), where \(n=\sum_t n_t\). The continuous objective is the original total tardiness divided by \(n\), so its minimizers are identical. The reduction therefore gives hardness for this rational-mass problem; normalization changes the objective by a common factor. This is a hardness-transfers case, rather than a prediction that continuity makes the problem tractable. Theorem 8 is the lead because it anchors the mirror in the paper’s duration-sensitive scheduling objective.
A second, particularly useful anchor is Theorem 12, also proved in the paper, by a reduction from Partition. It states that for every fixed \(p>1\), finding a schedule minimizing each of the \(L_p\)-T, \(L_p\)-E, and \(L_p\)-D objectives is NP-hard even with two agents. Its continuous mirror uses the same job and type model, with \(f_t(\pi)\) denoting type \(t\)’s cost under T, E, or D, and minimizes \(\bigl(\sum_t\mu_t f_t(\pi)^p\bigr)^{1/p}\). For a finite profile this is the paper’s \(L_p\) objective multiplied by \(n^{-1/p}\), which leaves the optimal schedules unchanged. In the two-agent reduction, the two preference types have mass \(1/2\) each. Replicating both groups gives arbitrarily many agents while keeping only two types, with the same optimum. This anchor also predicts hardness transfers, and it gives especially direct support for a high-multiplicity regime with \(\tau\) fixed.
Both mirrors ask the authors’ underlying scheduling questions: the jobs, durations, preferred schedules, cost functions, and integral output schedule are preserved. The continuous object is the population distribution, and every type remains a complete account of the preferences the problem uses. These formulations do not claim a tractability gain. Their contribution to the programme would be a precise boundary result: discrete hardness persists even when the population is represented by type masses.
The scope here is \(\Sigma\)-T from Theorem 8 and the \(L_p\)-T/E/D objectives from Theorem 12. I would not stretch these anchors to cover every rule in the paper. Further questions include whether \(\Sigma\)-T becomes tractable for fixed or small \(\tau\), what approximation guarantees are possible for rational-mass societies, and how the \(L_p\) results change at \(p=1\) or under other restrictions on the type distribution.
The weakest point is that Theorem 8’s reduction does not establish hardness when \(\tau\) is small: its support may grow with the construction. The city scenario makes low-support societies plausible, but the theorem itself does not validate that empirical assumption. Theorem 12 partly addresses this weakness for its own objectives, since its hardness already uses just two types; it does not close the small-\(\tau\) question for \(\Sigma\)-T.
The strongest negative point is that the schedule remains a permutation of indivisible jobs. Replacing a list of agents by rational masses changes only how their costs are aggregated; it does not create a new continuous decision variable. Theorem 8’s reduction also uses a support that grows with the construction, so it does not show hardness when the number of preference types is small. A sharper follow-up would ask whether \(\Sigma\)-T becomes easier for fixed or small \(\tau\).
That objection does not defeat the mirror, though. The question parameterized by \(m,\tau,L\) is still a computational question about a continuous population, and rational masses are exactly the input the programme is meant to study. The finite-profile correspondence is the high-multiplicity bridge, not evidence that the question is already answered or out of scope.
Theorem 12 is harder to resist. Its best mirror uses two ranking types, each with mass \(1/2\), and minimizes \(\bigl(\sum_t \mu_t f_t(\pi)^p\bigr)^{1/p}\) for \(f\in\{T,E,D\}\). Replicating each group preserves the optimum up to a common factor. Two large constituencies with identical rankings are a plausible regime, and the types retain every distinction the paper’s objective uses. The reduction’s dependence on the number of jobs does not count against the mirror: the question is whether this population representation is sensible, not whether continuity changes the answer.
Nor does the discrete permutation output disqualify either question. ChoCo continuizes the population; the paper’s jobs and schedule can remain discrete. For the same reason, the fact that every rational-mass instance can be scaled to a finite profile is not a collision with prior continuous work. The paper gives no continuous computational treatment that already answers these weighted optimization problems.
So the honest case against is limited: Theorem 8 does not establish hardness at small support, and the empirical case for low-support city preferences is plausible rather than demonstrated. Theorem 12 supplies a fixed-support mirror anyway. I cannot make the requested universal negative case honestly: at least the two-type \(L_p\) mirror survives the stated standard, so this case should not defeat the proponent’s anchors.
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.