Answer: Polynomial-time solvable
Theorem 3 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateFor any bin packing instance, a $\frac{4}{3}$-OMMS allocation exists.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given recipient types \(t\in T\) with rational masses \(\mu_t\) summing to \(1\), \(d\) item classes with rational per-recipient supplies \(q_j\), and type-specific sizes \(s_{tj}\), clear denominators with \(D\). For each \(r\), form the finite instance with \(rD\mu_t\) recipients of type \(t\) and \(rDq_j\) items of class \(j\); let \(\kappa_t(r)\) be the paper’s bin-packing MMS and set \(\kappa_t^\infty=\sup_r\kappa_t(r)\). Determine the complexity of finding a finite-support mass allocation \(x_{t,b}\ge0\), where \(b\in\mathbb Z_{\ge0}^d\) is an integral bundle, satisfying \(\sum_b x_{t,b}=\mu_t\), \(\sum_{t,b}b_jx_{t,b}=q_j\), and \(c_t(b)\le\frac43\kappa_t^\infty+\frac43\) whenever \(x_{t,b}>0\).
A society is given by its support: a list \(T\) of \(\tau\) recipient types with positive binary-rational masses \(\mu_t\), where \(\sum_t\mu_t=1\); \(\tau\) is the support size, not the number of possible types.
There are \(m=d\ge1\) item classes with binary-rational supplies \(q_j\ge0\) per recipient and binary-rational type-specific sizes \(0<s_{tj}\le1\). Bins have capacity \(1\). For an integral bundle \(b\in\mathbb Z_{\ge0}^d\), let \(c_t(b)\) be its optimal bin-packing cost under sizes \(s_{tj}\), with \(c_t(0)=0\).
Let \(D\) be the least common multiple of the denominators of all masses and supplies. For each integer \(r\ge1\), put \(n_r=rD\) and define
\(\kappa_t(r)=\min\{\max_{1\le\ell\le n_r}c_t(b^\ell): b^\ell\in\mathbb Z_{\ge0}^d,\ \sum_{\ell=1}^{n_r}b^\ell=rDq\}\), allowing empty bundles; set \(\kappa_t^\infty=\sup_{r\ge1}\kappa_t(r)\).
A mass allocation is a finitely supported family of nonnegative rational numbers \(x_{t,b}\) satisfying \(\sum_bx_{t,b}=\mu_t\) and \(\sum_{t,b}b_jx_{t,b}=q_j\) for every class \(j\). Its ordinal approximation guarantee is \(c_t(b)\le\frac43\kappa_t^\infty+\frac43\) whenever \(x_{t,b}>0\). The benchmark values are defined by the input, not supplied by an oracle; let \(L\) be the total input bit length.
Can a mass allocation with this \(\frac43\) ordinal guarantee and additive loss \(\frac43\) always be found in time polynomial in \(m,\tau,L\), or is attaining this guarantee NP-hard?
For finite societies, an oracle-free polynomial-time algorithm achieves \(c_i(A_i)\le\frac43\kappa_i+\frac43\) for every recipient ([Li, Sun, Wang and Zhou](https://arxiv.org/html/2510.04425v1)). No result settling this replication-defined mass-allocation problem was located.
The problem is polynomial-time solvable. In fact, an oracle-free algorithm produces a mass allocation satisfying the stronger bound
\(\displaystyle c_t(b)\le \left\lceil \frac54\kappa_t^\infty+\frac14\right\rceil\)
for every supported bundle. The algorithm uses one-bin configurations, approximate knapsack optimization, and a finite rational distribution over integral bundles.
Throughout, all integers and rational numbers are represented in binary.
For every type \(t\),
\(\displaystyle \kappa_t^\infty=\kappa_t(1).\)
Indeed, concatenate \(r\) copies of a partition witnessing \(\kappa_t(1)\). This produces \(rD\) bundles with total item vector \(rDq\), each having cost at most \(\kappa_t(1)\). Consequently,
\(\displaystyle \kappa_t(r)\le \kappa_t(1)\)
for every positive integer \(r\). Since the supremum includes \(r=1\), equality follows.
This observation concerns the benchmark only; our algorithm does not compute it.
If \(q=0\), assigning the empty bundle to every type solves the problem. Henceforth suppose \(q\ne0\).
Fix one type, and temporarily suppress its subscript. Define its finite set of one-bin configurations by
\(\displaystyle \mathcal A=\left\{a\in\mathbb Z_{\ge0}^{m}:\sum_{j=1}^{m}s_ja_j\le1\right\}.\)
Finiteness follows from \(s_j>0\). Every unit vector belongs to \(\mathcal A\), because \(s_j\le1\).
Consider the configuration covering LP
\(\displaystyle \lambda=\min\left\{\sum_{a\in\mathcal A}y_a: \sum_{a\in\mathcal A}a_jy_a\ge q_j\ \text{for every }j,\quad y_a\ge0\right\}. \)
Writing \(Q=\sum_jq_j\), singleton configurations show that \(\lambda\le Q\). The optimum is attained: the LP has finitely many variables, and its feasible solutions with objective at most \(Q\) form a nonempty compact set.
Its dual is
\(\displaystyle \lambda=\max\left\{\sum_jq_j\pi_j: \pi_j\ge0,\quad \sum_ja_j\pi_j\le1\ \text{for every }a\in\mathcal A\right\}. \)
The singleton constraints imply \(0\le\pi_j\le1\), so the dual feasible region is compact.
Let \(k=\kappa_t(1)\). Packing the bundles of an optimal first-replication partition separately uses at most \(Dk\) bins. Dividing the multiplicity of each resulting configuration by \(D\) gives a feasible configuration LP solution with objective at most \(k\). Therefore,
\(\displaystyle \lambda\le k=\kappa_t^\infty.\)
The following construction approximates this fractional lower bound without enumerating \(\mathcal A\).
We prove the algorithmic fact needed below:
Lemma. In polynomial time, one can find polynomially many configurations \(a^i\in\mathcal A\) and nonnegative rational coefficients \(y_i\) such that
\(\displaystyle \sum_i y_i a^i\ge q, \qquad B:=\sum_i y_i<\frac54\lambda+\frac14. \)
All inequalities between vectors here are coordinatewise.
For a nonnegative rational vector \(\pi\), put
\(\displaystyle M(\pi)=\max_{a\in\mathcal A}\pi\cdot a.\)
We first describe a polynomial-time algorithm returning a feasible configuration \(a\) with
\(\displaystyle \pi\cdot a\ge\frac45M(\pi).\)
Let \(U_j=\lfloor1/s_j\rfloor\). No feasible configuration contains more than \(U_j\) items of class \(j\).
Represent the available \(U_j\) copies by binary packages: packages of multiplicities \(1,2,4,\ldots\), with the final package truncated so that their sum is \(U_j\). Every integer between \(0\) and \(U_j\) is a subset sum of these package multiplicities. To verify this, successive package multiplicities never exceed one plus the sum of the preceding multiplicities; induction then shows that the attainable subset sums form the entire required interval.
A package of multiplicity \(h\) has weight \(hs_j\) and profit \(h\pi_j\). Each package fits individually, and their total number \(N\) is polynomial in the input length. Optimizing feasible subsets of these packages is exactly the original configuration optimization problem.
If all package profits vanish, return the empty configuration. Otherwise, let \(p_{\max}\) be the largest package profit and set
\(\displaystyle K=\frac{p_{\max}}{5N}.\)
Round each package profit \(p\) down to \(\lfloor p/K\rfloor\). Each rounded profit is at most \(5N\), so their total is at most \(5N^2\). Dynamic programming over total rounded profit, storing the minimum attainable weight, solves the rounded instance in polynomial time using exact rational arithmetic.
For an optimal original subset, rounding loses less than \(NK=p_{\max}/5\). The returned subset consequently has original profit at least
\(\displaystyle M(\pi)-\frac{p_{\max}}5\ge\frac45M(\pi),\)
where the last inequality uses \(p_{\max}\le M(\pi)\), since the most profitable package fits individually.
For completeness, we give the recovery argument; approximate pricing alone does not establish the lemma.
We use the standard rational implementation of the central-cut ellipsoid method. Its relevant property is that, starting with a containing ball of radius \(R\), polynomially many rational cuts suffice to obtain an enclosing ellipsoid of volume smaller than a ball of radius \(\rho\), with running time polynomial in the dimension, cut encoding lengths, and \(\log(R/\rho)\). Each update preserves the intersection with the halfspace supplied by the cut. The underlying volume contraction is described in [Goemans’s ellipsoid notes](https://math.mit.edu/~goemans/18433S07/ellipsoid.pdf).
Fix \(\delta=1/8\), and consider a rational threshold \(h\). Start with the ball of radius \(m\) centered at the midpoint of \([0,1]^m\). At each queried center \(\pi\):
Every accepted point satisfies \(M(\pi)\le5/4\). Thus \((4/5)\pi\) is feasible for the full configuration dual, and acceptance implies
\(\displaystyle h\le q\cdot\pi\le\frac54\lambda.\)
We next show what can be recovered when the procedure makes sufficiently many cuts without acceptance.
Let \(S\) contain all configurations used in its cuts, together with all singleton configurations. Define
\(\displaystyle w_S=\max\left\{q\cdot\pi: \pi\ge0,\quad a\cdot\pi\le1\ \text{for every }a\in S\right\}. \)
Singleton configurations make its feasible region a subset of \([0,1]^m\), so its optimum is attained.
Set
\(\displaystyle U=\max_jU_j,\qquad \theta=\frac{\delta}{4(Q+1)},\qquad \rho=\frac{\theta}{8mU},\qquad u=\frac{1}{4mU}(1,\ldots,1). \)
Suppose \(w_S\ge h+\delta\), and let \(\pi^*\) attain \(w_S\). Consider
\(\displaystyle \bar\pi=(1-\theta)\pi^*+\theta u.\)
For every \(a\in S\), its coordinates are at most \(U\), and hence \(a\cdot u\le1/4\). Consequently,
\(\displaystyle a\cdot\bar\pi\le1-\frac{3\theta}{4}.\)
Each coordinate of \(\bar\pi\) is at least \(\theta/(4mU)\) and at most \(1-3\theta/4\). Also,
\(\displaystyle q\cdot\bar\pi \ge w_S-\theta Q \ge h+\frac{3\delta}{4}. \)
These margins show that the entire Euclidean ball of radius \(\rho\) around \(\bar\pi\) satisfies the box constraints, the constraints for \(S\), and \(q\cdot\pi\ge h\). Explicitly, a perturbation \(v\) with \(\lVert v\rVert_2\le\rho\) changes any configuration inner product by at most
\(\displaystyle \lVert a\rVert_2\rho\le mU\rho=\frac{\theta}{8},\)
and changes the objective by at most
\(\displaystyle Q\rho\le\frac{\delta}{32}.\)
Every ellipsoid update preserves this ball: the ball satisfies every original inequality used in a cut, and therefore also the corresponding central halfspace.
It follows that, once the ellipsoid volume becomes smaller than a radius-\(\rho\) ball without acceptance, necessarily
\(\displaystyle w_S<h+\delta.\)
This requires polynomially many cuts, because \(\log U\) and \(\log(Q+1)\) are polynomially bounded by the input length.
Now solve the ordinary, explicitly listed covering LP using configurations in \(S\). It is feasible because it contains singleton configurations. By finite LP duality, its optimum is \(w_S<h+\delta\).
Finally, binary-search the threshold. Initially take lower endpoint \(0\) and upper endpoint \((5/4)Q+1\). The upper endpoint cannot be accepted, since acceptance implies \(h\le(5/4)\lambda\le(5/4)Q\). At each midpoint, acceptance updates the lower endpoint; a volume termination updates the upper endpoint and stores its configuration set.
Stop when the interval width is at most \(\delta\). The lower endpoint is always at most \((5/4)\lambda\), so the final upper endpoint \(h\) satisfies
\(\displaystyle h\le\frac54\lambda+\delta.\)
Solving the LP from its stored configuration set yields
\(\displaystyle B<h+\delta\le\frac54\lambda+\frac14.\)
This proves the lemma. The explicitly listed LP has polynomial size. An optimal basic solution can be chosen with at most \(m\) positive coefficients, since it has \(m\) covering constraints. Its rational encoding length is polynomial.
The covering solution might oversupply some classes. We can remove that oversupply while preserving feasible configurations and the total coefficient \(B\).
For a coordinate \(j\), scan the configurations, retaining their \(j\)-coordinates until their cumulative contribution reaches \(q_j\). At a crossing configuration with coefficient \(y_i\) and coordinate \(a^i_j>0\), let \(r\) be the still-required contribution. Replace it by:
Set coordinate \(j\) to zero in all later configurations.
Both replacement coefficients are nonnegative. Both configurations fit in one bin, because deleting items preserves feasibility. The operation makes the \(j\)-contribution exactly \(q_j\), preserves every other coordinate’s total contribution, and preserves the sum of coefficients.
Applying this to all coordinates gives
\(\displaystyle \sum_i y_i a^i=q,\qquad \sum_i y_i=B.\)
There is at most one split per coordinate. Starting with at most \(m\) configurations, we therefore finish with at most \(2m\).
The encoding length remains polynomial. Take an initial common denominator for the LP coefficients and supplies. Each crossing divides a rational number with the current common denominator by an integer at most \(U\); there are at most \(m\) crossings. A common denominator for all resulting coefficients thus gains at most \(m\log U\) bits.
We now prove the distributional rounding step.
Suppose we have \(p\) feasible one-bin configurations satisfying
\(\displaystyle \sum_{i=1}^{p}y_i a^i=q,\qquad \sum_{i=1}^{p}y_i=B.\)
Write \(y_i=k_i+f_i\), where \(k_i=\lfloor y_i\rfloor\) and \(0\le f_i<1\). Let
\(\displaystyle F_0=0,\qquad F_i=\sum_{\ell=1}^{i}f_\ell,\qquad F=F_p.\)
For \(u\in[0,1)\), define
\(\displaystyle \varepsilon_i(u)= \#\{z\in\mathbb Z:u+z\in[F_{i-1},F_i)\}. \)
Because the interval has length \(f_i<1\), this count belongs to \(\{0,1\}\). Under uniform \(u\),
\(\displaystyle \mathbb E[\varepsilon_i(u)]=f_i.\)
Indeed, translating the integration interval \([0,1)\) by all integers partitions the real line, so the integral of this count equals the length of \([F_{i-1},F_i)\).
Moreover,
\(\displaystyle \sum_i\varepsilon_i(u) =\#\{z\in\mathbb Z:u+z\in[0,F)\} \le\lceil F\rceil. \)
Define the integral bundle
\(\displaystyle b(u)=\sum_i\bigl(k_i+\varepsilon_i(u)\bigr)a^i.\)
It has mean
\(\displaystyle \mathbb E[b(u)]=\sum_i y_i a^i=q.\)
Packing each configuration separately gives
\(\displaystyle c_t(b(u)) \le\sum_i k_i+\lceil F\rceil =\lceil B\rceil. \)
This construction is a finite rational distribution. The vector \(\varepsilon(u)\) changes only at fractional parts of the endpoints \(F_i\). These rational breakpoints partition \([0,1)\) into at most \(p+1\) intervals. On each interval choose a rational interior point and give its bundle probability equal to the interval length.
Thus the distribution has at most \(p+1\le2m+1\) supported bundles, all with rational probabilities and polynomial encoding length. Large multiplicities are stored in binary; they are never expanded into individual bins or items.
Run Sections 2–5 separately for each type \(t\). Let \(p_{t,b}\) denote the resulting rational probability distribution. It satisfies
\(\displaystyle \sum_b p_{t,b}=1,\qquad \sum_b b\,p_{t,b}=q. \)
Define
\(\displaystyle x_{t,b}=\mu_t p_{t,b}.\)
Then
\(\displaystyle \sum_bx_{t,b}=\mu_t,\)
and, using \(\sum_t\mu_t=1\),
\(\displaystyle \sum_{t,b}b_jx_{t,b} =\sum_t\mu_tq_j =q_j. \)
Hence this is a mass allocation.
For every supported bundle, the preceding bounds imply
\(\displaystyle c_t(b)\le\lceil B_t\rceil \le\left\lceil\frac54\kappa_t^\infty+\frac14\right\rceil. \)
Finally,
\(\displaystyle \left\lceil\frac54\kappa_t^\infty+\frac14\right\rceil \le\frac54\kappa_t^\infty+\frac54 \le\frac43\kappa_t^\infty+\frac43, \)
where the last inequality follows because the difference of the right-hand expressions is \((\kappa_t^\infty+1)/12>0\).
There are at most \(\tau(2m+1)\) supported type–bundle pairs. All computations, including rational arithmetic and the explicitly listed LPs, take time polynomial in \(m,\tau,L\). Neither the population of size \(D\) nor the benchmark values are computed.
⟨structured verdict parsed — rendered above⟩
The output establishes polynomial-time solvability of the stated mass-allocation problem. The stronger claimed guarantee also follows. I found no false step or gap requiring additional mathematics.
The argument addresses the specified binary encoding and support representation. It neither computes the replication population nor assumes oracle access to the benchmarks.
The identity \(\kappa_t^\infty=\kappa_t(1)\) is correct.
Concatenating a feasible first-replication partition gives exactly \(rD\) bundles totaling \(rDq\), so \(\kappa_t(r)\le\kappa_t(1)\). Because the supremum includes \(r=1\), equality follows. The argument does not assert that every replication has the same optimum.
The defining minima exist: the total item counts are finite integers, there are finitely many bundle partitions, and singleton packing provides finite costs.
The case \(q=0\) is correctly handled by empty bundles.
All configuration coordinates are bounded because the sizes are strictly positive. Singleton configurations are feasible because every size is at most one.
The covering LP is feasible with objective at most \(Q\). Restricting its objective to at most \(Q\) bounds every nonnegative variable, so the compactness and attainment argument is valid. Its stated dual has the correct signs and constraints. Singleton constraints bound every dual coordinate by one.
Packing the first-replication bundles separately supplies a collection of at most \(D\kappa_t(1)\) feasible bin configurations. Dividing their multiplicities by \(D\) gives the required LP coverage. Therefore,
\[
\lambda_t\le\kappa_t^\infty.
\]
No benchmark computation is needed.
The binary-package construction is valid, including the truncated last package. Its multiplicities represent every integer from zero through \(U_j\), and every package fits individually.
The number of packages is polynomial in the binary input length; the algorithm does not enumerate the potentially enormous number of available copies.
The profit scaling is correct:
Consequently, the returned configuration has profit at least \(\frac45M(\pi)\). Exact rational weight comparisons and dynamic programming require polynomial bit complexity when the queried profits have polynomial encoding length. The zero-profit case is handled correctly.
This is the principal nontrivial step, and its logic checks out.
Acceptance. The approximate optimizer returns a configuration with value at least \(\frac45M(\pi)\). If its value is at most one, then \(M(\pi)\le\frac54\). Thus \(\frac45\pi\) is dual feasible, and
\[
h\le q\cdot\pi\le\frac54\lambda.
\]
Collected constraints. Adding singleton configurations makes the restricted dual region compact and contained in the box. Its optimum \(w_S\) therefore exists.
Interior-ball certificate. Under the contrary assumption \(w_S\ge h+\delta\), the proposed convex combination satisfies the stated margins:
The perturbation bounds are also correct:
\[
\|a\|_2\rho\le mU\rho=\frac{\theta}{8},
\qquad
Q\rho\le\frac{\delta}{32}.
\]
These bounds preserve every required inequality throughout the radius-\(\rho\) ball.
Every actual cut comes from an inequality satisfied by that ball. Replacing a violated inequality by the corresponding central halfspace also preserves the ball. This remains valid when \(S\) is defined retrospectively from the complete run.
Accordingly, sufficiently small enclosing volume contradicts \(w_S\ge h+\delta\), establishing \(w_S<h+\delta\).
Rational implementation. The proof explicitly invokes a rational ellipsoid implementation with containment preservation, polynomial encoding length, and polynomial volume-reduction time. These are standard valid properties. The cited [Goemans notes](https://math.mit.edu/~goemans/18433S07/ellipsoid.pdf) support the geometric contraction; finite-precision containment and complexity are treated explicitly in [Grötschel–Lovász–Schrijver, Chapter 3](https://www.mpi-inf.mpg.de/fileadmin/inf/d1/ellipsoid-lovasz.pdf). The required hypotheses hold here: the initial ball contains the box, all cut coefficients have polynomial encoding length, and \(\log(R/\rho)\) is polynomially bounded. Dimension one presents no mathematical obstruction.
Threshold search. Acceptance certifies the lower-endpoint bound. Volume termination supplies the configuration set associated with an upper endpoint. Monotonicity of the approximate oracle’s responses is unnecessary.
There is also no initialization failure involving an unstored configuration set. The initial upper endpoint exceeds every acceptable threshold by at least one. Since the stopping width is \(\delta<1\), some midpoint must terminate without acceptance before the search finishes.
The final restricted LP therefore gives
\[
B<h+\delta\le\frac54\lambda+\frac14.
\]
Deleting items preserves configuration feasibility. At each crossing, the two replacement coefficients are nonnegative and sum to the original coefficient. The operation changes only the selected coordinate’s total contribution.
Thus processing all coordinates produces exact expectation \(q\) while preserving \(B\). Zero supply coordinates and exact cumulative equalities cause no difficulty.
There is at most one split per coordinate, so the support bound of \(2m\) follows from the initial basic-solution bound of \(m\). The denominator-growth argument correctly accounts for at most \(m\) divisions by integers bounded by \(U\).
Each interval has length less than one, so each \(\varepsilon_i(u)\) belongs to \(\{0,1\}\). Its expectation is exactly \(f_i\).
The intervals concatenate to \([0,F)\), giving the stated bound on the total number of selected fractional configurations. Therefore the bundle expectation is \(q\), and separate packing establishes
\[
c_t(b(u))\le\sum_i k_i+\lceil F\rceil=\lceil B\rceil.
\]
The breakpoint construction yields a finite rational distribution. Endpoint behavior affects only a set of measure zero; choosing interior representatives preserves the expectations. The number of intervals is at most \(p+1\), and all multiplicities and probabilities have polynomial binary encoding length.
Multiplication by \(\mu_t\) gives exactly the prescribed type masses. Because every type distribution has expectation \(q\), summing across types gives the required society-wide supplies.
For every supported bundle,
\[
c_t(b)\le
\left\lceil\frac54\kappa_t^\infty+\frac14\right\rceil
\le\frac54\kappa_t^\infty+\frac54
\le\frac43\kappa_t^\infty+\frac43.
\]
The last difference is exactly \(\frac{\kappa_t^\infty+1}{12}>0\). The ceiling inequality and its constants are correct.
The explicit LPs, package dynamic programs, ellipsoid runs, supply adjustment, and distribution construction all have polynomial size and bit complexity. Repeating them for the listed types remains polynomial in \(m,\tau,L\). The final support contains at most \(\tau(2m+1)\) type–bundle pairs.
No mandatory repair is needed. A direct citation for the rational ellipsoid implementation would improve documentation, but the required standard property is already stated and correctly applied.
⟨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.