Answer: Polynomial-time solvable.
Lemma 1 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateThe social optimum is the same as the maxi- mum weight matching of G. Thus, we can use the maximum weight matching algorithm to compute the social optimum. The maximum weight match- ing is a classical network problem and can be solved in poly- nomial time [13, 7, 8]. We choose to implement the Hungar- ian algorithm [13, 18] because of its simplicity.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given types \(t\) with rational masses \(\mu_t\), machine classes \(j\) with per-population supplies \(q_j\), weights \(w_{tj}\), and integer parallelism caps \(k_t\), find the maximum welfare and an optimal assignment of mass to integral bundles. For bundle \(a\in\mathbb Z_{\ge 0}^{J}\), let \(y_{t,a}\) be the mass of type \(t\) receiving it; solve \(\max_{y\ge 0}\sum_{t,a} y_{t,a}\sum_j a_jw_{tj}\), subject to \(\sum_a y_{t,a}=\mu_t\) for each \(t\), \(\sum_{t,a}a_jy_{t,a}\le q_j\) for each \(j\), and \(y_{t,a}=0\) whenever \(\sum_j a_j>k_t\).
A society is given by its support: the list of \(\tau\) types with positive masses \(\mu_t\), each a binary rational, with \(\sum_t\mu_t=1\). Here \(\tau\) is the support size, not the number of possible types.
There are \(m\ge1\) machine classes, with binary rational supplies \(q_j\ge0\) per unit population and binary rational weights \(w_{tj}\ge0\). Each type has a positive integer parallelism cap \(k_t\), encoded in binary; weights need not be normalized.
A bundle comprises whole machine units: \(A_t=\{a\in\mathbb Z_{\ge0}^{m}:\sum_j a_j\le k_t\}\). Multiple units of the same class are permitted, and the empty bundle is permitted.
An assignment splits each type's mass among bundles: \(y_{t,a}\ge0\), with \(\sum_{a\in A_t}y_{t,a}=\mu_t\) and \(\sum_t\sum_{a\in A_t}a_jy_{t,a}\le q_j\). Supplies may remain unused.
Its welfare is \(\sum_t\sum_{a\in A_t}y_{t,a}\sum_j a_jw_{tj}\). The computational problem is to find the exact maximum and an optimal assignment, represented by its positive bundle masses.
Is this continuous welfare-maximization problem solvable in polynomial time, or is it NP-hard? State running times in \(m\), \(\tau\), the total input bit length \(L\), and the caps \(k_t\).
For finitely many users and individually listed machines, the maximum welfare with nonnegative additive weights and per-user parallelism caps equals a maximum-weight bipartite matching value and is computable in polynomial time. [Source](https://arxiv.org/abs/cs/0502019).
No result settling exactly the mass-allocation problem specified above was identified in the literature search.
The problem is solvable exactly in polynomial time in \(m\), \(\tau\), and the total input bit length \(L\). The caps affect the bit complexity through their binary encodings, rather than through their numerical values.
An optimal assignment can be represented using at most \(\tau(m+1)\) positive bundle masses. The key is that every feasible average allocation can be realized using only the empty bundle and bundles containing \(k_t\) units of one class.
For each type \(t\) and class \(j\), define the aggregate number of allocated units per unit population by
\(x_{tj}=\sum_{a\in A_t}a_jy_{t,a}\).
Every feasible assignment satisfies
\(x_{tj}\ge 0,\qquad \sum_{j=1}^{m}x_{tj}\le \mu_tk_t,\qquad \sum_{t=1}^{\tau}x_{tj}\le q_j.\)
Indeed, the type constraint follows from
\(\sum_jx_{tj}=\sum_{a\in A_t}y_{t,a}\sum_ja_j\le k_t\sum_{a\in A_t}y_{t,a}=\mu_tk_t.\)
By additivity, its welfare equals
\(\sum_{t=1}^{\tau}\sum_{j=1}^{m}w_{tj}x_{tj}.\)
Conversely, suppose \(x\) satisfies these aggregate constraints. Let \(e_j\) be the \(j\)-th coordinate vector. Since \(k_t\) is a positive integer, both \(0\) and \(k_te_j\) belong to \(A_t\). Set
\(y_{t,k_te_j}=\dfrac{x_{tj}}{k_t},\qquad y_{t,0}=\mu_t-\dfrac{\sum_jx_{tj}}{k_t},\)
and set every other bundle mass to zero.
These masses are nonnegative and sum to \(\mu_t\). Their class-\(j\) consumption is exactly
\(\sum_t k_t y_{t,k_te_j}=\sum_t x_{tj}\le q_j,\)
and their welfare is exactly \(\sum_{t,j}w_{tj}x_{tj}\).
Thus the original problem is equivalent, in both directions and with identical objective values, to the linear program
\(\displaystyle \max_{x\ge 0}\ \sum_{t,j}w_{tj}x_{tj}\)
subject to
\(\displaystyle \sum_jx_{tj}\le \mu_tk_t\quad\text{for every }t,\qquad \sum_tx_{tj}\le q_j\quad\text{for every }j.\)
This program has \(m\tau\) variables and \(\tau+m\) inequality constraints. Its feasible region is nonempty, since \(x=0\) is feasible, and compact, since \(0\le x_{tj}\le\mu_tk_t\). Consequently, an optimum exists.
The compact program already establishes polynomial-time solvability by exact rational linear programming: its encoding length is polynomial in \(m,\tau,L\), including the products \(\mu_tk_t\).
An explicit arithmetic-operation bound follows from a transportation formulation. Write
\(b_t=\mu_tk_t,\qquad B=\sum_tb_t,\qquad Q=\sum_jq_j.\)
Construct a directed bipartite network with:
Include all arcs from supply nodes to demand nodes, without upper capacities. An arc from type \(t\) to class \(j\) has cost \(-w_{tj}\); every arc incident to an additional node has cost zero.
To verify the reduction, let \(x\) satisfy the compact constraints and put \(X=\sum_{t,j}x_{tj}\). Extend \(x\) to a flow by assigning:
| Arc | Flow |
|---|---|
| Type \(t\) to class \(j\) | \(x_{tj}\) |
| Type \(t\) to additional demand node | \(b_t-\sum_jx_{tj}\) |
| Additional supply node to class \(j\) | \(q_j-\sum_tx_{tj}\) |
| Additional supply node to additional demand node | \(X\) |
All these flows are nonnegative. The additional supply node sends \(Q-X+X=Q\), and the additional demand node receives \(B-X+X=B\), so every balance equation holds.
Conversely, in any feasible transportation flow, the real type-to-class flows satisfy the compact inequalities, because the remaining outgoing and incoming flows are nonnegative. Its cost is exactly \(-\sum_{t,j}w_{tj}x_{tj}\). Hence minimum cost equals negative maximum welfare.
The network has
\(N=\tau+m+2,\qquad E=(\tau+1)(m+1).\)
It is feasible, and every arc flow is bounded by the total supply \(B+Q\), so its objective is bounded. Orlin’s strongly polynomial algorithm for uncapacitated minimum-cost flow therefore gives the arithmetic-operation bound
\(\displaystyle O\!\left(N\log N\left(E+N\log N\right)\right).\)
This is the standard bound from [Orlin, *A Faster Strongly Polynomial Minimum Cost Flow Algorithm*](https://pubsonline.informs.org/doi/10.1287/opre.41.2.338).
For exact rational inputs, one may first multiply all supplies and demands by a common denominator, and separately multiply all costs by a common denominator. The products of the input denominators have bit length \(O(L)\); the resulting integer data likewise have polynomial bit length. These scalings preserve optimality, and scaling the resulting flows back recovers the exact rational solution.
Thus the bit running time is \(\operatorname{poly}(m,\tau,L)\). The displayed arithmetic bound is independent of the numerical values of the caps. In particular, there is no factor proportional to \(k_t\), nor any enumeration of the \(\binom{k_t+m}{m}\) possible bundles.
After computing an exact optimal \(x\), apply the formulas from Section 1 and output only positive masses.
For each type, there are at most \(m\) positive masses on bundles \(k_te_j\), plus one on the empty bundle. Hence the output contains at most \(\tau(m+1)\) positive bundle masses.
Reconstruction takes \(O(m\tau)\) rational arithmetic operations. Each bundle coordinate is either zero or the binary-encoded integer \(k_t\), and the rational masses have polynomial encoding length. Even when bundle vectors are written densely, the complete output has polynomial size.
This settles the specified mass-allocation problem, including exact welfare computation and an explicit optimal assignment.
⟨structured verdict parsed — rendered above⟩
Result: proved. The prover establishes exact polynomial-time solvability of the specified continuous problem, including a polynomial-size optimal assignment. No major or minor mathematical issues were found.
The definition
\[
x_{tj}=\sum_{a\in A_t}a_jy_{t,a}
\]
is well-defined because each bundle set is finite.
Nonnegativity follows from nonnegative bundle coordinates and masses. The displayed derivation of
\[
\sum_jx_{tj}\le\mu_tk_t
\]
correctly uses the bundle cap and the type’s mass equation. The class supply constraints translate directly to
\[
\sum_tx_{tj}\le q_j.
\]
The welfare identity is correct: all sums are finite, and the objective is additive in machine units. There are no bundle-dependent terms that the aggregate formulation discards.
Finding: Every feasible original assignment produces a feasible aggregate allocation with exactly the same welfare.
The converse construction is valid under the task’s explicit assumptions:
The aggregate row constraint makes the proposed empty-bundle mass nonnegative. The masses sum exactly to \(\mu_t\). Each nonempty bundle contributes only to its designated class, so the resulting class consumption and welfare are precisely those claimed.
Finding: The compact formulation is an exact equivalence, rather than a relaxation. This settles the central mathematical issue.
The compact feasible region contains the zero allocation. It is closed and bounded by the coordinate bounds stated in the proof. Its objective is continuous.
Finding: The compactness argument correctly establishes attainment of an optimum, which the reconstruction transfers to the original problem.
The network’s total supply and total demand both equal \(B+Q\).
For the proposed extension of an aggregate allocation, the row and column inequalities make every slack flow nonnegative. Each real supply node sends its prescribed supply, and each real demand node receives its prescribed demand. The two additional-node balance calculations are correct, including the flow \(X\) between the additional nodes.
Conversely, nonnegative slack flows force the real type-to-class flows to obey the compact inequalities. Only real type-to-class arcs carry nonzero costs, so the cost is exactly the negative of the original welfare.
The node and arc counts are correct:
\[
N=\tau+m+2,\qquad E=(\tau+1)(m+1).
\]
Finding: Feasibility, objective preservation, and both directions of the reduction are fully verified.
The stated arithmetic-operation bound
\[
O\!\left(N\log N\left(E+N\log N\right)\right)
\]
matches the published bound for Orlin’s uncapacitated minimum-cost flow algorithm. [Orlin’s paper](https://pubsonline.informs.org/doi/10.1287/opre.41.2.338)
The constructed instance meets the relevant conditions: it is a finite uncapacitated minimum-cost flow problem, has balanced node requirements, is feasible, and has a bounded objective. Negative real-arc costs do not invalidate the application. In this network, every arc flow is bounded by total supply, as the prover states.
The independent rational linear programming argument also applies: the compact program has polynomially many explicitly encoded variables and constraints, rational data, a nonempty feasible region, and a finite attained optimum.
Finding: Both the polynomial-time conclusion and the displayed arithmetic-operation bound are justified.
Multiplication by the binary-encoded integer \(k_t\) increases the encoding length of \(\mu_tk_t\) only polynomially in the input length.
The denominator-scaling claim is correct. Products of input denominators have bit length bounded by their total encoded length. The sums defining \(B\) and \(Q\) introduce no obstruction to using those common denominators. Separate positive scalings of balances and costs preserve the optimization problem after flows are scaled back.
Strong polynomiality supplies polynomial control of intermediate encoding lengths, so the arithmetic bound is consistent with polynomial bit complexity.
Finding: The proof correctly distinguishes arithmetic-operation complexity from bit complexity. There is no dependence proportional to the numerical caps.
The reconstruction produces at most \(m+1\) positive bundle masses per type. Omitting zero masses is valid and preserves all constraints. The rational masses have polynomial encoding length, and writing bundle coordinates densely still gives polynomial total output size.
The argument covers zero supplies, zero weights, unused supply, a single machine class, and vanishing slack masses. Positive type masses and positive caps are supplied by the task. No unhandled degenerate case breaks the proof.
Finding: The requested exact welfare and explicit optimal assignment are both addressed.
No repair is required. The proof resolves the problem as specified.
⟨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.