Answer: Every finite-factor polynomial-time multiplicative approximation is impossible unless \(\mathrm{P}=\mathrm{NP}\), already for every fixed \(k\ge3\), equal dyadic masses, and nonzero weights in \(\{-1,+1\}\).
Theorem 3.4 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateThe offline variant of the problem MaxWC is inap- proximable for any k ≥3, unless P = NP.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given finite types \(T\), rational masses \(\mu_i \ge 0\) with \(\sum_i \mu_i = 1\), an integer \(k \ge 3\), and symmetric rational interaction weights \(\omega_{ij}\) with \(\omega_{ii}=0\), choose \(x_{ir} \ge 0\) satisfying \(\sum_{r=1}^{k} x_{ir} = \mu_i\) to maximize \(\operatorname{TW}(x)=\sum_{r=1}^{k}\sum_{i<j}\omega_{ij}x_{ir}x_{jr}\), or decide whether the optimum is positive.
A society is given by its support: the list of \(\tau\) types with positive binary-rational masses \(\mu_i\), where \(\sum_i\mu_i=1\); \(\tau\) is the support size, not the number of possible types.
Interactions are symmetric rational weights \(\omega_{ij}\), with \(\omega_{ii}=0\); zero denotes an absent edge, and each nonzero weight has absolute value at least \(1\). Allow both positive and negative weights. Let \(m\) count nonzero unordered interaction pairs and \(L\) be the total input bit length.
Given an integer \(k\ge3\), an offline allocation consists of real masses \(x_{ir}\ge0\) satisfying \(\sum_{r=1}^{k}x_{ir}=\mu_i\). Types may split among coalitions; empty coalition slots are allowed, so there are at most \(k\) coalitions, with no size bound.
Maximize \(\operatorname{TW}(x)=\sum_{r=1}^{k}\sum_{i<j}\omega_{ij}x_{ir}x_{jr}\), and write \(\operatorname{OPT}\) for its maximum. A multiplicative guarantee is required whenever \(\operatorname{OPT}>0\); on other inputs the algorithm must still return a feasible allocation.
Does this mass-allocation problem admit a polynomial-time multiplicative approximation with any finite factor \(\rho(m,\tau,k,L)\ge1\), or is every such approximation impossible unless \(\mathrm{P}=\mathrm{NP}\)? State running times in \(m,\tau,k,L\).
For indivisible vertices, maximizing total internal edge weight with at most \(k\) coalitions is inapproximable within any finite multiplicative factor for every fixed \(k\ge3\), unless \(\mathrm{P}=\mathrm{NP}\); the [full version](https://www.moscardelli.it/protetta/J39.pdf) repeats this result.
No result settling exactly the mass-allocation approximation question was located.
1. Result and computational model. Every polynomial-time multiplicative approximation with any finite factor \(\rho(m,\tau,k,L)\) is impossible unless \(\mathrm{P}=\mathrm{NP}\). This holds for every fixed \(k\ge3\), even with equal dyadic masses and all nonzero weights in \(\{-1,+1\}\).
Here polynomial time means the usual deterministic bit model, with allocations output as binary-encoded rational numbers. The proof below is independent of the cited indivisible-vertex reduction.
2. Proven lemma: splitting does not improve the optimum. Call an allocation *pure* if each type places its entire mass in one coalition.
Every feasible allocation can be converted to a pure allocation without decreasing welfare. To prove this, fix a type \(i\) and hold all other allocations fixed. Define
\(\displaystyle a_{ir}=\sum_{j\ne i}\omega_{ij}x_{jr}.\)
Because \(\omega_{ii}=0\), the objective has the form
\(\displaystyle \operatorname{TW}(x)=C+\sum_{r=1}^{k}a_{ir}x_{ir},\)
where \(C\) is independent of type \(i\)’s allocation. Choose \(r^\ast\) maximizing \(a_{ir}\). Nonnegativity and the mass constraint imply
\(\displaystyle \sum_{r=1}^{k}a_{ir}x_{ir}\le a_{ir^\ast}\sum_{r=1}^{k}x_{ir}=\mu_i a_{ir^\ast}.\)
Thus replacing type \(i\)’s allocation by \(x_{ir^\ast}=\mu_i\) and \(x_{ir}=0\) for \(r\ne r^\ast\) does not decrease welfare. Process every type once. Previously processed types remain pure, and each step is nondecreasing, proving the claim.
The feasible region is a nonempty compact product of simplices, and the objective is continuous, so a maximum exists. Applying the preceding procedure to a maximizer proves
\(\displaystyle \operatorname{OPT}=\max_{c:\{1,\ldots,\tau\}\to\{1,\ldots,k\}}\sum_{i<j}\omega_{ij}\mu_i\mu_j\,\mathbf{1}_{\{c(i)=c(j)\}}.\)
This is an equality for arbitrary signed weights.
With adjacency lists, purification takes \(O(k(m+\tau))\) rational arithmetic operations: computing the coefficients for type \(i\) takes \(O(k\deg(i))\) operations, and finding their maximum takes \(O(k)\). If the supplied allocation has total encoding length \(B\), the bit running time is \(O(k(m+\tau)\operatorname{poly}(L+B))\). Intermediate numbers have polynomial encoding length because each coefficient is a sum of products of input weights and either supplied coordinates or input masses.
3. Proven reduction: positive optimum encodes coloring. Fix \(k\ge3\). Deciding whether a finite simple graph is colorable with at most \(k\) colors is \(\mathrm{NP}\)-complete. The base case is the classical \(\mathrm{NP}\)-completeness of graph \(3\)-colorability. [Garey, Johnson, and Stockmeyer](https://doi.org/10.1016/0304-3975%2876%2990059-1)
For completeness, hardness for larger fixed \(k\) follows by adjoining a clique of size \(k-3\) and connecting each new vertex to every original vertex. The clique consumes \(k-3\) distinct colors, leaving at most three for the original graph; conversely, any three-coloring extends.
Let \(G=(V,E)\) be an instance of fixed-\(k\) colorability, with \(n=|V|\) and \(e=|E|\). Construct a society as follows.
Every listed type has positive dyadic mass, and the masses sum to one. Thus \(\tau=N\) is the actual support size. Also \(m=e+1\), and every nonzero weight has absolute value one.
For a pure allocation \(c\), define the number of monochromatic original edges by
\(\displaystyle h(c)=\bigl|\{\{u,v\}\in E:c(u)=c(v)\}\bigr|.\)
Its welfare is exactly
\(\displaystyle \operatorname{TW}(c)=\frac{1}{N^2}\left(\mathbf{1}_{\{c(a)=c(b)\}}-h(c)\right).\)
If \(G\) is \(k\)-colorable, assign its vertices according to a proper coloring and place \(a,b\) together in any coalition. This gives welfare \(1/N^2\). No pure allocation exceeds that value, so the lemma gives \(\operatorname{OPT}=1/N^2>0\).
If \(G\) is not \(k\)-colorable, every pure allocation has \(h(c)\ge1\), hence welfare at most zero. The lemma then implies that every fractional allocation also has welfare at most zero.
Consequently,
\(\displaystyle G\text{ is }k\text{-colorable}\quad\Longleftrightarrow\quad\operatorname{OPT}>0.\)
4. Why every finite multiplicative factor fails. Suppose an algorithm \(A\) returns a feasible allocation on every input and, whenever \(\operatorname{OPT}>0\), guarantees
\(\displaystyle \operatorname{TW}(A(I))\ge\frac{\operatorname{OPT}(I)}{\rho(m,\tau,k,L)},\)
where \(\rho\) is finite.
Run \(A\) on the constructed society and purify its output using Section 2. Accept precisely when the resulting assignment of the original graph vertices is a proper \(k\)-coloring.
If \(G\) is colorable, the approximation guarantee gives strictly positive welfare. Purification preserves positivity. The displayed welfare formula then forces \(h(c)=0\), so the procedure accepts.
If \(G\) is not colorable, no assignment can be a proper coloring, so the procedure rejects. This argument uses only feasibility on instances with nonpositive optimum.
The procedure never computes \(\rho\), and imposes no bound on its growth. Only its finiteness matters.
5. Running times and conclusion. The reduction satisfies \(\tau=N<2(n+2)\) and \(m=e+1\). With a sparse interaction-list encoding, its length is \(L=O((n+e)\log(n+2)+\log(k+1))\), and construction takes polynomial bit time. A dense encoding also has polynomial length.
If \(A\) runs in time \(T(m,\tau,k,L)\) and outputs \(B\) bits, the resulting coloring algorithm runs in
\(\displaystyle T(m,\tau,k,L)+O\!\left(k(m+\tau)\operatorname{poly}(L+B)\right).\)
A polynomial-time algorithm has polynomial output length. Thus polynomial \(T\), even allowing polynomial dependence on the numerical value of \(k\), would yield a polynomial-time algorithm for fixed-\(k\) colorability and imply \(\mathrm{P}=\mathrm{NP}\).
For comparison, the proven lemma gives an exact exhaustive algorithm: with \(q=\min\{k,\tau\}\), enumerate all \(q^\tau\) pure assignments. Its bit running time is \(O(q^\tau(m+\tau)\operatorname{poly}(L))\).
Therefore the stated mass-allocation approximation question is resolved: splitting supplies no improvement in optimal welfare, and no finite-factor polynomial-time multiplicative approximation exists unless \(\mathrm{P}=\mathrm{NP}\).
⟨structured verdict parsed — rendered above⟩
The proof is correct and resolves the task in the explicitly stated deterministic bit model. No major or minor mathematical gaps were found. The impossibility holds for every fixed \(k\ge3\), even with equal dyadic masses and interaction weights restricted to \(\{-1,+1\}\).
The prover explicitly assumes that an algorithm outputs feasible allocations as binary-encoded rational numbers. This is a standard interpretation of polynomial time for the task’s rational input.
The approximation hypothesis is used only when \(\operatorname{OPT}>0\). On all other inputs, the argument requires only feasibility, exactly as specified in the task.
The factor \(\rho(m,\tau,k,L)\) can have arbitrary growth and need not be computed. Its finiteness and positivity suffice to make \(\operatorname{OPT}/\rho\) strictly positive on the constructed yes-instances.
The coefficient formula
\[
a_{ir}=\sum_{j\ne i}\omega_{ij}x_{jr}
\]
is correct. Symmetry ensures that every interaction involving type \(i\) has the stated coefficient, and the absence of diagonal interactions makes the objective linear in that type’s coordinates when all other coordinates are fixed.
The inequality
\[
\sum_{r=1}^{k}a_{ir}x_{ir}\le
\mu_i\max_{1\le r\le k}a_{ir}
\]
follows directly from nonnegativity and the mass constraint. It remains valid when all coefficients are negative.
Moving all of type \(i\)’s mass to a maximizing coalition preserves feasibility and does not decrease welfare. Processing subsequent types changes their coordinates only; previously processed types remain pure. The argument therefore establishes purification after one pass without requiring convergence or repeated optimization.
The existence of a maximizer is also justified: the feasible region is a nonempty compact product of simplices, and the objective is continuous. Purifying a maximizer proves the claimed equality between fractional and pure optima for arbitrary signed weights.
The cited theorem is applicable: deciding whether a finite simple graph admits a proper coloring using at most three colors is NP-complete. The cited paper explicitly treats graph three-colorability. [Garey, Johnson, and Stockmeyer](https://www.sciencedirect.com/science/article/pii/0304397576900591)
For larger fixed \(k\), the stated clique construction is correct. The added clique requires \(k-3\) distinct colors, and its adjacency to every original vertex prevents those colors from appearing on the original graph. Conversely, a proper three-coloring extends using distinct additional colors for the clique. For fixed \(k\), the construction has polynomial size.
Every input restriction is satisfied:
Each internal original edge contributes \(-1/N^2\), and the pair \(\{a,b\}\) contributes \(1/N^2\) precisely when its endpoints share a coalition. Thus the displayed formula is exact:
\[
\operatorname{TW}(c)=
\frac{\mathbf{1}_{\{c(a)=c(b)\}}-h(c)}{N^2}.
\]
For a colorable graph, the exhibited allocation has welfare \(1/N^2\), and the formula bounds every pure allocation by that value. Purification transfers this upper bound to fractional allocations.
For a noncolorable graph, every pure assignment has \(h(c)\ge1\), hence welfare at most zero. Purification implies the same upper bound for every fractional allocation. The prover correctly refrains from asserting that the optimum must equal zero.
Therefore the equivalence between graph colorability and strictly positive optimum is established.
On a colorable instance, the approximation guarantee forces strictly positive output welfare. Purification preserves that positivity.
In the pure welfare formula, the indicator is at most one and \(h(c)\) is a nonnegative integer. Strictly positive welfare consequently forces \(h(c)=0\). The extracted assignment is therefore a proper coloring.
On a noncolorable instance, no assignment can pass the proper-coloring check. No approximation guarantee on nonpositive-optimum instances is used.
This is a valid polynomial-time decision reduction. It requires neither computing the factor nor numerically distinguishing an arbitrarily small positive objective value: the final acceptance test is a discrete coloring check.
The purification operation count follows from summing the degrees:
\[
O\bigl(k(m+\tau)\bigr).
\]
Its bit-complexity bound is justified because coefficients are sums of products of supplied rational coordinates or input masses with input weights. Their encoding lengths remain polynomial in \(L+B\), allowing exact arithmetic and comparisons.
The padding bound \(N<2(n+2)\) and the stated sparse encoding bound are valid, including the case of an empty original graph. Dense encoding also remains polynomial.
For fixed \(k\), polynomial running time and polynomial output length for the approximation algorithm make purification and the final coloring check polynomial. This yields the claimed implication \(\mathrm{P}=\mathrm{NP}\).
The exhaustive algorithm is correctly bounded using \(q=\min\{k,\tau\}\): a pure allocation uses at most \(\tau\) occupied slots, and coalition labels can be relabeled without affecting welfare. The stated enumeration and bit-complexity bounds are consistent.
None. The proof supplies the necessary hypotheses, handles signed weights and nonpositive optima correctly, and establishes the requested hardness independently of the indivisible-vertex result. No repair is required.
⟨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.