Answer: Yes. A deterministic algorithm achieves the requested guarantee with \(C=1\), in time polynomial in \(m,\tau,L,1/\epsilon\).
Theorem 3 — class: algorithmic
Given household types \(a\in[\tau]\) with rational masses \(\mu_a\) summing to \(1\), resource categories \(g\in[r]\) with rational per-capita supplies \(q_g\), rational utilities \(u_{ag}\) normalized so \(\max_g u_{ag}=1\), positive rational type weights \(w_a\), and a smoothing parameter \(\omega\in(0,1]\), each household must receive an integral bundle \(k\in\mathbb{Z}_{\ge 0}^r\). Choose masses \(x_{a,k}\ge 0\) satisfying \(\sum_k x_{a,k}=\mu_a\) and \(\sum_{a,k} k_gx_{a,k}\le q_g\) for each category. With \(U_a(k)=\sum_g u_{ag}k_g\) and \(W=\sum_a\mu_aw_a\), maximize \(F_\omega(x)=\exp\!\left(\frac{1}{W}\sum_{a,k}x_{a,k}w_a\ln(U_a(k)+\omega)\right)\). Does there exist an algorithm returning a feasible \(x\) with value at least \(\mathrm{OPT}/O\!\left(e^\epsilon/(\omega\ln(1+1/\omega))\right)\) in time polynomial in \(\tau\), \(r\), the input bit length, \(1/\epsilon\), and \(1/\omega\)?
A society is given by its support: a list of \(\tau\ge1\) household types with positive binary-rational masses \(\mu_a\) summing to \(1\); \(\tau\) is the support size, not the number of possible types.
There are \(m=r\ge1\) resource categories, with binary-rational per-capita supplies \(q_g\ge0\), utilities \(u_{ag}\in[0,1]\) satisfying \(\max_g u_{ag}=1\), positive rational weights \(w_a\), and rational parameters \(\omega\in(0,1]\) and \(\epsilon>0\). Let \(L\) be the total input bit length.
Each household receives an integral bundle \(k\in\mathbb Z_{\ge0}^{m}\), including possibly the empty bundle. A type may be split among different bundles, with masses \(x_{a,k}\ge0\).
Feasibility means \(\sum_k x_{a,k}=\mu_a\) and \(\sum_{a,k}k_gx_{a,k}\le q_g\) for every category \(g\); there is no separate per-household bundle bound.
Define \(U_a(k)=\sum_g u_{ag}k_g\), \(W=\sum_a\mu_aw_a\), and \(F_\omega(x)=\exp\!\left(W^{-1}\sum_{a,k}x_{a,k}w_a\ln(U_a(k)+\omega)\right)\). The smoothing offset consumes no supply.
Let \(\mathrm{OPT}\) be the supremum over all feasible bundle-mass distributions. An algorithm represents its allocation by a finite list of bundles and binary-rational nonzero masses.
Does there exist an absolute constant \(C\ge1\) and an algorithm that, for every such instance, returns a feasible \(x\) with \(F_\omega(x)\ge \mathrm{OPT}\,\omega\ln(1+1/\omega)/(Ce^\epsilon)\) in time polynomial in \(m,\tau,L,1/\epsilon,1/\omega\)?
For finite societies with \(n\) agents and \(M\) explicitly listed indivisible items, the same normalized, weighted, smoothed objective admits an \(O(e^\epsilon/(\omega\ln(1+1/\omega)))\)-approximation in \(O(nM^2/(\epsilon\omega))\) time. [Kell–Sun](https://arxiv.org/html/2109.00081)
No result settling this precise support-encoded mass-allocation approximation question was located in the literature search.
There is a deterministic algorithm satisfying the requested guarantee. In fact, its running time is polynomial in \(m,\tau,L,1/\epsilon\); dependence on \(\omega\) through its binary encoding suffices.
The proof uses a fractional relaxation followed by a distributional rounding procedure. The latter preserves each type’s expected consumption exactly and incurs a bounded loss in logarithmic welfare. A final conversion enforces binary-rational output masses.
Define the normalized type weights
\(
p_a=\mu_aw_a/W.
\)
They are positive rational numbers and satisfy \(\sum_a p_a=1\).
Let \(z_{ag}\) denote the aggregate mass of category \(g\) assigned to type \(a\). Consider the compact rational polytope
\(
\mathcal Z=\{z\ge0:\sum_a z_{ag}\le q_g\text{ for every }g\}.
\)
For \(z\in\mathcal Z\), put
\(
t_a(z)=\mu_a^{-1}\sum_g u_{ag}z_{ag},
\)
and define
\(
J(z)=\sum_a p_a\ln(t_a(z)+\omega),\qquad
V=\max_{z\in\mathcal Z}J(z).
\)
Claim. \(\ln(\mathrm{OPT})\le V\).
Indeed, for any feasible bundle distribution \(x\), set
\(
z_{ag}=\sum_k k_gx_{a,k}.
\)
These quantities are finite and \(z\in\mathcal Z\). Under the probability distribution \(x_{a,k}/\mu_a\), the expected utility of type \(a\) is \(t_a(z)\). Concavity of the logarithm gives
\(
\mu_a^{-1}\sum_k x_{a,k}\ln(U_a(k)+\omega)
\le \ln(t_a(z)+\omega).
\)
Multiplying by \(p_a\) and summing proves
\(
\ln F_\omega(x)\le J(z)\le V.
\)
This also applies to distributions of infinite support. Their expected utilities are finite, and
\(
0\le\ln(1+U_a(k)/\omega)\le U_a(k)/\omega,
\)
so the logarithmic expectations are well defined and finite. Taking the supremum proves the claim.
We first construct, in polynomial time, a rational \(\widehat z\in\mathcal Z\) satisfying
\(
J(\widehat z)\ge V-\epsilon/2.
\)
Write
\(
Q=\sum_gq_g,\qquad \mu_{\min}=\min_a\mu_a.
\)
If \(Q=0\), assigning every household the empty bundle is optimal, so assume \(Q>0\). Every feasible fractional utility satisfies
\(
0\le t_a(z)\le Q/\mu_{\min}.
\)
Set
\(
S=\omega+Q/\mu_{\min},\qquad
\delta=\min\{1,\epsilon/4\}.
\)
Construct the rational geometric grid
\(
b_i=\omega(1+\delta)^i,\qquad 0\le i\le N,
\)
where \(N\) is the smallest index with \(b_N\ge S\). Its size satisfies
\(
N=O\!\left(1+\delta^{-1}\ln(S/\omega)\right).
\)
Because \(S/\omega\) has polynomial binary encoding length, \(N\), and the encoding lengths of all grid points, are polynomial in \(m,\tau,L,1/\epsilon\).
For each grid point, compute a rational number \(c_i\) with
\(
\ln b_i-\delta\le c_i\le\ln b_i.
\)
Define
\(
\ell_i(s)=c_i+(s-b_i)/b_i,\qquad
H(s)=\min_{0\le i\le N}\ell_i(s).
\)
For every \(s\in[\omega,S]\),
\(
\ln s-\delta\le H(s)\le\ln s+\delta.
\)
For the lower bound, the tangent inequality gives
\(
\ln b_i+(s-b_i)/b_i\ge\ln s,
\)
and replacing \(\ln b_i\) by \(c_i\) decreases its value by at most \(\delta\).
For the upper bound, choose \(b_i\le s\le(1+\delta)b_i\). With \(r=s/b_i\),
\(
\ell_i(s)-\ln s
\le r-1-\ln r
\le r-1
\le\delta.
\)
Now solve the rational linear program maximizing \(\sum_a p_ah_a\), subject to
\(
z\in\mathcal Z,\qquad
h_a\le\ell_i(\omega+t_a(z))
\quad\text{for every }a,i,
\)
and the additional lower bounds \(h_a\ge c_0-1\).
These lower bounds do not exclude any maximizing choice: since \(\delta\le1\),
\(
H(\omega+t_a(z))
\ge\ln\omega-\delta
\ge c_0-1.
\)
The resulting feasible polytope is nonempty and bounded. Every coefficient is rational with polynomial encoding length. We apply the standard theorem that rational linear programs can be optimized exactly in polynomial time, returning a rational optimum of polynomial encoding length. See the discussion of rational LP complexity in [Adler and Beling](https://adler.ieor.berkeley.edu/ilans_pubs/lp_algebraic_stoc_1992.pdf).
Because every \(p_a\) is positive, the LP optimizes
\(
\widetilde J(z)=\sum_a p_aH(\omega+t_a(z)).
\)
The pointwise estimates imply
\(
J(z)-\delta\le\widetilde J(z)\le J(z)+\delta.
\)
Consequently, its rational optimizer \(\widehat z\) satisfies
\(
J(\widehat z)\ge V-2\delta\ge V-\epsilon/2.
\)
For completeness, computing the \(c_i\) needs no exact logarithm oracle. For a positive rational \(b\), write \(b=2^kr\) with \(1\le r<2\). With \(v=(r-1)/(r+1)\), we have
\(
\ln r=2\sum_{j=0}^{\infty}\frac{v^{2j+1}}{2j+1},
\qquad 0\le v<1/3.
\)
The tail after \(n\) terms is at most
\(
\frac{2v^{2n+1}}{(2n+1)(1-v^2)}.
\)
The same series with \(v=1/3\) computes \(\ln2\). Combining certified rational intervals for \(\ln r\) and \(\ln2\) gives a lower approximation to \(\ln b=k\ln2+\ln r\) within \(\delta\), using polynomially many rational operations of polynomial bit length.
Lemma. Given rational vectors \(y\in\mathbb Q_{\ge0}^m\) and \(u\in\mathbb Q^m\cap[0,1]^m\), one can compute a rational probability distribution on at most \(2(m+1)\) integral bundles \(K\) such that
\(
\mathbb E[K]=y
\)
and
\(
\mathbb E[\ln(u\cdot K+\omega)]
\ge\ln(u\cdot y+\omega)-A_\omega,
\)
where
\(
s_\omega=\ln(1+1/\omega),\qquad
A_\omega=\ln\!\left(\frac1{\omega s_\omega}\right)-1+\omega s_\omega.
\)
The computation and output encoding lengths are polynomial in the input encoding length and \(m\).
Write
\(
y=h+f,\qquad
h=\lfloor y\rfloor,\qquad f\in[0,1]^m.
\)
Consider
\(
P=\{v\in[0,1]^m:u\cdot v=u\cdot f\}.
\)
Every vertex of \(P\) has at most one fractional coordinate. To prove this, if two coordinates \(i,j\) are strictly between their bounds, there is a nonzero direction supported on them with \(u\cdot d=0\). Small moves in both directions remain feasible, contradicting extremality. A single fractional coordinate with zero utility coefficient likewise permits a feasible move in both directions.
We next give a constructive decomposition
\(
f=\sum_{j=1}^{s}\lambda_jv^{(j)},\qquad
s\le m+1,
\)
where the \(v^{(j)}\) are vertices of \(P\), the coefficients are nonnegative rationals, and \(\sum_j\lambda_j=1\).
Start with a residual point \(x=f\). Find a vertex \(v\) while preserving every coordinate already at a bound:
Each move fixes another coordinate, so at most \(m\) moves are needed.
If \(x=v\), terminate. Otherwise choose the largest \(\lambda\) such that
\(
x'=(x-\lambda v)/(1-\lambda)\in[0,1]^m.
\)
Explicitly, \(\lambda\) is the minimum of
\(
x_i/v_i\quad(v_i>0),\qquad
(1-x_i)/(1-v_i)\quad(v_i<1).
\)
Because \(v\) shares the coordinates of \(x\) already at bounds and \(x\ne v\), this minimum satisfies \(0<\lambda<1\). The residual \(x'\) lies in \(P\), preserves all previously fixed coordinates, and fixes at least one additional coordinate. Record the term \(\lambda v\) and continue with \(x'\), scaling subsequent coefficients by \(1-\lambda\). There are at most \(m\) peeling steps followed by one final vertex.
Here is also an explicit bit-complexity justification. A vertex with one fractional coordinate \(i\) has that coordinate equal to
\(
\frac{u\cdot f-\sum_{g\ne i}u_gv_g}{u_i},
\)
with every other coordinate integral. Thus every vertex has a common denominator of polynomial bit length, uniformly over all steps.
If the current residual has common denominator \(D\), and the chosen vertex has common denominator \(E\), either active-ratio formula above gives a new residual with common denominator at most \(DE\), before reduction. For example, when \(\lambda=x_i/v_i\), writing \(x_j=X_j/D\) and \(v_j=V_j/E\) gives
\(
x'_j=\frac{X_jV_i-X_iV_j}{DV_i-X_iE}.
\)
The upper-bound case has the same denominator bound. Consequently, denominator bit lengths grow additively over at most \(m\) steps. The decomposition coefficients also have polynomial bit length.
At an integral vertex \(v\), use the single bundle \(h+v\).
At a vertex whose only fractional coordinate is \(i\), write \(v_i=p\). Round that coordinate to zero with probability \(1-p\), and to one with probability \(p\). This preserves the mean vector \(h+v\).
The resulting utilities are two endpoints \(U_0,U_0+d\), where
\(
0<d=u_i\le1,\qquad
U_0+pd=u\cdot y.
\)
Therefore the loss from this rounding is
\(
\ln(U_0+pd+\omega)
-(1-p)\ln(U_0+\omega)
-p\ln(U_0+d+\omega).
\)
Setting \(b=U_0+\omega\) and \(t=d/b\), this becomes
\(
G_t(p)=\ln(1+pt)-p\ln(1+t).
\)
Since \(b\ge\omega\) and \(d\le1\), we have \(0<t\le1/\omega\). Moreover,
\(
\frac{\partial G_t(p)}{\partial t}
=\frac{pt(1-p)}{(1+pt)(1+t)}
\ge0.
\)
Hence the loss is at most \(\max_{0\le p\le1}G_{1/\omega}(p)\).
For any \(t>0\), differentiation in \(p\) gives the maximizer
\(
p^*=\frac1{\ln(1+t)}-\frac1t.
\)
It lies strictly between zero and one because
\(
t/(1+t)<\ln(1+t)<t.
\)
Substitution yields
\(
\max_{0\le p\le1}G_t(p)
=\ln\!\left(\frac{t}{\ln(1+t)}\right)-1+\frac{\ln(1+t)}t.
\)
At \(t=1/\omega\), this is exactly \(A_\omega\).
Every vertex has the same unrounded utility \(u\cdot y\). Mixing the rounded distributions according to the decomposition coefficients thus preserves \(\mathbb E[K]=y\) and proves the stated logarithmic bound. At most two bundles arise per vertex, completing the lemma.
For each type \(a\), set
\(
y_{ag}=\widehat z_{ag}/\mu_a.
\)
Apply the lemma with utility vector \(u_a\), and multiply its probability masses by \(\mu_a\). Denote the resulting allocation by \(x^\circ\).
Its type masses are exactly \(\mu_a\). Its consumption satisfies
\(
\sum_{a,k}k_gx^\circ_{a,k}
=\sum_a\mu_a y_{ag}
=\sum_a\widehat z_{ag}
\le q_g.
\)
Thus it is feasible, with at most \(2\tau(m+1)\) listed bundles.
Its normalized logarithmic welfare satisfies
\(
\ln F_\omega(x^\circ)
\ge J(\widehat z)-\sum_a p_aA_\omega
=J(\widehat z)-A_\omega.
\)
By Section 2,
\(
\ln F_\omega(x^\circ)\ge V-\epsilon/2-A_\omega.
\)
This construction is deterministic: the distribution itself is the output allocation; no random sampling is performed.
All intermediate masses are rational with polynomial encoding length. We now also ensure terminating binary masses whenever “binary-rational” has that stricter, dyadic meaning.
Every constructed bundle satisfies
\(
k_g\le y_{ag}+1.
\)
Consequently,
\(
U_a(k)\le\sum_gk_g
\le Q/\mu_{\min}+m=:B_*.
\)
Choose a positive integer \(R\), of polynomial size, satisfying
\(
R\ge\ln(1+B_*/\omega).
\)
Such an \(R\) can be obtained directly from the bit length of the numerator of the rational number \(1+B_*/\omega\).
Let
\(
N_0=2\tau(m+1),\qquad w_{\max}=\max_aw_a.
\)
Choose an integer precision \(B\) such that
\(
2^{-B}N_0\frac{w_{\max}}W R\le\epsilon/2.
\)
If the input type masses are dyadic, also choose \(B\) so that every \(2^B\mu_a\) is an integer. These requirements give a \(B\) polynomial in the input encoding length and \(\log^+(1/\epsilon)\).
For every nonempty listed bundle, replace its mass \(\rho\) by
\(
\rho'=2^{-B}\lfloor2^B\rho\rfloor.
\)
For each type, assign all remaining mass to the empty bundle. Remove zero entries and merge duplicate bundles.
Type masses remain exact, and consumption can only decrease. All nonempty masses are dyadic. The empty mass is \(\mu_a\) minus a dyadic number, so it is dyadic when the input masses are dyadic; under the ordinary binary-encoded rational interpretation, it also meets the required representation.
Moving mass \(d\) from a bundle \(k\) of type \(a\) to the empty bundle decreases normalized logarithmic welfare by
\(
\frac{w_a}W d\ln\!\left(1+\frac{U_a(k)}\omega\right)
\le\frac{w_{\max}}W dR.
\)
Each listed nonempty mass loses less than \(2^{-B}\). Therefore the final feasible allocation \(x\) satisfies
\(
\ln F_\omega(x)
\ge\ln F_\omega(x^\circ)-\epsilon/2
\ge V-\epsilon-A_\omega.
\)
It has at most \(\tau(2m+3)\) entries and polynomial total encoding length.
Since \(\ln(\mathrm{OPT})\le V\),
\(
F_\omega(x)\ge\mathrm{OPT}\,e^{-\epsilon-A_\omega}.
\)
The explicit loss formula gives
\(
e^{-A_\omega}
=\omega\ln(1+1/\omega)\,
e^{\,1-\omega\ln(1+1/\omega)}.
\)
The inequality \(\ln(1+t)\le t\), applied at \(t=1/\omega\), shows
\(
\omega\ln(1+1/\omega)\le1.
\)
Thus
\(
e^{-A_\omega}\ge\omega\ln(1+1/\omega),
\)
and finally
\(
\boxed{
F_\omega(x)\ge
\mathrm{OPT}\,
\frac{\omega\ln(1+1/\omega)}{e^\epsilon}
}.
\)
The rational LP has polynomial size; all rounding decompositions, bundle coordinates, and masses have polynomial encoding length; and the final dyadic conversion is polynomial time. No step enumerates individual households or resource units. The requested algorithm therefore exists with the absolute constant \(C=1\).
⟨structured verdict parsed — rendered above⟩
The argument establishes the requested approximation with \(C=1\), under the natural interpretation that utilities are supplied as binary-encoded rational numbers. I found no false inequality, failed feasibility argument, or substantive gap. Two minor clarifications are needed: explicitly state that input interpretation, and justify that the points produced by the vertex-finding procedure are indeed vertices.
The normalization \(p_a=\mu_aw_a/W\) is valid: \(W>0\), every \(p_a>0\), and \(\sum_a p_a=1\).
The polytope \(\mathcal Z\) is nonempty and compact. In particular, every coordinate satisfies \(0\le z_{ag}\le q_g\). Since \(\omega>0\), the objective \(J\) is continuous throughout this polytope, so its maximum \(V\) exists.
For any feasible bundle distribution, the aggregate quantities \(z_{ag}\) are finite by the supply constraints. The stated expression for each type’s expected utility follows from the definition of \(z\).
Jensen’s inequality applies to these expectations. The infinite-support case is also covered correctly: the displayed bound on \(\ln(1+U_a(k)/\omega)\) establishes integrability, including when some utilities or supplies vanish.
Thus the conclusion \(\ln(\mathrm{OPT})\le V\) is justified. Taking the supremum introduces no attainment assumption.
The case \(Q=0\) is handled correctly: only empty bundles can receive positive mass, and their objective value is \(\omega\).
For \(Q>0\), the bound \(t_a(z)\le Q/\mu_{\min}\) is valid. The grid covers the full interval needed for evaluating the objective.
Both estimates for \(H\) are correct:
The endpoint \(s=b_N\) causes no problem.
The additional lower bounds on \(h_a\) are compatible with every feasible \(z\). The resulting LP is nonempty and bounded, and positivity of the objective coefficients ensures that its optimum corresponds to maximizing \(\widetilde J\).
The invoked theorem is applicable: a nonempty bounded LP with binary-encoded rational coefficients can be optimized exactly in polynomial bit complexity, with a rational optimizer of polynomial encoding length. The cited paper’s discussion confirms polynomial-time solvability for rational LPs. [Adler–Beling](https://adler.ieor.berkeley.edu/ilans_pubs/lp_algebraic_stoc_1992.pdf)
The error accounting is correct:
\[
J(\widehat z)\ge V-2\delta\ge V-\epsilon/2.
\]
Here the last inequality holds both when \(\epsilon\le4\) and when \(\epsilon\ge4\).
The logarithm series and its tail bound are correct. Certified intervals also permit a lower approximation when the exponent \(k\) is negative; the write-up’s interval formulation accommodates that sign. The required precision and rational arithmetic have polynomial bit complexity.
Minor issue 1 — utility encoding. The task does not explicitly specify the representation of \(u_{ag}\). The proof uses rational utilities both in the LP and in its rounding lemma. This is the natural interpretation of the finite-bit input model, but the write-up should state it explicitly.
Minimum clarification: Say that the utilities are binary-encoded rationals and that their encoding lengths are included in \(L\).
The perturbation argument correctly proves that every vertex of \(P\) has at most one fractional coordinate, and that a fractional coordinate at a vertex cannot have zero utility coefficient.
The constructive moves preserve the utility equality and previously fixed coordinates. Each move fixes at least one additional coordinate, so the stated bound on the number of moves is valid.
Minor issue 2 — certification of the constructed vertices. The write-up proves a necessary condition for being a vertex, then treats the points produced by the procedure as vertices without stating why the condition reached by that procedure is sufficient. This is a routine extremality check, rather than a substantive mathematical gap.
Minimum clarification: Explicitly justify that a feasible point with all coordinates integral, or with exactly one fractional coordinate having positive utility coefficient, is a vertex of \(P\).
The subsequent peeling procedure is otherwise correct:
The bound of at most \(m+1\) terms is therefore valid.
The bit-complexity argument is also sound. The vertex-coordinate formula gives polynomial-size denominators uniformly over the possible vertices. The residual formula has denominator magnitude at most \(DE\), so denominator bit lengths grow additively. The decomposition coefficients consequently retain polynomial encoding length.
At every decomposed vertex, the unrounded utility equals \(u\cdot y\). Rounding the sole fractional coordinate preserves the complete expected bundle vector.
The two-point loss is correctly expressed as
\[
G_t(p)=\ln(1+pt)-p\ln(1+t).
\]
The derivative with respect to \(t\) is correct and nonnegative. The hypotheses \(U_0\ge0\), \(\omega>0\), and \(d\le1\) justify \(t\le1/\omega\).
The maximizer
\[
p^*=\frac1{\ln(1+t)}-\frac1t
\]
is correct and lies strictly between zero and one by the inequalities stated in the output. Substitution gives exactly the displayed formula for \(A_\omega\).
Integral vertices incur zero loss. Mixing the distributions therefore establishes the lemma’s expectation and welfare guarantees, with at most \(2(m+1)\) bundles. Zero utility coefficients and entirely zero utility vectors cause no failure.
Multiplying each type’s rounding probabilities by \(\mu_a\) preserves its total mass exactly.
The expected-consumption identities are correct and imply feasibility against every supply constraint. The smoothing offset is never counted as resource consumption.
The welfare inequality follows with precisely one copy of \(A_\omega\), because \(\sum_a p_a=1\). The bound on the number of listed bundles is correct.
The output distribution is deterministic; no sampling claim is needed.
The constructed coordinate bound \(k_g\le y_{ag}+1\) is valid. Summing it yields the stated utility bound \(B_*\).
A polynomial-size integer \(R\) with the required logarithmic upper bound can indeed be obtained from the numerator’s bit length. The precision requirement on \(B\) is compatible with polynomial encoding length, including very small type masses or highly unequal weights.
Rounding nonempty masses downward and assigning the remainder to the empty bundle:
The welfare loss per moved mass is exactly the displayed logarithmic difference. Summing over at most \(N_0\) entries gives loss at most \(\epsilon/2\).
The final support-size bound is also correct. Zero entries can be removed without affecting feasibility.
Combining the two approximation errors yields
\[
F_\omega(x)\ge\mathrm{OPT}\,e^{-\epsilon-A_\omega}.
\]
The expression for \(e^{-A_\omega}\) is correct. Since \(\omega\ln(1+1/\omega)\le1\), the final factor is at least the requested factor with \(C=1\).
The running-time claim is supported by the grid size, rational LP complexity, decomposition bounds, and output conversion. Large supplies require large bundle coordinates only in value; their binary encoding lengths remain polynomial.
The established result is a polynomial-time approximation guarantee for the support-encoded problem. Under the supplied classification’s explicit example for approximation guarantees, its continuous status is “other.”
⟨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.