| paper | d4-conf-ecai-2024-0221 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
other→P discrete result → its continuous mirror
Answer: Feasibility and exact minimization are polynomial-time solvable in \(m,\tau,L\), with a rational optimal plan. Additive approximation is polynomial-time solvable in \(m,\tau,L,\log(1/\varepsilon)\) by returning that exact plan. · discrete side: other · adjudication: proved
full proof & adversarial review →
Proposition 4.1
statement extracted from the paper’s text layer
Given projects \(P\), work packages \(W\), months \(M\), and a finite support \(T\) of complete researcher profiles with rational masses \(\mu_t\) summing to \(1\), each profile specifies cost \(e_t\), capacity \(\tau_{t,m}\), package eligibility, and target dedication \(q_{t,p,m}\). The instance also gives per-capita package requirements \(d_w\), project budgets \(b_p\), and nonnegative rational weights \(\alpha,\beta,\gamma\). Choose average dedication \(y_{t,w,m}\ge 0\), zero for ineligible packages, with \(\sum_w y_{t,w,m}\le\tau_{t,m}\), so that \(\sum_t\mu_t\sum_{m\in[w_s,w_e]}y_{t,w,m}\ge d_w\) for each package. Let \(z_{t,p,m}=\sum_{w\in p}y_{t,w,m}\) and \(c_p=\sum_t\mu_t e_t\sum_{w\in p,m}y_{t,w,m}\). Find a feasible plan minimizing \(\alpha\sum_t\mu_t\sum_{p,m}(z_{t,p,m}-q_{t,p,m})^2+\beta\sum_p\min(0,c_p-b_p)^2+\gamma\sum_p\max(0,c_p-b_p)^2\), or report infeasibility; for approximate computation, return an \(\varepsilon\)-optimal plan. Measure input size in the support and planning dimensions and binary input length.
A convex quadratic workforce-allocation model over a finite distribution of complete staffing profiles, with per-unit dedication variables, per-capita package requirements and budgets, and the paper’s preference-deviation and soft-budget penalties.
The mirror covers the static soft-budget optimization in Equations (12) and (13). It leaves the hard-budget formulation, the stochastic robust extension, and the paper’s empirical and scalability claims outside the anchor.
I would make one narrow lead case: a cohort version of the paper’s soft-budget RPP. The continuous object is the workforce, with mass representing fractions of researchers who share the same full RPP profile. It is not the project, the budget, or the uncertainty that becomes continuous.
My anchor is Proposition 4.1, proved by the authors (its proof is in the supplementary material). It states that the soft-constrained optimization problem in Equation (12) can be posed as the constrained least-squares problem in Equation (13): minimize \(\alpha\lVert Ax-t\rVert_2^2+\beta\lVert v\rVert_2^2+\gamma\lVert u\rVert_2^2\), subject to \(Dx\ge d\), \(Tx\le\tau\), \(Bx-b\le u\), \(Bx-b\ge v\), \(u\ge0\), and \(v\le0\). Here \(u\) and \(v\) capture, respectively, positive and negative project-budget deviations. This is a formulation result, not a theorem that the problem is in P. The paper computes with the formulation using a constrained least-squares solver, so it is a computational anchor of the kind allowed in the prompt.
Call the mirror Cohort-RPP\(_\infty\). An instance has projects \(P\), work packages \(W\), months \(M\), and a finite support \(T\) of researcher types with rational masses \(\mu_t\ge0\), where \(\sum_{t\in T}\mu_t=1\). A type fully specifies the RPP information relevant to a researcher: hourly cost \(e_t\), monthly capacity \(\tau_{t,m}\), work-package eligibility, and target dedication \(q_{t,p,m}\). The instance also gives per-capita work-package requirements \(d_w\), project budgets \(b_p\), and objective weights \(\alpha,\beta,\gamma\). These are the intensive versions of total requirements and budgets for a workforce of size \(N\), divided by \(N\).
The decision variable \(y_{t,w,m}\) is the average monthly dedication to package \(w\) by a unit of mass of type \(t\). It is zero when type \(t\) is ineligible, and otherwise satisfies \(0\le y_{t,w,m}\le\tau_{t,m}\), with \(\sum_w y_{t,w,m}\le\tau_{t,m}\). Each package must receive its required dedication: \(\sum_t\mu_t\sum_{m\in[ w_s,w_e]}y_{t,w,m}\ge d_w\). Define the type’s dedication to project \(p\) in month \(m\) as \(z_{t,p,m}=\sum_{w\in p}y_{t,w,m}\), and per-capita project spending as \(c_p=\sum_t\mu_t e_t\sum_{w\in p,m}y_{t,w,m}\). The problem is to find a feasible \(y\) minimizing
\(\alpha\sum_t\mu_t\sum_{p,m}(z_{t,p,m}-q_{t,p,m})^2+\beta\sum_p\min(0,c_p-b_p)^2+\gamma\sum_p\max(0,c_p-b_p)^2\).
A solution is an optimal type-level dedication plan, or an infeasibility report. For a complexity version, the solver can return an \(\varepsilon\)-optimal feasible plan. The parameters are the number of supported types \(\tau=|T|\), projects, packages, months, input bit length, and \(\log(1/\varepsilon)\).
A plausible regime is a large research consortium or multi-institution grant portfolio with thousands of researchers but a comparatively small set of standardized staffing profiles: for example, recurring combinations of role, contract cost, time cap, project eligibility, and target workload. The number of people \(N\) can then greatly exceed the number of distinct profiles \(\tau\). Each researcher within a type is interchangeable for everything the RPP model uses. This is a scenario claim, not a claim that every research institute has such a workforce. The paper’s actual setting, with personal preferences and a small set of projects, is not itself compelling evidence for that regime.
This remains the authors’ underlying allocation problem: it still assigns dedication to the same work packages, respects the same capacities and project costs, and minimizes the same preference and budget deviations. Aggregation is defensible because researchers in a type have identical constraints and targets; averaging their plans preserves linear constraints and cannot increase the squared preference-deviation objective. The paper already permits real-valued dedication, so this mirror does not add an integral-hours assumption. It makes the population a distribution and expresses requirements and budgets per capita.
I expect this mirror to be Class A, in the usual approximate convex-optimization sense. Proposition 4.1 gives the direct route: the type-level problem is a constrained least-squares optimization of size polynomial in the listed support and instance dimensions. It is an interesting compression and high-multiplicity formulation, though not a new discovery that convex optimization can solve the paper’s problem. Further questions include whether a discrete workforce plan with integral assignments can be recovered with controlled additive error, and how that approximation depends on \(N\) and \(\tau\).
The scope is deliberately limited to the soft-budget RPP allocation captured by Proposition 4.1. I am not anchoring the paper’s stochastic-robust extension: it is motivated by uncertainty in project data, not by a continuous population, and no separately numbered computational result there strengthens this case.
The weakest point is that the paper’s decisions are already fractional and its named anchor establishes a least-squares formulation rather than a hardness result or a population-size-independent algorithm. Also, target preferences may be personal enough that a faithful type must include so much detail that \(\tau\) approaches \(N\). If that happens, the mirror loses its compression. The case survives only for the stated cohort regime, where standardized profiles are a credible feature of the planning problem.
The best objection starts with the anchor: Proposition 4.1 is a reformulation of the soft-budget objective as constrained least squares. It does not give a complexity classification or an algorithmic result; the paper’s computational evidence is that standard solvers handle its instances quickly. So it is a thin target for a programme about the complexity landscape of continuous societies.
The stronger cohort mirror is mathematically sound, which limits the negative case. If researchers in a type share the same targets, costs, capacities, and eligibility, the constraints and costs depend on their aggregate allocation. For their preference term, averaging their plans cannot worsen the objective:
\[
\sum_{i=1}^{n_t}\lVert z_i-q_t\rVert^2
\;\ge\;
n_t\lVert \bar z_t-q_t\rVert^2.
\]
That gives an exact type-level quotient of the finite workforce model. But it leaves the central computation as the same convex quadratic optimization the paper already formulates. Researchers’ dedication is already divisible into real-valued hours, so the population limit removes no integrality barrier and exposes no new optimization machinery. The paper has already made the problem a least-squares model and solved it with an off-the-shelf solver.
The proposed low-support regime also needs the full RPP profile to repeat. A type includes project-specific targets and work-package eligibility, so grouping people by broad labels such as “permanent” and “contracted” would be faithful only if those other inputs also match. The paper gives no evidence that the complete profiles remain few as the workforce and project portfolio grow. With a fixed portfolio and workload, per-capita requirements and budgets shrink as the workforce grows, while positive per-person targets remain; the limit then represents a vanishing share of staff doing the work. Scaling the portfolio and workload with the workforce avoids that, but produces a replicated convex planning problem whose type aggregation is still the same exact QP quotient.
That is a case for low marginal value, not a universal defeat. A large consortium with repeated full profiles and a proportionally growing portfolio is plausible, and the cohort question is well-posed there. I cannot honestly establish that no worthwhile mirror exists in any scenario. The strongest negative verdict is that this paper offers little of the complexity-theoretic gap ChoCo is meant to chart: its likely mirror is an exact compression of an optimization problem that is already continuous in its decisions and already tractable by standard convex optimization.
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.