Answer: Yes. A randomized polynomial-time algorithm outputs at most two binary-rational coalitions and achieves an expected \(O(\log(\tau+1))\)-approximation.
Theorem 4.7 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateThere exists a randomized O(log𝑛)-approximation algorithm for maximizing social welfare in ASHGs with nonnegative total value.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite type set \(T\), rational masses \(\mu \in \mathbb{Q}_{\ge 0}^{\tau}\) summing to \(1\), and a symmetric rational valuation matrix \(W=(w_{ts})\) satisfying \(V_\mu:=\sum_{t,s}\mu_t\mu_s w_{ts}\ge 0\), output in randomized time polynomial in \(\tau\) and encoding length \(L\) a finite mass partition \(\Pi=(x^\ell)_{\ell=1}^{r}\) with \(x^\ell\in\mathbb{R}_{\ge 0}^{\tau}\) and \(\sum_{\ell}x^\ell_t\le\mu_t\), such that \(\operatorname{OPT}_\mu\le O(\log(\tau+1))\,\mathbb{E}[\operatorname{SW}_\mu(\Pi)]\), where \(\operatorname{SW}_\mu(\Pi)=\sum_{\ell}\sum_{t,s}w_{ts}x^\ell_t x^\ell_s\).
A society is given by its support: a list \(T\) of \(\tau\ge1\) 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. Input also includes a symmetric matrix \(W\in\mathbb Q^{\tau\times\tau}\) with unrestricted signs and \(V_\mu:=\sum_{t,s}\mu_t\mu_sw_{ts}\ge0\). Let \(L\) be the total input bit length; there is no separate candidate parameter \(m\).
A feasible mass partition is any finite list \(\Pi=(x^\ell)_{\ell=1}^r\) of nonzero vectors \(x^\ell\in\mathbb R_{\ge0}^{\tau}\) satisfying \(\sum_\ell x_t^\ell\le\mu_t\). Types may be split among coalitions; residual mass consists of isolated individuals and contributes zero welfare. The empty list is allowed, and coalition sizes and their number are unrestricted.
Define \(\operatorname{SW}_\mu(\Pi):=\sum_\ell\sum_{t,s}w_{ts}x_t^\ell x_s^\ell\) and \(\operatorname{OPT}_\mu:=\sup_{\Pi}\operatorname{SW}_\mu(\Pi)\) over these feasible real partitions. Diagonal entries describe interactions between distinct individuals of the same type and are unrestricted; individual self-interactions have zero mass. Algorithmic outputs must list binary-rational coalition masses.
Does there exist a randomized algorithm with expected running time polynomial in \(\tau\) and \(L\) that, on every such input, outputs a feasible partition satisfying \(\operatorname{OPT}_\mu\le C\log(\tau+1)\,\mathbb E[\operatorname{SW}_\mu(\Pi)]\) for some universal constant \(C\ge1\)?
For finite symmetric additively separable hedonic games with nonnegative total valuation, a randomized polynomial-time algorithm achieves an expected \(O(\log n)\)-approximation, where \(n\) is the number of agents. [Bullinger, Chatziafratis, and Shahkar](https://arxiv.org/html/2503.06017v1)
No result settling this precise divisible-mass approximation question was located in the literature search.
Yes. There is a randomized algorithm with running time polynomial in \(\tau\) and \(L\) that outputs at most two coalitions and satisfies
\(\operatorname{OPT}_\mu\le 1024\ln(\tau+1)\,\mathbb E[\operatorname{SW}_\mu(\Pi)]\).
The proof below handles unrestricted diagonal entries and produces binary-rational masses.
Write \(n:=\tau\), \(P:=\operatorname{diag}(\mu_1,\ldots,\mu_n)\), and \(A:=PWP\). Thus \(A\) is symmetric and rational, and
\(\mathbf 1^\mathsf T A\mathbf 1=V_\mu\ge0\).
Define
\(M_A:=\max_{z\in[-1,1]^n}z^\mathsf TAz\).
This maximum exists by compactness and continuity, and \(M_A\ge0\), since \(z=0\) is feasible.
Lemma 1. \(\operatorname{OPT}_\mu\le M_A\).
Proof. Fix any feasible finite partition \(\Pi=(x^\ell)_{\ell=1}^r\), and put \(y^\ell:=P^{-1}x^\ell\). Positivity of the masses makes \(P^{-1}\) well-defined. Feasibility gives
\(y^\ell\ge0\) and \(\sum_\ell y_i^\ell\le1\) for every \(i\).
Let \(\varepsilon_1,\ldots,\varepsilon_r\) be independent uniform signs, and set \(z:=\sum_\ell\varepsilon_\ell y^\ell\). For every outcome,
\(|z_i|\le\sum_\ell y_i^\ell\le1\).
Independence and zero means give
\(\mathbb E[z^\mathsf TAz] =\sum_{\ell,k}\mathbb E[\varepsilon_\ell\varepsilon_k](y^\ell)^\mathsf TAy^k =\sum_\ell(x^\ell)^\mathsf TWx^\ell =\operatorname{SW}_\mu(\Pi).\)
Since \(z^\mathsf TAz\le M_A\) for every outcome, every feasible partition has welfare at most \(M_A\). Taking the supremum proves the lemma. \(\square\)
Conversely, every \(z\in[-1,1]^n\) defines a feasible partition using all the mass:
\(x^+:=\tfrac12P(\mathbf1+z),\qquad x^-:=\tfrac12P(\mathbf1-z).\)
Both vectors are nonnegative and sum to \(\mu\); a zero vector is omitted. Direct expansion gives
\(\operatorname{SW}_\mu(x^+,x^-) =\tfrac12\mathbf1^\mathsf TA\mathbf1+\tfrac12z^\mathsf TAz =\tfrac12V_\mu+\tfrac12z^\mathsf TAz.\)
Consequently, it suffices to approximate \(M_A\) logarithmically. Notice that these identities include all diagonal terms exactly.
Consider
\(S:=\max\{\operatorname{tr}(AX):X\succeq0,\ X_{ii}\le1\text{ for all }i\}.\)
Here \(X\succeq0\) means that \(X\) is positive semidefinite. Every feasible box vector gives a feasible matrix \(X=zz^\mathsf T\), so
\(S\ge M_A\ge\operatorname{OPT}_\mu\).
The feasible region is compact: positive semidefiniteness implies
\(|X_{ij}|\le\sqrt{X_{ii}X_{jj}}\le1\).
It is strictly feasible, since \(X=I/2\) satisfies \(X\succ0\) and every diagonal inequality strictly.
Its dual is
\(\min\{\sum_i\lambda_i:\lambda_i\ge0,\ D-A\succeq0,\ D=\operatorname{diag}(\lambda)\}.\)
The dual is feasible by taking \(D=cI\) with sufficiently large \(c\). Slater duality therefore gives an attained dual optimum \(D\) satisfying
\(\sum_i\lambda_i=S\).
This is the standard strict-feasibility duality theorem; see [Lovász, Section 3.1](https://sites.math.washington.edu/~thomas/teaching/m514_web/Lovasz_semidef.pdf).
For the rounding argument, suppose that \(S>0\) and we have a binary-rational matrix \(B\in\mathbb R^{n\times n}\) satisfying
\(\sum_j B_{ij}^2\le1\quad\text{for every }i,\qquad p:=\operatorname{tr}(ABB^\mathsf T)\ge S-\epsilon,\qquad 0<\epsilon\le S/8.\)
Section 4 constructs such a matrix in polynomial time.
Set \(k:=\lceil\log_2(24n)\rceil\), and let \(R\) be the smallest power of two satisfying \(R^2\ge2k\). Then
\(R^2<8k\).
Draw independent uniform signs \(\xi_1,\ldots,\xi_n\), and put \(g:=B\xi\). Define the event
\(\mathcal E:=\{\max_i|g_i|\le R\}\).
The algorithm selects \(z\) as follows:
Thus \(z\in[-1,1]^n\) in every outcome. All calculations and comparisons are exact rational operations.
For each row of \(B\),
\(\mathbb E[e^{tg_i}] =\prod_j\cosh(tB_{ij}) \le\exp\!\left(\tfrac12t^2\sum_jB_{ij}^2\right) \le e^{t^2/2}.\)
The inequality uses \(\cosh u\le e^{u^2/2}\). Applying the exponential Markov inequality with \(t=R\), and also to \(-g_i\), gives
\(\Pr(|g_i|>R)\le2e^{-R^2/2}\).
Hence, by the union bound and \(k\ge\ln(24n)\),
\(\Pr(\mathcal E^c)\le2ne^{-R^2/2}\le2ne^{-k}\le1/12.\)
Let \(D\) be an optimal dual matrix from Section 2, and define
\(H:=B^\mathsf TDB,\qquad K:=B^\mathsf T(D-A)B.\)
Both \(H\) and \(K\) are positive semidefinite. For every outcome,
\(g^\mathsf TAg=\xi^\mathsf TH\xi-\xi^\mathsf TK\xi.\)
Moreover, with \(X:=BB^\mathsf T\),
\(\operatorname{tr}K =\sum_i\lambda_iX_{ii}-p \le\sum_i\lambda_i-p =S-p \le\epsilon.\)
Here we used \(\lambda_i\ge0\) and \(X_{ii}\le1\). Also,
\(\operatorname{tr}H=p+\operatorname{tr}K\ge S-\epsilon\).
Put \(h:=\xi^\mathsf TH\xi\). Since \(H\succeq0\), we have \(h\ge0\), and
\(\mathbb E[h]=\operatorname{tr}H\).
Expanding the square and using independence of the signs yields
\(\mathbb E[h^2] =(\operatorname{tr}H)^2+4\sum_{i<j}H_{ij}^2 \le(\operatorname{tr}H)^2+2\operatorname{tr}(H^2) \le3(\operatorname{tr}H)^2.\)
The last inequality follows because the eigenvalues of \(H\) are nonnegative, so
\(\operatorname{tr}(H^2)\le(\operatorname{tr}H)^2\).
Cauchy–Schwarz now gives
\(\mathbb E[h\,\mathbf1_{\mathcal E^c}] \le\sqrt{\mathbb E[h^2]\Pr(\mathcal E^c)} \le\tfrac12\operatorname{tr}H.\)
Therefore
\(\mathbb E[h\,\mathbf1_{\mathcal E}]\ge\tfrac12\operatorname{tr}H\).
For a real number \(a\), write \(a_+:=\max\{a,0\}\). Because \(\xi^\mathsf TK\xi\ge0\),
\(\mathbb E[(g^\mathsf TAg)_+\mathbf1_{\mathcal E}] \ge\mathbb E[h\mathbf1_{\mathcal E}] -\mathbb E[\xi^\mathsf TK\xi] \ge\tfrac12\operatorname{tr}H-\operatorname{tr}K.\)
The bounds above imply
\(\mathbb E[(g^\mathsf TAg)_+\mathbf1_{\mathcal E}] \ge\tfrac12(S-\epsilon)-\epsilon \ge\tfrac14S.\)
By the definition of \(z\), we have proved
\(\mathbb E[z^\mathsf TAz]\ge S/(4R^2).\)
This argument is valid for arbitrary signs on the diagonal of \(A\).
Two issues remain: choosing a sufficiently small tolerance without knowing \(S\), and constructing the rational factor \(B\).
First test exactly whether \(A\preceq0\), using rational symmetric elimination. This takes polynomial time: a negative pivot, or a zero diagonal with a nonzero row, certifies failure of positive semidefiniteness when testing \(-A\); positive pivots permit Schur-complement elimination.
If \(A\preceq0\), then \(M_A=0\). Lemma 1 and feasibility of the empty partition imply \(\operatorname{OPT}_\mu=0\), so the algorithm outputs the empty partition.
Suppose henceforth that \(A\not\preceq0\). Choose a positive integer \(d\) clearing all denominators of \(A\), and write \(J:=dA\). Define
\(M:=n\max_{i,j}|J_{ij}|,\qquad \beta:=1/(dM^{n-1}).\)
Since \(J\ne0\), we have \(M\ge1\). Every eigenvalue of \(J\) has absolute value at most \(M\), by the maximum absolute row-sum bound.
Let \(r\) be the rank of \(J\). The product of its nonzero eigenvalues, up to sign, is the coefficient of the lowest-degree nonzero term of its characteristic polynomial. It is therefore a nonzero integer and has absolute value at least one. Consequently, every nonzero eigenvalue \(\theta\) satisfies
\(|\theta|\ge M^{-(r-1)}\ge M^{-(n-1)}.\)
Since \(A\not\preceq0\), it has a positive eigenvalue at least \(\beta\). A corresponding Euclidean unit eigenvector belongs to \([-1,1]^n\); hence
\(S\ge M_A\ge\beta\).
The integers \(d\) and \(J\) have polynomial bit length: for example, \(d\) can be the product of the entry denominators. Thus \(\beta\) also has polynomial bit length. We choose
\(\epsilon:=\beta/8\).
This ensures \(0<\epsilon\le S/8\), with \(\log(1/\epsilon)\) polynomial in the input length.
We use the standard ellipsoid optimization theorem: a rational linear objective over a compact convex set with known inner and outer balls and a polynomial-time separation oracle can be optimized to additive tolerance in time polynomial in the input length and the logarithm of the inverse tolerance. The SDP version is described in [Lovász, Section 3.2](https://sites.math.washington.edu/~thomas/teaching/m514_web/Lovasz_semidef.pdf).
For our feasible region, the necessary geometric bounds are explicit. In the space of symmetric matrices with Frobenius norm, the ball of radius \(1/4\) around \(I/2\) is feasible: every matrix in this ball has smallest eigenvalue at least \(1/4\) and diagonal entries at most \(3/4\). Conversely, every feasible matrix satisfies
\(\|X\|_F\le\operatorname{tr}X\le n\).
There is an exact rational separation oracle. A violated diagonal inequality supplies a coordinate cut. Otherwise, rational symmetric elimination either verifies positive semidefiniteness or returns a rational vector \(v\) with \(v^\mathsf TXv<0\); the valid inequality \(v^\mathsf TYv\ge0\) then separates \(X\) from the feasible region. The elimination and its certificates have polynomial bit length.
We can therefore compute a rational matrix \(Y\) satisfying
\(Y\succeq0,\qquad Y_{ii}\le1,\qquad \operatorname{tr}(AY)\ge S-\epsilon/2,\)
in polynomial time.
Let \(Q:=\max\{1,\sum_{i,j}|A_{ij}|\}\), so \(Q\ge\|A\|_F\). Choose a positive dyadic number \(\eta\) satisfying
\(\eta\le1/2,\qquad \eta\le\epsilon/(4Qn(n+1)).\)
It requires only polynomially many bits.
Rational symmetric elimination gives a factorization
\(Y=U\operatorname{diag}(a_1,\ldots,a_n)U^\mathsf T\),
where \(U\) and the nonnegative \(a_i\) are rational. Zero pivots are handled by omitting zero rows and columns and padding the resulting factor with zero columns. The rational entries have polynomial bit length, as they are ratios of minors of \(Y\).
Define the real factor
\(F:=U\operatorname{diag}(\sqrt{a_1},\ldots,\sqrt{a_n})\).
Then \(FF^\mathsf T=Y\), and every row of \(F\) has Euclidean norm at most one.
Approximate each entry of \(F\) by a dyadic number with error at most \(\eta/n\), producing a dyadic matrix \(C\) with
\(\|C-F\|_F\le\eta\).
This is polynomial-time scalar arithmetic: square roots of nonnegative rationals can be enclosed to the required precision by bisection, followed by multiplication and dyadic rounding.
Set \(B:=(1-\eta)C\). Each row satisfies
\(\|B_{i,*}\|_2\le(1-\eta)(1+\eta)\le1.\)
Furthermore,
\(\|B-F\|_F \le(1-\eta)\|C-F\|_F+\eta\|F\|_F \le\eta(n+1).\)
Since both \(B\) and \(F\) have Frobenius norm at most \(\sqrt n\),
\(\|BB^\mathsf T-Y\|_F \le(\|B\|_F+\|F\|_F)\|B-F\|_F \le2n(n+1)\eta.\)
It follows that
\(|\operatorname{tr}(ABB^\mathsf T)-\operatorname{tr}(AY)| \le\|A\|_F\|BB^\mathsf T-Y\|_F \le\epsilon/2.\)
Thus \(B\) satisfies all the requirements of Section 2, including
\(\operatorname{tr}(ABB^\mathsf T)\ge S-\epsilon\).
Its entries are dyadic and have polynomial bit length.
The complete algorithm is:
Every output is feasible. Because \(V_\mu\ge0\), its expected welfare satisfies
\(\mathbb E[\operatorname{SW}_\mu(\Pi)] =\tfrac12V_\mu+\tfrac12\mathbb E[z^\mathsf TAz] \ge S/(8R^2) \ge\operatorname{OPT}_\mu/(8R^2).\)
To bound the constant, observe that
\(k\le\log_2(48n)\le6+\log_2(n+1)\le7\log_2(n+1).\)
Consequently,
\(R^2<8k\le(56/\ln2)\ln(n+1)<128\ln(n+1).\)
Combining these inequalities proves
\(\operatorname{OPT}_\mu \le1024\ln(n+1)\,\mathbb E[\operatorname{SW}_\mu(\Pi)].\)
All deterministic computations have polynomial bit complexity. Rounding uses exactly \(n\) fair bits and polynomial-time rational arithmetic, so even the worst-case running time is polynomial. Because \(B\) is dyadic and \(R\) is a power of two, the output coordinates are dyadic fractions of the input masses and are binary-rational; in particular, dyadic input masses give dyadic output masses.
The continuous quadratic step is consistent with broader logarithmic SDP bounds for indefinite homogeneous quadratic optimization, such as [He, Luo, Nie, and Zhang, Theorem 4.2](https://arxiv.org/pdf/math/0701070). The proof above establishes the required box case directly, including the finite-precision construction. No expansion into a potentially enormous finite population is needed.
⟨structured verdict parsed — rendered above⟩
The prover resolves the assigned approximation question. The argument is correct, including its treatment of unrestricted diagonal entries, arbitrary finite real partitions, and rational output precision. I found no major or minor mathematical issues.
The established result is a polynomial-time approximation guarantee. It does not establish polynomial-time exact optimization of the continuous problem.
Correct. Positivity of every input mass makes \(P^{-1}\) well-defined. For every feasible partition, its normalized vectors satisfy \(y^\ell\ge0\) and \(\sum_\ell y_i^\ell\le1\).
Consequently, the random vector \(z=\sum_\ell\varepsilon_\ell y^\ell\) belongs to \([-1,1]^n\) for every sign outcome. Independence gives \(\mathbb E[\varepsilon_\ell\varepsilon_k]=0\) for distinct indices and \(1\) for equal indices. The displayed expectation therefore equals the partition welfare, with all diagonal terms retained.
This establishes \(\operatorname{SW}_\mu(\Pi)\le M_A\) for every feasible finite partition. Taking the supremum is legitimate and requires neither attainment of \(\operatorname{OPT}_\mu\) nor a bound on the number of coalitions. The empty partition also satisfies the bound.
Correct converse construction. For every box vector, the two displayed mass vectors are nonnegative and sum coordinatewise to \(\mu\). Omitting a zero vector satisfies the requirement that listed coalitions be nonzero. The expansion gives exactly
\(\operatorname{SW}_\mu(x^+,x^-)=V_\mu/2+z^\mathsf TAz/2\).
The hypothesis \(V_\mu\ge0\) is used appropriately when turning the quadratic guarantee into a welfare guarantee.
Correct. Every matrix \(zz^\mathsf T\) arising from a box vector is feasible, establishing \(S\ge M_A\). Positive semidefiniteness implies nonnegative diagonal entries and the stated bound on every off-diagonal entry. The feasible region is closed and bounded, hence compact.
The dual is correctly stated. The nonnegative multipliers correspond to the diagonal upper bounds, and its matrix constraint is \(D-A\succeq0\).
The invoked strict-feasibility theorem says that primal strict feasibility, dual feasibility, and a finite primal optimum imply equality of optimal values and attainment of the dual optimum. All these hypotheses are verified here:
This application agrees with [Lovász, Section 3.1, Theorem 3.4](https://sites.math.washington.edu/~thomas/teaching/m514_web/Lovasz_semidef.pdf).
The optimal dual matrix is used only for analysis. The algorithm does not need to compute or represent it rationally.
Correct threshold and rejection probability. The definition of \(R\) ensures \(R^2\ge2k\). Minimality among powers of two gives \(R^2<8k\). The row norm condition on \(B\) gives the displayed subgaussian moment bound.
Exponential Markov and the union bound yield
\(\Pr(\mathcal E^c)\le2ne^{-k}\le1/12\).
The comparison \(k\ge\ln(24n)\) is valid because \(24n>1\) and \(\log_2(24n)\ge\ln(24n)\).
Correct control of the indefinite objective. Both \(H\) and \(K\) are positive semidefinite. Their traces satisfy
\(0\le\operatorname{tr}K\le S-p\le\epsilon\)
and
\(\operatorname{tr}H=p+\operatorname{tr}K\ge S-\epsilon\).
The inequality involving \(S-p\) uses precisely the nonnegative dual multipliers and the row feasibility of \(B\).
Correct second-moment calculation. For independent signs, distinct off-diagonal sign products have zero cross expectation. Thus the stated identity
\(\mathbb E[h^2]=(\operatorname{tr}H)^2+4\sum_{i<j}H_{ij}^2\)
is correct. Positive semidefiniteness then gives
\(\mathbb E[h^2]\le3(\operatorname{tr}H)^2\).
Cauchy–Schwarz and the rejection bound give
\(\mathbb E[h\mathbf1_{\mathcal E^c}]\le\operatorname{tr}H/2\).
This does not assume independence between \(h\) and \(\mathcal E\).
Correct positive-part estimate. Since \(\xi^\mathsf TK\xi\ge0\), the positive-part bound and subsequent subtraction of its unconditional expectation are valid. The resulting lower bound is
\(S/2-3\epsilon/2\ge5S/16\ge S/4\).
Thus the weaker constant claimed in the proof is justified.
The rounding rule consequently gives
\(\mathbb E[z^\mathsf TAz]\ge S/(4R^2)\).
No diagonal sign restriction enters this argument.
Correct zero case. Rational symmetric elimination can test whether \(-A\) is positive semidefinite. Its pivot and zero-row conditions are valid.
If \(A\preceq0\), then \(M_A=0\). Lemma 1 gives \(\operatorname{OPT}_\mu\le0\), while the empty partition gives the reverse inequality. Outputting the empty partition therefore satisfies the requested guarantee.
Correct positive-optimum lower bound. After clearing denominators, \(J\) is a nonzero symmetric integer matrix. Its eigenvalues have absolute value at most \(M\).
Symmetry ensures that the number of nonzero eigenvalues, counted with multiplicity, equals its rank. Their product, up to sign, is a nonzero integer characteristic-polynomial coefficient. For any nonzero eigenvalue, bounding the remaining factors by \(M\) gives the claimed lower bound.
Because \(A\not\preceq0\), a positive eigenvalue exists. Its Euclidean unit eigenvector belongs to the box, proving \(S\ge M_A\ge\beta>0\).
The denominator product, integer matrix entries, and power \(M^{n-1}\) all have polynomial bit length. Hence \(\epsilon=\beta/8\) has polynomial encoding length and satisfies the required relative accuracy.
The argument includes the case \(n=1\), where the exponent \(n-1\) is zero.
Correct geometric bounds. A Frobenius perturbation of size at most \(1/4\) around \(I/2\) has operator norm at most \(1/4\). This proves both positive definiteness and the asserted diagonal upper bounds. The outer bound follows from \(\|X\|_F\le\operatorname{tr}X\le n\) for positive semidefinite matrices.
The inner ball has a known rational center; translating coordinates meets the centered-ball formulation of the optimization theorem.
Correct separation oracle. A violated diagonal constraint supplies a rational separating inequality. Otherwise, symmetric elimination either confirms positive semidefiniteness or supplies a rational negative quadratic-form certificate. Its corresponding inequality is valid throughout the feasible region. Rational elimination and its certificates have polynomial bit complexity.
The cited optimization theorem supplies a rational feasible point with additive objective accuracy under these geometric and oracle hypotheses. Exact feasibility of the resulting \(Y\), rather than merely approximate feasibility, is supported by [Lovász, Section 3.2, Theorem 3.7 and its SDP application](https://sites.math.washington.edu/~thomas/teaching/m514_web/Lovasz_semidef.pdf).
Thus the asserted properties of \(Y\) are justified.
Correct. Rational symmetric elimination of a positive semidefinite matrix gives the stated rational factorization. Zero pivots have zero residual rows and columns, so omitting them and padding with zero columns preserves the factorization.
The real factor \(F\) has row norms at most one because \(FF^\mathsf T=Y\). Approximating each of its \(n^2\) entries within \(\eta/n\) gives \(\|C-F\|_F\le\eta\).
The scaling satisfies
\(\|B_{i,*}\|_2\le(1-\eta)(1+\eta)\le1\).
Therefore \(BB^\mathsf T\) is exactly feasible.
The displayed Frobenius estimates are valid, including their deliberately loose dependence on \(n\). Combining them with the choice of \(\eta\) bounds the objective loss by \(\epsilon/2\). Together with the accuracy of \(Y\), this establishes \(p\ge S-\epsilon\).
Polynomial bit length of the elimination factors also makes the required scalar square-root approximation polynomial-time, including when multiplication by an entry of \(U\) requires additional precision.
Correct. The two-coalition identity, nonnegative total valuation, and rounding bound yield
\(\mathbb E[\operatorname{SW}_\mu(\Pi)]\ge S/(8R^2)\ge\operatorname{OPT}_\mu/(8R^2)\).
The inequalities bounding \(k\) hold for every \(n\ge1\). In particular, \(\log_2(n+1)\ge1\) justifies absorbing the additive constant. The bound
\(R^2<128\ln(n+1)\)
therefore establishes the stated constant \(1024\).
All output vectors are feasible in every outcome. Since \(B\) is dyadic and \(R\) is a power of two, the output coordinates have polynomial-length binary-rational representations after multiplication by the input masses. Exactly \(n\) fair bits suffice, and the subsequent comparisons and arithmetic are exact rational operations.
The proof establishes polynomial worst-case running time, which is stronger than the requested polynomial expected running time.
The final reference to He, Luo, Nie, and Zhang is contextual; no step of the proof depends on applying that theorem.
No repair or additional mathematical clarification is needed. The prover has established the requested approximation result. This should be distinguished from a claim that the exact continuous optimum is polynomial-time computable.
⟨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.