Answer: Exactly polynomial-time solvable, with bit complexity \(\bigl(m\tau^2(L+1)\bigr)^{O(1)}\); the numerical horizon \(H\) enters only through its binary encoding in \(L\).
Theorem 1 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateFinding an optimal policy for the online resource allocation problem is NP-hard.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite horizon \(H\), resource capacities per capita \(a_r\), and a deterministic known stream of cohorts with rational masses \(\mu_{t,k}\) and task attributes \((v_k,d_k,q_k)\), find a welfare-maximizing feasible schedule. Choose accepted mass \(x_{t,k}\) with \(0 \le x_{t,k} \le \mu_{t,k}\), set \(x_{t,k}=0\) when the task cannot finish by \(H+1\), and require \(\sum_{(t,k):\,t \le u < t+d_k} q_{k,r}x_{t,k} \le a_r\) for every resource \(r\) and time \(u\). Maximize \(\sum_{t,k} v_k x_{t,k}\), with each individual task receiving its full requested bundle or being rejected.
A society is given by its support: a list of \(\tau\) arrival-tagged types \((t,k)\) with positive binary rational masses \(\mu_{t,k}\), summing to \(1\). Here \(\tau\) is the support size, not the number of possible types.
There are \(m\ge 1\) resources with positive rational per-capita capacities \(a_r\), and a finite discrete horizon \(H\ge 1\). Each listed arrival time satisfies \(t\in\{1,\ldots,H\}\); task attributes are a nonnegative rational value \(v_k\), a positive integer duration \(d_k\), and a resource bundle \(q_k\in\mathbb Z_{\ge 0}^{m}\). All numerical inputs are binary encoded; \(L\) is their total bit length.
The entire stream is known in advance. Choose accepted masses \(x_{t,k}\in[0,\mu_{t,k}]\). Every accepted individual starts immediately at \(t\), receives its full bundle throughout \([t,t+d_k)\), and completes at \(t+d_k\); other individuals are rejected. Mass within a cohort may be split between acceptance and rejection.
Require \(x_{t,k}=0\) if \(t+d_k>H+1\), and \(\sum_{(t,k):\,t\le u<t+d_k}q_{k,r}x_{t,k}\le a_r\) for every \(r\in\{1,\ldots,m\}\) and \(u\in\{1,\ldots,H\}\). Welfare is \(\sum_{t,k}v_kx_{t,k}\).
Is finding a welfare-maximizing feasible schedule solvable in polynomial time, or is it NP-hard? State running times in \(m\), \(\tau\), \(L\), and \(H\), accounting for the binary encoding of \(H\).
The discrete problem with indivisible tasks is NP-hard even with one resource and a deterministic stream known in advance. That result does not establish the complexity of the mass formulation above.
The mass formulation is solvable exactly in polynomial time, even when \(H\) is binary encoded. A valid bit-complexity bound is
\[ \bigl(m\tau^2(L+1)\bigr)^{O(1)}. \]
The key is to retain capacity constraints only at distinct arrival times, rather than at all \(H\) time steps.
Index the listed support by \(i\in\{1,\ldots,\tau\}\), writing its data as \(t_i,d_i,q_{i,r},v_i,\mu_i\). Define the completion time \(e_i=t_i+d_i\), and let
\[ I=\{i:e_i\le H+1\},\qquad n=|I|. \]
Every cohort outside \(I\) must have \(x_i=0\), so it can be removed from the optimization. If \(n=0\), rejecting every cohort is optimal. Henceforth assume \(n\ge1\).
Let \(S=\{t_i:i\in I\}\) be the set of distinct eligible arrival times. Its size satisfies \(|S|\le n\le\tau\).
For a nonnegative vector \(x=(x_i)_{i\in I}\), define the load on resource \(r\) at time \(u\) by
\[ \ell_r(u)=\sum_{\substack{i\in I\\t_i\le u<e_i}}q_{i,r}x_i. \]
Lemma. The inequalities \(\ell_r(u)\le a_r\) for every \(u\in\{1,\ldots,H\}\) and every resource \(r\) are equivalent to the inequalities \(\ell_r(s)\le a_r\) for every \(s\in S\) and every resource \(r\).
Proof. Necessity follows because every \(s\in S\) lies in \(\{1,\ldots,H\}\).
For sufficiency, fix a time \(u\). If no eligible arrival occurs by \(u\), its load is zero. Otherwise, let \(s=\max\{t_i:i\in I,\ t_i\le u\}\).
Consider any cohort active at \(u\). Its arrival time satisfies \(t_i\le u\), so the definition of \(s\) gives \(t_i\le s\). Moreover, \(s\le u<e_i\). Thus this cohort was also active at \(s\). Consequently, the set of cohorts active at \(u\) is contained in the set active at \(s\).
Since \(q_{i,r}x_i\ge0\), this containment implies \(\ell_r(u)\le\ell_r(s)\le a_r\). This holds for every resource and every time. \(\square\)
The strict inequality \(s<e_i\) correctly accounts for the half-open service interval: cohorts completing at \(s\) consume no capacity at \(s\).
For \(s\in S\), \(r\in\{1,\ldots,m\}\), and \(i\in I\), define
\[ A_{(s,r),i}=q_{i,r}\mathbf{1}_{\{t_i\le s<e_i\}}. \]
Solve the linear program with objective
\[ \max\sum_{i\in I}v_i x_i, \]
subject to the cohort bounds
\[ 0\le x_i\le\mu_i\qquad(i\in I) \]
and the capacity constraints
\[ \sum_{i\in I}A_{(s,r),i}x_i\le a_r \qquad(s\in S,\ r\in\{1,\ldots,m\}). \]
There are \(n\le\tau\) variables and at most \(m|S|+2n\le(m+2)\tau\) inequalities.
By the lemma, this program describes exactly the feasible accepted-mass vectors after removing the compulsory rejections. Its objective is exactly their welfare. Splitting cohort mass is permitted by the problem, so every feasible vector of this program is a valid schedule.
All coefficients are rational. The zero vector is feasible, and the bounds \(0\le x_i\le\mu_i\) make the feasible set compact. Therefore an optimum exists.
We now apply the standard rational linear-programming theorem: an explicitly represented rational linear program can be solved in polynomial bit time, returning an exact rational optimum when it is feasible and bounded. These hypotheses have all been verified above. Polynomial-time LP algorithms and the polynomial encoding size of optimal vertices are covered in [Goemans’s linear-programming notes, Sections 11–13](https://ocw.mit.edu/courses/6-854j-advanced-algorithms-fall-2008/908fe54d659623efadda2d033b895caf_notes_lp.pdf).
Append \(x_i=0\) for the removed cohorts to obtain an optimal schedule for the original instance.
Computing each \(e_i=t_i+d_i\) and comparing it with \(H+1\) uses integers of \(O(L+1)\) bits. Sorting eligible arrival times takes \(O(\tau\log(\tau+1)(L+1))\) bit operations.
The dense capacity matrix has at most \(m\tau^2\) entries. Each entry is either zero or an input bundle coordinate. Including the bounds, right-hand sides, and objective, the LP has total encoding length
\[ B=O\!\left(m\tau^2(L+1)\right). \]
A direct construction also takes \(O(m\tau^2(L+1))\) bit operations. Applying polynomial-time rational LP therefore yields the overall bound
\[ T(m,\tau,L,H)=\bigl(m\tau^2(L+1)\bigr)^{O(1)}. \]
There is no dependence on the numerical value of \(H\) beyond its contribution to \(L\), which includes its binary encoding length \(\Theta(\log(H+1))\). Since the support and capacities are explicitly listed, \(\tau,m=O(L)\), so this is polynomial in the full input length.
For comparison, explicitly constructing constraints for all time steps gives a dense LP of encoding length \(O((mH+\tau)\tau(L+1))\), and hence a bound of \(((mH+\tau)\tau(L+1))^{O(1)}\). That bound is polynomial in the numerical horizon and can be exponential in its binary encoding length. The arrival-time reduction eliminates this issue.
The indivisible-task hardness result does not transfer: indivisibility imposes discrete acceptance choices, whereas the formulation here permits precisely the continuous variables used by the LP.
⟨structured verdict parsed — rendered above⟩
The output proves the requested polynomial-time classification. The arrival-time reduction is correct, the linear program exactly represents the mass formulation, and its encoding size is polynomial even when \(H\) is binary encoded. No major or minor mathematical issues were found.
The condition \(e_i=t_i+d_i>H+1\) forces \(x_i=0\) in the original problem. Removing precisely these variables therefore preserves feasibility and welfare. If \(n=0\), the all-zero vector is the only feasible accepted-mass vector and is optimal.
For retained cohorts, their arrival times remain in \(\{1,\ldots,H\}\), so every proposed capacity-check time belongs to the required domain.
Necessity follows by restricting the original constraints to \(S\).
For sufficiency, the proof fixes an arbitrary required time \(u\). If no eligible cohort has arrived, the load is zero. Otherwise, the latest eligible arrival \(s\le u\) exists because the support is finite.
For every cohort active at \(u\), its arrival satisfies \(t_i\le s\), and its completion satisfies \(s\le u<e_i\). Thus it is also active at \(s\). The resulting containment of active sets gives the load inequality because every summand \(q_{i,r}x_i\) is nonnegative.
This establishes the claim for every resource and every required time. It does not assume that completions coincide with arrivals or that arrival times are consecutive.
The strict completion inequality correctly handles simultaneous completions and arrivals: a cohort completing at \(s\) is absent from the load at \(s\).
The matrix entries encode precisely the cohorts active at each retained check time. The cohort bounds match the permitted acceptance and rejection splitting. By the proved lemma, the capacity rows enforce all original capacity constraints.
Conversely, every feasible original schedule restricts to a feasible LP vector. Appending zeros to an LP solution restores the compulsory rejections. The objective is unchanged in both directions.
There are \(n\) variables and \(m|S|+2n\) inequalities when both bounds are counted explicitly. The stated upper bound \((m+2)\tau\) is correct.
All LP data are rational. The zero vector is feasible because capacities are positive. The feasible region is closed and contained in the bounded box defined by the cohort bounds, hence compact. Its linear objective therefore attains a finite optimum.
The prover states the relevant rational LP theorem with the needed exact-output and bit-complexity guarantees. Its application satisfies the hypotheses: explicit rational data, feasibility, and boundedness. The cited notes discuss polynomial-size vertex representations in Section 11 and polynomial-time LP algorithms, exact-optimality recovery, and bit complexity in Section 13. The citation supports the invocation. [Goemans’s linear-programming notes](https://ocw.mit.edu/courses/6-854j-advanced-algorithms-fall-2008/908fe54d659623efadda2d033b895caf_notes_lp.pdf).
The argument therefore establishes production of an optimal accepted-mass vector, rather than merely an approximate objective value.
Adding binary integers to compute \(e_i\) and \(H+1\) requires only \(O(L+1)\)-bit operands and results. The stated sorting bound is valid using comparisons of this bit length.
The capacity matrix has at most \(m\tau^2\) entries. Every entry is zero or an input coordinate, with encoding length \(O(L+1)\). Bounds, objective coefficients, right-hand sides, and dimension information fit within the stated total bound
\(B=O(m\tau^2(L+1))\).
The direct construction bound also covers eligibility checks, sorting, and coefficient assembly; here \(m\ge1\) and \(\tau\ge1\), the latter following from positive masses summing to one.
Consequently, the overall bound
\(T(m,\tau,L,H)=(m\tau^2(L+1))^{O(1)}\)
follows from polynomial bit-time rational LP optimization. No iteration over the numerical horizon is required.
The assertions \(\tau,m=O(L)\) follow from the explicitly listed support masses and resource capacities. The comparison with constructing all \(H\) time-step constraints is also correct: its stated bound can be exponential in the horizon’s binary encoding length.
The argument accommodates \(H=1\), duplicate arrival times, zero resource bundles, zero values, completion exactly at \(H+1\), and arbitrarily large binary-encoded durations. None invalidates the reduction or LP theorem application.
The distinction from indivisible-task hardness is appropriate: the proof uses precisely the continuous acceptance variables authorized by the task.
Required feedback: None. The write-up resolves the assigned question without an additional lemma or clarification.
⟨structured verdict parsed — rendered above⟩
Tier: machine-proved, adversarially reviewed by an independent model. No human has checked this proof. Generated from pipeline artifacts by tools/atlas_build.py.