Answer: A feasible binary rational vector satisfying the \(1-1/e-\epsilon\) approximation guarantee can be found in time polynomial in \(m,\tau,L,1/\epsilon\).
Theorem 1 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateFor an information propagation network formu- lated by IC model, the information coverage maximization problem is NP-hard.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given rational type masses \(\mu_t\) summing to \(1\), contact intensities \(q_{tu}\), activation probabilities \(p_{tu}\), and a seed budget \(\kappa\), choose seed masses \(x_t\) with \(0\leq x_t\leq\mu_t\) and \(\sum_t x_t=\kappa\) to maximize \(C(x)=\sum_u v_u^\infty\). Define \(z^0=a^0=v^0=x\), and for each round set \(z_u^{r+1}=(\mu_u-a_u^r)(1-\exp[-\sum_t q_{tu}p_{tu}z_t^r])\), \(a_u^{r+1}=a_u^r+z_u^{r+1}\), and \(v_u^{r+1}=v_u^r+(\mu_u-v_u^r)(1-\exp[-\sum_t q_{tu}z_t^r])\). For rational inputs and \(\epsilon>0\), can one find a feasible seed-mass vector with coverage at least \((1-1/e-\epsilon)\max_y C(y)\) in time polynomial in the number of types, input bit length, and \(1/\epsilon\)?
A society is given by its support: a list of \(\tau\geq1\) types with positive binary rational masses \(\mu_t\), summing to \(1\); \(\tau\) is the support size, not the number of possible types.
Inputs also specify binary rational contact intensities \(q_{tu}\geq0\), activation probabilities \(p_{tu}\in[0,1]\), a budget \(0<\kappa\leq1\), and \(\epsilon>0\). Let \(m\) count ordered type pairs with positive contact intensity and \(L\) be the total input bit length; unspecified pairs have zero intensity, and within-type contacts are allowed.
A feasible seed vector satisfies \(0\leq x_t\leq\mu_t\) and \(\sum_t x_t=\kappa\). Set \(z^0=a^0=v^0=x\), where \(z\) is newly active mass, \(a\) is cumulative active mass, and \(v\) is cumulative covered mass, counting active and informed individuals once.
For \(r\geq0\), define \(z_u^{r+1}=(\mu_u-a_u^r)(1-\exp(-\sum_t q_{tu}p_{tu}z_t^r))\) and \(a_u^{r+1}=a_u^r+z_u^{r+1}\).
Define \(v_u^{r+1}=v_u^r+(\mu_u-v_u^r)(1-\exp(-\sum_t q_{tu}z_t^r))\) and \(C(x)=\sum_u\lim_{r\to\infty}v_u^r\). Thus contact can inform individuals even when its activation probability is zero.
Is finding a feasible binary rational vector \(x\) with \(C(x)\geq(1-1/e-\epsilon)\sup_{y\text{ feasible}}C(y)\) possible in time polynomial in \(m,\tau,L,1/\epsilon\), or is achieving this approximation guarantee NP-hard?
Discrete information coverage maximization under the independent cascade model is NP-hard; its coverage objective is monotone and submodular, yielding a greedy \(1-1/e\) guarantee with exact value access, although exact coverage evaluation is #P-hard. [Source](https://www.ijcai.org/Proceedings/15/Papers/298.pdf)
No complexity classification for exactly the mass recurrence above was identified in the literature search.
The requested approximation can be found in polynomial time. More precisely, in the standard binary encoding of rational numbers, there is a deterministic algorithm that returns a feasible rational vector \(x\) satisfying
\(C(x)\geq (1-1/e-\epsilon)\sup_{y\text{ feasible}}C(y)\)
in time polynomial in \(m,\tau,L,1/\epsilon\).
The proof requires addressing two issues: the limiting dynamics can be discontinuous when a type has zero seed mass, and direct iteration need not converge in polynomial time. We avoid the first issue by reserving a small positive seed mass for every type, and the second by evaluating the positive-seed fixed point through convex optimization.
Write \(n=\tau\), and define matrices with destination types indexing rows:
\(B_{ut}=q_{tu}p_{tu},\qquad Q_{ut}=q_{tu}.\)
All vector inequalities below are componentwise. For \(0\leq x\leq\mu\), define
\(F_x(a)_u=\mu_u-(\mu_u-x_u)\exp(-(Ba)_u)\)
and
\(H_x(a)_u=\mu_u-(\mu_u-x_u)\exp(-(Qa)_u).\)
Telescoping the susceptible-mass recurrence gives, with \(a^{-1}=0\),
\(a^r=F_x(a^{r-1}),\qquad v^r=H_x(a^{r-1})\qquad(r\geq0).\)
Indeed, for \(r\geq1\),
\(\mu_u-a_u^r=(\mu_u-x_u)\exp\bigl(-\sum_{k=0}^{r-1}(Bz^k)_u\bigr)=(\mu_u-x_u)\exp(-(Ba^{r-1})_u),\)
and the corresponding calculation for \(v^r\) uses \(Q\).
The map \(F_x\) is increasing in both \(x\) and \(a\). Starting from \(a^{-1}=0\), its iterates increase and remain bounded by \(\mu\). Consequently, their limit \(a(x)\) exists, and
\(a(x)=F_x(a(x)),\qquad C(x)=\sum_u H_x(a(x))_u.\)
This also proves that \(a(x)\), the limiting covered vector, and \(C(x)\) are increasing in \(x\). Moreover,
\(\sum_u x_u\leq C(x)\leq1.\)
We will use these statements on the entire box \(0\leq x\leq\mu\), including vectors whose total seed mass is less than the budget.
Scaling lemma. For \(0\leq\lambda\leq1\),
\(C(\lambda x)\geq\lambda C(x).\)
To prove it, fix a coordinate and put \(s=(Ba)_u\). The scalar function
\(h(t)=\mu_u-(\mu_u-tx_u)e^{-ts}\)
satisfies \(h(0)=0\) and
\(h''(t)=-e^{-ts}\bigl(2x_us+(\mu_u-tx_u)s^2\bigr)\leq0\qquad(0\leq t\leq1).\)
Thus
\(F_{\lambda x}(\lambda a)\geq\lambda F_x(a).\)
Induction over the iterates starting from zero gives
\(a^r(\lambda x)\geq\lambda a^r(x),\)
and hence \(a(\lambda x)\geq\lambda a(x)\). The same scalar calculation with \(Q\), followed by monotonicity of \(H_{\lambda x}\), proves the coverage inequality.
This proof does not assume continuity at vectors with zero coordinates.
Throughout this section, suppose every coordinate of \(x\) is positive.
Each coordinate of \(F_x(a)\) is concave in \(a\), and \(F_x(0)=x>0\). Therefore, for every \(\rho>1\) and \(a\geq0\),
\(F_x(\rho a)\leq\rho F_x(a)-(\rho-1)x<\rho F_x(a).\)
Suppose \(a,c\) were distinct fixed points. Both are positive. After interchanging them if necessary, let
\(\rho=\max_u a_u/c_u>1.\)
Then \(a\leq\rho c\), so
\(a=F_x(a)\leq F_x(\rho c)<\rho F_x(c)=\rho c.\)
This contradicts equality in a coordinate attaining the maximum ratio. Thus \(a(x)\) is the unique nonnegative fixed point.
For this subsection, all quantities are evaluated at \(x\). Set
\(E=\operatorname{diag}(e^{-Ba}),\qquad S=\operatorname{diag}(\mu-a),\qquad J=SB.\)
The fixed-point equation implies
\((Ja)_u=(\mu_u-x_u)e^{-(Ba)_u}(Ba)_u\leq(\mu_u-x_u)(1-e^{-(Ba)_u})=a_u-x_u,\)
where the inequality uses \(se^{-s}\leq1-e^{-s}\) for \(s\geq0\).
Since \(a>0\) and \(x>0\), this establishes a strict contraction for \(J\) in the weighted maximum norm with weights \(a_u\). In particular, its spectral radius is less than one, and
\(R=(I-J)^{-1}=\sum_{k\geq0}J^k\)
exists and is nonnegative.
The implicit-function theorem now gives
\(Da(x)=RE.\)
Here \(Da(x)\) denotes the Jacobian of the limiting active vector. The formula also applies at an upper boundary \(x_u=\mu_u\): the implicit equation extends smoothly to a neighborhood, and \(I-J\) remains invertible there.
Let \(w(x)=H_x(a(x))\) be the limiting covered vector, and set
\(T=\operatorname{diag}(e^{-Qa}),\qquad W=\operatorname{diag}(\mu-w).\)
Differentiating gives
\(Dw(x)=T+WQRE,\qquad \nabla C(x)=(Dw(x))^{\mathsf T}\mathbf1.\)
All entries are nonnegative.
Furthermore, if \(0<x\leq x'\leq\mu\), monotonicity of \(a\) and \(w\) shows that \(S,E,T,W\) decrease componentwise. Therefore \(J\) decreases, and its nonnegative Neumann series shows that \(R\) decreases as well. The derivative formulas consequently give
\(\nabla C(x')\leq\nabla C(x).\)
Thus, on every box bounded away from zero seeds, \(C\) is differentiable, monotone, and has diminishing coordinate derivatives.
A useful consequence is the following bound for any positive vector \(b\leq\mu\):
\(b^{\mathsf T}\nabla C(b)\leq C(b).\)
Indeed, for \(0<s<1\), diminishing derivatives give
\(C(b)-C(sb)=\int_s^1 b^{\mathsf T}\nabla C(tb)\,dt\geq(1-s)b^{\mathsf T}\nabla C(b).\)
Use \(C(sb)\geq0\) and let \(s\) decrease to zero. Again, continuity at zero is unnecessary.
We next prove the bit-complexity statement needed by the optimization algorithm:
Oracle lemma. Given a rational vector \(0<x\leq\mu\) and a rational accuracy \(\rho>0\), one can compute a rational vector \(\widetilde g\) satisfying
\(\|\widetilde g-\nabla C(x)\|_\infty\leq\rho\)
in time polynomial in the input bit length, \(n\), the encoding length of \(x\), and \(\log(1/\rho)\).
Put \(d=\min_u x_u>0\). Consider
\(K_x=\{a\in[0,\mu]:a_u+(\mu_u-x_u)e^{-(Ba)_u}\leq\mu_u\text{ for every }u\}.\)
Each defining nonlinear function is convex, so \(K_x\) is convex.
Every \(a\in K_x\) satisfies \(a\leq F_x(a)\). Iterating \(F_x\) from this point produces an increasing bounded sequence whose limit is a fixed point. Uniqueness therefore implies \(a\leq a(x)\). Conversely, \(a(x)\in K_x\). Hence \(a(x)\) is the unique maximizer of the linear objective
\(\max_{a\in K_x}\mathbf1^{\mathsf T}a.\)
The body has explicit inner and outer bounds. Let \(c=(d/2)\mathbf1\). The Euclidean ball of radius \(d/4\) about \(c\) lies in \(K_x\): every point in this ball has coordinates between \(d/4\) and \(3d/4\), whereas
\(F_x(a)\geq x\geq d\mathbf1.\)
Also \(K_x\subseteq[0,1]^n\), giving an outer radius \(n\).
We use the standard ellipsoid-method consequence that a bounded convex body with a specified interior ball and a polynomial-time weak separation oracle admits approximate linear optimization in time polynomial in the dimension, encoding lengths, logarithms of the radius bounds, and logarithm of the requested accuracy. This is the weak-separation/weak-optimization theorem of [Grötschel, Lovász, and Schrijver](https://www.zib.de/userpage/groetschel/pubnew/paper/groetschellovaszschrijver1981a.pdf).
Here are the remaining oracle checks explicitly. Write
\(\phi_u(a)=a_u+(\mu_u-x_u)e^{-(Ba)_u}-\mu_u.\)
Outside the rational box \([0,\mu]\), an exact box separator is available. Inside the box, both \(\phi_u\) and its gradient can be approximated to any prescribed accuracy using rational arithmetic.
To see that these approximations suffice for weak separation, suppose all constraint violations at a queried point \(y\) are at most \(2\theta\). Since \(\phi_u(c)\leq-d/2\), convexity implies that
\(y'=(1-t)y+tc,\qquad t=\frac{4\theta}{d+4\theta},\)
belongs to \(K_x\). Its distance from \(y\) is at most \(4\theta\sqrt n/d\).
Otherwise, a constraint with a certified positive violation supplies a separating hyperplane through its convex supporting-plane inequality. For example, if \(\phi_u(y)>3\theta/4\), an approximation to its gradient with coordinate error at most \(\theta/(8n)\) remains a valid separator, because \(y,z\in[0,\mu]\) imply \(\|z-y\|_1\leq n\). Choosing \(\theta\) proportional to the desired weak-separation tolerance times \(d/n\) therefore implements the required oracle.
Exponential evaluations also have polynomial bit complexity. For an absolute error \(2^{-b}\) and rational \(s\geq0\), return zero if \(s\geq b\). Otherwise \(s<b\), and a Taylor expansion with \(O(b)\) terms gives the requested accuracy using arithmetic of polynomial bit length. All exponential arguments here are nonnegative; the large values of contact intensities therefore cause no difficulty.
Finally, approximate linear optimization determines the whole vector \(a(x)\), rather than merely its sum. Suppose its output \(\widehat a\) is within Euclidean distance \(\delta\) of \(K_x\), and
\(\mathbf1^{\mathsf T}\widehat a\geq\mathbf1^{\mathsf T}a(x)-\delta.\)
Choose \(a'\in K_x\) within distance \(\delta\). Since \(a'\leq a(x)\),
\(\|a(x)-a'\|_\infty\leq\mathbf1^{\mathsf T}(a(x)-a')\leq(1+\sqrt n)\delta.\)
Consequently,
\(\|\widehat a-a(x)\|_\infty\leq(2+\sqrt n)\delta.\)
Clipping the output to \([0,\mu]\) cannot increase this error. Thus the fixed point can be approximated to coordinate error \(h\) in time polynomial in the input lengths and \(\log(1/h)\).
The following bounds verify that no numerical precision requirement grows beyond polynomial bit length.
Let
\(H=\max\{1,\max_{u,t}B_{ut},\max_{u,t}Q_{ut}\}.\)
Use the induced maximum-row-sum matrix norm. Since \(a_u\leq1\) and \(x_u\geq d\), the earlier inequality gives
\(Ja\leq(1-d)a.\)
Therefore
\(Ra\leq a/d,\qquad \|R\|_\infty\leq d^{-2}.\)
Suppose the computed active vector has coordinate error at most \(h\), and the exponential factors used in the derivative formulas are computed to absolute error at most \(h\), clipped to \([0,1]\). Denote the resulting quantities by tildes. Since the exponential function \(e^{-s}\) is \(1\)-Lipschitz for \(s\geq0\),
\(\|\widetilde J-J\|_\infty\leq2n^2H^2h.\)
If
\(h\leq d^2/(4n^2H^2),\)
the usual inverse perturbation identity gives
\(\|\widetilde R\|_\infty\leq2d^{-2},\qquad \|\widetilde R-R\|_\infty\leq4n^2H^2h/d^4.\)
Writing \(A=RE\), these bounds imply
\(\|\widetilde A-A\|_\infty\leq8n^2H^2h/d^4.\)
Substituting into \(Dw=T+WQA\), using that the diagonal entries of \(T,W,\widetilde T,\widetilde W\) lie in \([0,1]\), gives
\(\|\widetilde{Dw}-Dw\|_\infty\leq12n^3H^3h/d^4.\)
Column summation therefore gives
\(\|\widetilde g-\nabla C(x)\|_\infty\leq12n^4H^3h/d^4.\)
It suffices to choose
\(h\leq\min\{d^2/(4n^2H^2),\ \rho d^4/(16n^4H^3)\}.\)
The logarithm of the reciprocal of this precision is polynomial in the relevant input lengths. The approximate derivative formula involves only rational matrix inversion and rational arithmetic after the exponential approximations have been obtained. These operations also have polynomial bit complexity.
This proves the oracle lemma.
Let
\(\mathrm{OPT}=\sup\{C(y):0\leq y\leq\mu,\ \mathbf1^{\mathsf T}y=\kappa\},\qquad c_*=1-1/e.\)
In particular, \(\mathrm{OPT}\geq\kappa\).
Put \(\eta=\min\{\epsilon,1/2\}\), and choose a dyadic number \(\alpha\) such that
\(\eta/16\leq\alpha\leq\eta/8.\)
Define the positive reserve
\(b_u=\alpha\min\{\mu_u,\kappa/n\},\qquad s_b=\sum_u b_u.\)
Then
\(s_b\leq\alpha\kappa,\qquad 0<b_u\leq\alpha\mu_u.\)
Consider the fixed residual polytope
\(P=\{u\geq0:u\leq\mu-b,\ \mathbf1^{\mathsf T}u\leq\kappa-s_b\},\)
and the function \(f(u)=C(b+u)\), defined on the entire box \(0\leq u\leq\mu-b\).
Choose a power of two \(N\) satisfying
\(N\geq8n/(\alpha\eta),\)
and set \(\Delta=1/N\) and \(\rho=\eta/16\).
Starting from \(u^0=0\), perform the following for \(j=0,\ldots,N-1\):
The linear optimization in step 2 is a fractional-knapsack problem: sort the coefficients and fill coordinates subject to their caps and the single mass budget.
Each \(u^j\) is feasible. Indeed, it is \(j/N\) times an average of points in the convex, downward-closed polytope \(P\).
After the last iteration, increase coordinates of \(b+u^N\), within their remaining caps, until the total mass equals \(\kappa\). Such completion is possible because \(\sum_u\mu_u=1\geq\kappa\). Denote the completed vector by \(x\). Monotonicity gives
\(C(x)\geq f(u^N).\)
For every original feasible vector \(y\), the vector \(u=(1-\alpha)y\) belongs to \(P\). Its coordinate caps follow from \(b\leq\alpha\mu\), and its budget follows from \(s_b\leq\alpha\kappa\).
Using monotonicity and the scaling lemma,
\(f((1-\alpha)y)=C(b+(1-\alpha)y)\geq C((1-\alpha)y)\geq(1-\alpha)C(y).\)
Let \(M=\max_{u\in P}f(u)\). This maximum exists: all seeds in this domain are positive, so the fixed-point and derivative results imply continuity, and \(P\) is compact. Taking a supremum over \(y\) gives
\(M\geq(1-\alpha)\mathrm{OPT}.\)
Thus we do not need the original supremum to be attained.
Let \(u^*\in P\) attain \(M\). Diminishing derivatives and monotonicity imply, for every \(u\in P\),
\(M-f(u)\leq f(u\vee u^*)-f(u)\leq\nabla f(u)^{\mathsf T}(u^*-u)_+\leq\nabla f(u)^{\mathsf T}u^*.\)
The coordinatewise maximum need not belong to \(P\); it belongs to the box on which \(f\) is defined, which is sufficient.
Let \(g^j=\nabla f(u^j)\). Approximate-gradient maximization then gives
\((g^j)^{\mathsf T}v^j\geq M-f(u^j)-2\rho\kappa.\)
Here each gradient replacement costs at most \(\rho\kappa\), because every vector in \(P\) has total mass at most \(\kappa\).
Define coordinate direction bounds
\(r_u=\min\{\mu_u-b_u,\kappa-s_b\}.\)
Every \(v\in P\) satisfies \(v\leq r\). Along each update, derivatives decrease componentwise, so
\(f(u^{j+1})-f(u^j)=\int_0^\Delta\nabla f(u^j+tv^j)^{\mathsf T}v^j\,dt\geq\Delta(g^{j+1})^{\mathsf T}v^j.\)
Consequently,
\(f(u^{j+1})-f(u^j)\geq\Delta(g^j)^{\mathsf T}v^j-\Delta r^{\mathsf T}(g^j-g^{j+1}).\)
The last error term is nonnegative. Combining this with the preceding gap bound and unrolling the recurrence gives
\(f(u^N)\geq[1-(1-\Delta)^N]M-2\rho\kappa-\Delta r^{\mathsf T}g^0.\)
To justify the final term, the geometrically weighted sum of discretization errors is at most their unweighted sum, which telescopes to
\(\Delta r^{\mathsf T}(g^0-g^N)\leq\Delta r^{\mathsf T}g^0.\)
Since \((1-1/N)^N\leq e^{-1}\),
\(f(u^N)\geq c_*M-2\rho\kappa-\Delta r^{\mathsf T}\nabla C(b).\)
This bound uses no Lipschitz constant for the gradient.
For each coordinate,
\(r_u\leq\min\{\mu_u,\kappa\}\leq n\min\{\mu_u,\kappa/n\}=(n/\alpha)b_u.\)
Since the gradient is nonnegative, the bound from Section 2 gives
\(r^{\mathsf T}\nabla C(b)\leq(n/\alpha)b^{\mathsf T}\nabla C(b)\leq(n/\alpha)C(b).\)
The reserve \(b\) can be completed to a feasible vector, so \(C(b)\leq\mathrm{OPT}\). Hence
\(\Delta r^{\mathsf T}\nabla C(b)\leq\frac{n}{\alpha N}\mathrm{OPT}\leq(\eta/8)\mathrm{OPT}.\)
Also,
\(2\rho\kappa=(\eta/8)\kappa\leq(\eta/8)\mathrm{OPT}.\)
Combining these inequalities with \(M\geq(1-\alpha)\mathrm{OPT}\) yields
\(C(x)\geq f(u^N)\geq[c_*(1-\alpha)-\eta/4]\mathrm{OPT}\geq[c_*-3\eta/8]\mathrm{OPT}.\)
Because \(\eta\leq\epsilon\), this proves the requested guarantee.
The smallest valid power of two \(N\) is \(O(n/\eta^2)\), so the number of gradient-oracle calls is polynomial in \(n,1/\epsilon\).
Every queried seed vector satisfies \(x_u\geq b_u\). Thus, uniformly over all oracle calls,
\(\log(1/d)\leq\log(1/\alpha)+\max\{\log(1/\min_u\mu_u),\log(n/\kappa)\}.\)
This is polynomially bounded by the input bit length and \(\log(1/\eta)\). Likewise, \(\log H\) is bounded by the input encoding length. Section 3 therefore gives polynomial time for every gradient query, even when masses are very small or intensities are very large.
The reserve, residual caps, and residual budget are rational numbers of polynomial encoding length. Fractional-knapsack directions use these numbers and their sums and differences. A common denominator of polynomial bit length can be used for all directions; averaging introduces only the additional factor \(N\). Budget completion also uses rational sums and differences. Therefore the returned vector has polynomial encoding length. If the inputs are dyadic, choosing \(\alpha\) dyadic and \(N\) a power of two makes the returned vector dyadic as well.
The resulting algorithm runs in time polynomial in \(m,\tau,L,1/\epsilon\) and produces the required feasible binary rational vector. The proof allows arbitrary nonnegative contact intensities, zero activation probabilities, and within-type contacts.
⟨structured verdict parsed — rendered above⟩
Verdict: proved with minor gaps. The argument establishes the requested polynomial-time approximation in substance. I found no false central step or gap requiring new mathematics. The remaining issue is the precise formulation and tolerance accounting for the cited weak-optimization theorem.
This assessment concerns the continuous mass recurrence in USER_TASK; the proof does not rely on transferring submodularity or computational results from the discrete cascade model.
The telescoping identities are correct. The initial convention \(a^{-1}=0\) gives \(F_x(0)=H_x(0)=x\), so the identities include the base case. For subsequent rounds, multiplying the susceptible-mass factors produces exactly the exponent involving \(a^{r-1}\).
The iteration is increasing and bounded by \(\mu\). Continuity of \(F_x\) justifies passing to the limit in the fixed-point equation. Continuity of \(H_x\) similarly justifies the coverage formula. Monotonicity in the seed vector follows by comparing iterates.
The bounds \(\sum_u x_u\leq C(x)\leq1\) hold on the entire seed box, including vectors below the budget.
The scaling lemma is correct. The stated second derivative
\(h''(t)=-e^{-ts}\bigl(2x_us+(\mu_u-tx_u)s^2\bigr)\)
has the correct sign because \(s\geq0\) and \(tx_u\leq\mu_u\). Concavity therefore gives the stated scaling inequality for \(F\), and induction applies from the common initial vector zero. The corresponding argument for \(H\) correctly incorporates the previously established active-mass inequality.
The cases \(\lambda=0\) and \(\lambda=1\) are included. Continuity at zero seeds is not required.
The uniqueness argument is valid. Concavity and \(F_x(0)=x>0\) give the strict scaling inequality used in the maximum-ratio argument. Every nonnegative fixed point is positive, so the coordinate ratios are defined. If two fixed points differ, interchanging them when necessary makes the maximum ratio strictly greater than one.
The Jacobian calculation and invertibility argument are correct. The inequality using \(se^{-s}\leq1-e^{-s}\) establishes \(Ja\leq a-x\). Because every coordinate of \(x\) is positive, the weighted maximum-norm contraction is strict. This supports both the implicit-function theorem and the nonnegative Neumann-series representation of \(R\).
The formulas \(Da=RE\) and \(Dw=T+WQRE\) correctly account for direct seeding and indirect activation or coverage. In particular, the coverage derivative uses \(Q\), retaining contacts with zero activation probability.
The boundary discussion at \(x_u=\mu_u\) is sound: the defining equation is smooth and its derivative with respect to \(a\) remains invertible.
Diminishing derivatives follow as written. Increasing seeds increases \(a\) and \(w\), decreases the stated diagonal factors, and decreases \(J\). Entrywise monotonicity of the nonnegative powers of \(J\) then decreases \(R\). The products in the derivative formula preserve this ordering.
The integral argument proving \(b^{\mathsf T}\nabla C(b)\leq C(b)\) is valid. It uses differentiability only along positive seed vectors and does not require continuity at zero.
The convex characterization is correct. Each nonlinear constraint is convex. Every point of \(K_x\) is a subsolution whose increasing iteration converges to the unique fixed point. Consequently, every such point lies componentwise below \(a(x)\). This establishes the claimed unique linear maximizer.
The geometric bounds are correct. The proposed interior ball lies inside the rational box and satisfies \(a<F_x(a)\) componentwise. The outer radius is sufficient, including when \(n=1\). Its encoding length and the logarithm of the reciprocal interior radius have the claimed polynomial bounds.
The weak-separation calculations check out. The proposed convex combination with the interior point removes violations bounded by \(2\theta\), and the distance bound is valid. In the separating case, the gradient approximation error contributes at most \(\theta/8\) to the supporting-plane inequality, below the stated positive violation.
The procedure still needs ordinary implementation choices for certification thresholds and hyperplane normalization, but the supplied margins suffice; these do not constitute a substantive gap.
Exponential evaluation has the claimed bit complexity. The large-argument cutoff is valid because \(e^{-b}\leq2^{-b}\) for nonnegative integer \(b\). For arguments below \(b\), a Taylor truncation with a sufficiently large constant multiple of \(b\) terms achieves the stated accuracy with polynomial-length arithmetic. Approximating constraint gradients may require additional bits because of multiplication by entries of \(B\); their encoding lengths provide the required polynomial bound.
Severity: minor.
The proof invokes “approximate linear optimization” and subsequently assumes an output satisfying both distance at most \(\delta\) from \(K_x\) and objective error at most \(\delta\) relative to the maximum over all of \(K_x\).
The standard weak-optimization formulation instead compares the returned objective against points in an eroded body, while permitting the output to lie in an enlarged body. This distinction appears explicitly in [Grötschel and Nešetřil’s account of the GLS theorem](https://www.zib.de/userpage/groetschel/pubnew/groetschel-nesetril.pdf).
The stated full-body guarantee is a standard consequence when the supplied inner and outer bounds are available, so this is an omitted routine tolerance conversion, not missing mathematics.
Minimum clarification required: State the exact optimization theorem or corollary being applied, including its output guarantees. If using the usual eroded-body formulation, specify how its tolerance is chosen from \(\delta\), the interior radius, and the outer bound to obtain the two inequalities subsequently assumed. Include a precise theorem reference.
Conditional on those output guarantees, the coordinate-recovery calculation is correct. The componentwise domination of points in \(K_x\) converts the objective error into coordinate error. The constants \(1+\sqrt n\) and \(2+\sqrt n\) are valid. Clipping cannot increase the coordinate error.
The numerical bounds are valid. The inequalities \(Ja\leq(1-d)a\), \(Ra\leq a/d\), and \(\|R\|_\infty\leq d^{-2}\) follow from the stated coordinate bounds.
The perturbation threshold makes the inverse perturbation product at most one half. The subsequent bounds for \(\widetilde R\), \(\widetilde A\), and \(\widetilde{Dw}\) are conservative but sufficient. Passing from maximum row-sum error to a column-sum error introduces at most the additional factor \(n\) stated in the proof.
The selected accuracy therefore gives the required gradient error. Its reciprocal has polynomial logarithmic length, and rational matrix inversion has polynomial bit complexity for matrices of the resulting encoding size.
The reserve and residual polytope are correctly constructed. All reserve coordinates are positive; its mass and coordinate bounds are valid.
Each update remains feasible because it is a scaled average of points in the convex polytope \(P\). Fractional-knapsack optimization is appropriate. Because approximate coefficients can be negative, an implementation must leave budget unused when filling another coordinate would decrease the linear objective; the instruction to maximize over \(P\) already requires this.
Budget completion is possible because the total available mass is one and \(\kappa\leq1\). It preserves rationality and cannot reduce coverage.
Every substantive inequality in the approximation analysis is valid.
The argument also covers guarantees that become nonpositive for large \(\epsilon\).
The running-time and output-length analysis is sound, subject to the minor theorem clarification above.
The smallest admissible power of two has size \(O(n/\eta^2)\). Positive reserve coordinates uniformly bound the precision requirements across all queries. Small masses and large intensities affect bit precision through logarithms of their magnitudes.
The direction vectors admit the stated polynomial-length common denominator, and averaging and budget completion preserve polynomial encoding length. The distinction between binary-encoded rationals and dyadic rationals is explicitly addressed.
No restriction excluding within-type contacts, zero contact intensities, or zero activation probabilities enters the argument. The edge cases \(n=1\), \(\kappa=1\), and absence of positive contacts do not invalidate any step.
Actionable feedback: Make the weak-optimization theorem and its tolerance conversion explicit. No substantive replacement argument is needed.
⟨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.