Answer: Yes. A deterministic algorithm running in time polynomial in \(\tau\), \(L\), and \(1/\epsilon\) returns a feasible rational allocation \(d\) satisfying \(\Phi_K(d)\ge(1-1/e-\epsilon)\mathrm{OPT}\).
Theorem 4 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateMLE-Greedy is a (1 −1/𝑒)-factor approximation algorithm for FIM. Equivalently, 𝐹(x(𝑘)) ≥(1 −1/𝑒) 𝐹(x∗(𝑘)) . We defer the proof.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given \(\tau\) types with rational masses \(\mu_t>0\) summing to \(1\), a rational type-to-type contact-rate kernel \(K\), and a per-capita budget \(\kappa\), choose type-level seed probabilities \(d_t\in[0,1]\) with \(\sum_t\mu_t d_t\le\kappa\) to maximize limiting active mass \(\Phi_K(d)=\sum_t\mu_t a_t^{(\infty)}\), where \(a_t^{(0)}=d_t\) and \(a_t^{(r+1)}=1-(1-d_t)\exp(-\sum_s\mu_sK_{st}a_s^{(r)})\). Does there exist an algorithm, polynomial in \(\tau\), input bit length \(L\), and \(1/\epsilon\), that returns a feasible rational \(d\) with value at least \((1-1/e-\epsilon)\) times optimum?
A society is given by its support: a list of \(\tau\ge1\) types with positive binary-rational masses \(\mu_t\) summing to \(1\); \(\tau\) is the support size, not the number of possible types.
The input also contains a directed contact-rate matrix \(K\in\mathbb{Q}_{\ge0}^{\tau\times\tau}\), a binary-rational per-capita budget \(0<\kappa\le1\), and a binary-rational accuracy parameter \(0<\epsilon<1-1/e\). Entries of \(K\), including diagonal entries, are unrestricted nonnegative rates; \(K_{st}\) describes influence from type \(s\) to type \(t\).
An allocation is \(d\in[0,1]^\tau\) satisfying \(\sum_t\mu_t d_t\le\kappa\). Define \(a_t^{(0)}=d_t\) and \(a_t^{(r+1)}=1-(1-d_t)\exp(-\sum_s\mu_sK_{st}a_s^{(r)})\) for \(r\ge0\).
Use the componentwise limit of this iteration, \(a^{(\infty)}\), to define \(\Phi_K(d)=\sum_t\mu_t a_t^{(\infty)}\) and \(\mathrm{OPT}=\sup\{\Phi_K(d):d\in[0,1]^\tau,\ \sum_t\mu_td_t\le\kappa\}\).
Let \(L\) be the total binary input length. Computation uses the ordinary bit model with no value or gradient oracle; there is no separate parameter \(m\) in this model.
Does there exist an algorithm running in time polynomial in \(\tau\), \(L\), and \(1/\epsilon\) that returns a feasible rational allocation \(d\) satisfying \(\Phi_K(d)\ge(1-1/e-\epsilon)\mathrm{OPT}\)?
For finite independent-cascade networks with independent initial activation probabilities and a unit-cost incentive budget, MLE-Greedy achieves a \((1-1/e)\) approximation using a discrete influence subroutine ([Umrawal et al.](https://doi.org/10.1613/jair.1.20410)).
Finite-network independent-cascade seed selection also admits a \((1-1/e-\epsilon)\) approximation ([Borgs et al.](https://arxiv.org/abs/1212.0884)). No result settling the stated mass-based iteration problem was identified in the search.
Yes. There is a deterministic algorithm with the requested running time and approximation guarantee. The proof uses an explicit convex program, together with certified finite-precision computations.
Write \(c=1-1/e\), and define the nonnegative matrix \(B\) by \(B_{ts}=\mu_sK_{st}\). Thus \((Ba)_t=\sum_s\mu_sK_{st}a_s\).
For an allocation \(d\), let
\[ M_d(a)_t=1-(1-d_t)\exp(-(Ba)_t). \]
The map \(M_d\) is componentwise nondecreasing in both \(a\) and \(d\). Moreover, \(M_d(d)\ge d\), and \(M_d\) maps \([0,1]^\tau\) into itself. Consequently, the prescribed iteration increases componentwise and has a limit. Continuity of \(M_d\) implies that this limit is a fixed point.
Every fixed point \(x\in[0,1]^\tau\) satisfies \(x=M_d(x)\ge d\). Induction therefore shows that the prescribed limit is the least fixed point in this cube. Comparing iterations also proves that \(\Phi_K\) is componentwise nondecreasing.
We will use the bounds
\[ \kappa\le\mathrm{OPT}\le1. \]
The lower bound follows from the feasible uniform allocation \(d_t=\kappa\), whose limiting activation is at least its initial activation. The upper bound follows from \(a_t^{(\infty)}\le1\).
For \(h\in\mathbb R_{\ge0}^\tau\), define
\[ q(h)_t=1-\exp(-h_t),\qquad T_h(a)_t=1-\exp(-h_t-(Ba)_t). \]
Let \(b^*(h)\) be the limit of the iteration starting at \(q(h)\), and put \(F(h)=\sum_t\mu_tb_t^*(h)\). By definition,
\[ F(h)=\Phi_K(q(h)). \]
Each coordinate of \(T_h(a)\) is jointly concave in \((h,a)\) and nondecreasing in \(a\). The initial vector \(q(h)\) is componentwise concave in \(h\).
Inductively, every finite iterate is componentwise concave in \(h\): first use monotonicity in \(a\) to insert the concavity inequality for the preceding iterate, and then use joint concavity of \(T\). Passing to the componentwise limit preserves these inequalities.
Thus \(F\) is concave and nondecreasing on \(\mathbb R_{\ge0}^\tau\), and \(F(0)=0\). In particular,
\[ F(\alpha h)\ge\alpha F(h) \quad\text{for }0\le\alpha\le1. \]
For every \(d\in[0,1]^\tau\),
\[ F(d)\ge c\,\Phi_K(d). \]
Here \(d\) on the left is the argument of \(F\), so the corresponding initial activation is \(q(d)\).
To prove this, fix \(x\in[0,1]\) and \(z\ge0\), and define
\[ H_x(z)=1-\exp(-x-cz)-c\bigl(1-(1-x)\exp(-z)\bigr). \]
Its derivative satisfies
\[ H_x'(z) =c\bigl(\exp(-x-cz)-(1-x)\exp(-z)\bigr)\ge0, \]
because \(\exp(-x)\ge1-x\) and \(\exp(-cz)\ge\exp(-z)\). Concavity of \(x\mapsto1-\exp(-x)\), applied to its endpoints on \([0,1]\), gives
\[ H_x(0)=1-\exp(-x)-cx\ge0. \]
Therefore
\[ 1-\exp(-x-cz) \ge c\bigl(1-(1-x)\exp(-z)\bigr). \]
Let \(a^{(r)}\) be the original iteration for \(d\), and let \(b^{(r)}\) be the iteration for \(q(d)\). Initially, \(b^{(0)}\ge ca^{(0)}\). If \(b^{(r)}\ge ca^{(r)}\), nonnegativity of \(B\) and the scalar inequality above give
\[ b^{(r+1)}=T_d(b^{(r)})\ge T_d(ca^{(r)}) \ge ca^{(r+1)}. \]
Taking limits and then weighted sums proves the comparison.
Suppose every coordinate of \(h\) is positive. We claim that every \(u\in[0,1]^\tau\) satisfying \(u\le T_h(u)\) also satisfies \(u\le b^*(h)\).
First, \(b^*(h)\ge q(h)>0\). Suppose, toward a contradiction, that
\[ r=\max_t\frac{u_t}{b_t^*(h)}>1. \]
The map \(T_h\) is concave on the entire nonnegative orthant. Applying concavity to
\[ b^*(h)=\frac1r\bigl(rb^*(h)\bigr) +\left(1-\frac1r\right)0 \]
gives
\[ T_h(rb^*(h)) \le rT_h(b^*(h))-(r-1)T_h(0) <rb^*(h) \]
componentwise. The strict inequality uses \(T_h(0)=q(h)>0\).
Choose a coordinate \(j\) attaining the maximum ratio. Since \(u\le rb^*(h)\), monotonicity implies
\[ u_j\le T_h(u)_j \le T_h(rb^*(h))_j <rb_j^*(h)=u_j, \]
a contradiction.
This proves the claim. It also proves uniqueness of the fixed point when \(h>0\).
Positivity matters: with one type, contact rate \(2\), and zero seeding, the prescribed iteration stays at zero, although \(a=1-\exp(-2a)\) has a positive fixed point. We will enforce positive seeding explicitly.
Set
\[ \sigma=\frac{\epsilon}{16},\qquad \delta=\sigma\kappa,\qquad b=(1-2\sigma)\kappa. \]
Since \(\epsilon<1\), we have \(0<\delta\le\sigma<1/16\).
For \(a_t<1\), define
\[ g_t(a)=-\log(1-a_t)-(Ba)_t. \]
Each \(g_t\) is convex, and \(g_t(0)=0\).
Consider the compact convex set \(C\) of pairs \((a,h)\) satisfying
\[ 0\le a_t\le1-\delta,\qquad \delta\le h_t\le1,\qquad \sum_t\mu_th_t\le b,\qquad g_t(a)\le h_t \]
for every type \(t\). Let \(V\) be the maximum of the linear objective \(\sum_t\mu_ta_t\) on \(C\).
The last inequalities are equivalent to \(a\le T_h(a)\). Because \(h_t\ge\delta>0\), Section 3 implies that every feasible pair satisfies
\[ \sum_t\mu_ta_t\le F(h). \]
We next prove
\[ V\ge(c-4\sigma)\mathrm{OPT}. \]
Take any feasible allocation \(d\) for the original problem and set
\[ h_d=(1-3\sigma)d+\delta\mathbf1. \]
Its coordinates lie in \([\delta,1]\), and
\[ \sum_t\mu_t(h_d)_t \le(1-3\sigma)\kappa+\delta=b. \]
By monotonicity, concavity, and Section 2,
\[ F(h_d)\ge F((1-3\sigma)d) \ge(1-3\sigma)F(d) \ge(1-3\sigma)c\,\Phi_K(d). \]
Write \(x=b^*(h_d)\). Every coordinate of \(x\) is strictly below \(1\), because \(h_d\) and \(B\) are finite and \(x=T_{h_d}(x)\). Its fixed-point equation gives \(g_t(x)=(h_d)_t\).
Convexity and \(g_t(0)=0\) imply
\[ g_t((1-\delta)x) \le(1-\delta)g_t(x) \le(h_d)_t. \]
Consequently, \(((1-\delta)x,h_d)\in C\), and hence
\[ V\ge(1-\delta)(1-3\sigma)c\,\Phi_K(d). \]
This holds for every feasible \(d\), whether or not the original supremum is attained. Taking the supremum and using \(\delta\le\sigma\) yields
\[ V\ge(1-4\sigma)c\,\mathrm{OPT} \ge(c-4\sigma)\mathrm{OPT}. \]
We now establish that this convex program can be approximately optimized in the ordinary bit model.
Define
\[ G=\delta^{-1}+1+\max_t\sum_sB_{ts}. \]
For \(f_t(a,h)=g_t(a)-h_t\), the gradient on the bounding box satisfies
\[ \|\nabla f_t(a,h)\|_1 \le\delta^{-1}+\sum_sB_{ts}+1\le G. \]
Thus each \(f_t\) is \(G\)-Lipschitz in the maximum norm on that box.
Take the rational center
\[ z_0=(a_0,h_0),\qquad a_0=\frac{\delta}{4}\mathbf1,\qquad h_0=2\delta\mathbf1. \]
Using \(-\log(1-u)\le u/(1-u)\) gives
\[ f_t(z_0) \le-\log(1-\delta/4)-2\delta \le-\frac{3\delta}{2}. \]
The budget slack at \(z_0\) is
\[ b-\sum_t\mu_t(h_0)_t=(1-4\sigma)\kappa>\kappa/2. \]
Set
\[ r=\frac{\delta}{16(G+1)},\qquad R=2\tau. \]
The Euclidean ball of radius \(r\) about \(z_0\) lies in \(C\). Indeed:
Also, \(C\) lies in the Euclidean ball of radius \(R\) about \(z_0\), because both \(C\) and \(z_0\) lie in \([0,1]^{2\tau}\).
These radii and the center have polynomial encoding length. Large contact rates enter through the binary encoding of \(G\), rather than through a dependence polynomial in their numerical magnitude.
Given a rational query point \(y=(a,h)\) and rational tolerance \(t>0\), first check all linear constraints exactly. A violated linear constraint supplies a rational separating hyperplane.
Otherwise, \(y\) is in the bounding box and satisfies the budget. Put
\[ u=\frac{t\delta}{4R}. \]
Approximate each \(f_t(y)\) to absolute error at most \(u/4\).
If an approximation exceeds \(u/2\), the corresponding true value is positive. Its gradient is rational:
\[ \nabla f_t(a,h) =\left(\frac{e_t}{1-a_t}-B_{t\bullet},-e_t\right). \]
For every \(z\in C\), convexity gives
\[ \nabla f_t(y)\cdot(z-y) \le f_t(z)-f_t(y)<0. \]
Thus this gradient supplies a genuine rational separating hyperplane.
If no approximation exceeds \(u/2\), all true constraint values are at most \(u\). Define
\[ \lambda=\frac{u}{u+\delta},\qquad z=(1-\lambda)y+\lambda z_0. \]
The linear constraints remain satisfied. Since \(f_t(y)\le u\) and \(f_t(z_0)\le-\delta\), convexity gives \(f_t(z)\le0\), so \(z\in C\). Moreover,
\[ \|z-y\|_2 \le\lambda R\le\frac{Ru}{\delta}=\frac t4. \]
The routine therefore correctly certifies proximity to \(C\).
Only logarithms require transcendental computation in this routine. They can be computed with certified error in polynomial time. Explicitly, scale a positive rational argument as \(2^{-k}v\), where \(1\le v<2\), and use
\[ \log v =2\sum_{j=0}^{\infty} \frac{w^{2j+1}}{2j+1}, \qquad w=\frac{v-1}{v+1}\in[0,1/3]. \]
The tail decreases geometrically; the same series computes \(\log2\). Rational partial sums and tail bounds give the required certified precision with polynomially many bit operations.
We use the standard weak separation-to-optimization theorem: for a compact convex body with explicitly supplied inner and outer balls, polynomial-time weak separation permits polynomial-time linear optimization with both additive objective error and distance-to-feasibility error bounded by a prescribed rational tolerance. This is the bit-model theorem of [Grötschel, Lovász, and Schrijver, Sections 1–3](https://ir.cwi.nl/pub/10046/10046D.pdf).
All its hypotheses have just been verified. Apply it with objective \((\mu,0)\), whose Euclidean norm is at most \(1\), and tolerance
\[ \theta=\frac{\delta}{32(G+1)}=\frac r2. \]
It returns a rational point \((\widetilde a,\widetilde h)\) satisfying
\[ \operatorname{dist}((\widetilde a,\widetilde h),C)\le\theta, \qquad \sum_t\mu_t\widetilde a_t\ge V-\theta. \]
The routine and the resulting optimization algorithm have polynomial bit complexity. In particular, the encoding lengths of \(\delta,G,r,R,\theta\) are polynomial in the input length.
Clip \(\widetilde a_t\) to \([0,1-\delta]\) and \(\widetilde h_t\) to \([\delta,1]\), obtaining rational vectors \(\bar a,\bar h\).
Choose a closest point of \(C\). Coordinatewise clipping cannot increase distance to that point. Each clipped coordinate is therefore within \(\theta\) of its corresponding coordinate in \(C\). It follows that
\[ \sum_t\mu_t\bar a_t\ge V-2\theta, \qquad \sum_t\mu_t\bar h_t\le b+\theta, \qquad g_t(\bar a)-\bar h_t\le G\theta. \]
Define \(h^+=\bar h+G\theta\mathbf1\). Then \(h^+>0\) and \(\bar a\le T_{h^+}(\bar a)\). Section 3 gives
\[ F(h^+)\ge\sum_t\mu_t\bar a_t. \]
Set \(\zeta=\delta/32\). Compute rational coordinates \(d_t\in[0,1]\) satisfying
\[ 1-\exp(-h_t^+) \le d_t \le1-\exp(-h_t^+)+\zeta. \]
This is polynomial-time certified upward rounding. Indeed, \(h_t^+<2\); Taylor expansion of the bounded-argument exponential has factorial remainder bounds, and a sufficiently fine dyadic rounding adds at most the prescribed error.
Because \(1-\exp(-x)\le x\) for \(x\ge0\),
\[ \sum_t\mu_td_t \le b+(G+1)\theta+\zeta =b+\frac{\delta}{16}<\kappa. \]
Thus the rational output is feasible.
Monotonicity of \(\Phi_K\), followed by the preceding bounds, gives
\[ \Phi_K(d) \ge F(h^+) \ge V-2\theta \ge(c-4\sigma)\mathrm{OPT}-2\theta. \]
Finally, \(2\theta\le\delta=\sigma\kappa\le\sigma\mathrm{OPT}\), so
\[ \Phi_K(d) \ge(c-5\sigma)\mathrm{OPT} \ge(1-1/e-\epsilon)\mathrm{OPT}. \]
The construction uses polynomially many bit operations in \(\tau\) and \(L\), and therefore satisfies the requested polynomial bound in \(\tau,L,1/\epsilon\). It computes neither values nor gradients of the original limiting objective.
⟨structured verdict parsed — rendered above⟩
The argument is sound in substance and resolves the target with one minor expositional gap. I found no false central step, missing mathematical lemma, or dependence on an unavailable influence oracle.
The sole issue is that the separation routine does not explicitly specify the normalization of its rational cut vectors required by the formal weak-separation interface. This is a routine implementation clarification.
The monotonicity assertions hold because \(B\) is nonnegative and \(1-d_t\) is nonnegative on the allocation domain. The iteration starts at \(d\), increases componentwise, and remains in the cube. Its componentwise limit exists and is a fixed point by continuity.
Every fixed point in the cube dominates \(d\). Comparing that fixed point with each iterate proves that the prescribed limit is the least fixed point. Comparing iterations for two ordered allocations also proves the claimed monotonicity of \(\Phi_K\).
The bounds \(\kappa\le\mathrm{OPT}\le1\) are correct, including when \(\kappa=1\).
No issue.
Each coordinate of \(T_h(a)\) is jointly concave in its arguments and nondecreasing in \(a\). Consequently, the stated induction proves componentwise concavity of every finite iterate as a function of \(h\). Passing to the limit preserves the concavity inequalities.
At \(h=0\), the prescribed iteration remains zero, so \(F(0)=0\). The resulting scaling inequality is valid. This argument does not require continuity of \(F\) at the boundary.
The scalar comparison is also correct. Differentiating the displayed expression gives exactly
\[
H_x'(z)=c\bigl(\exp(-x-cz)-(1-x)\exp(-z)\bigr).
\]
Both inequalities used to show this derivative is nonnegative hold throughout the stated domains. Concavity of \(1-\exp(-x)\) supplies the endpoint bound at \(z=0\).
The comparison of iterations has the correct initialization and induction step. It proves \(F(d)\ge c\,\Phi_K(d)\), including allocations with zero or unit coordinates.
No issue.
The ratio argument is valid because every coordinate of \(b^*(h)\) is positive.
Although the vector \(rb^*(h)\) may leave the cube, \(T_h\) is defined, concave, and monotone on the entire nonnegative orthant. Thus the concavity application uses a valid domain. Strictness follows in every coordinate from \(T_h(0)>0\).
The maximizing coordinate then produces the stated contradiction. This establishes the subsolution bound. Together with the previously established least-fixed-point property, it also establishes uniqueness for positive \(h\).
The zero-seeding example correctly explains why positivity is necessary.
No issue.
The functions \(g_t\) are convex on the specified box, and the logarithms are defined there because \(\delta>0\). The constraints therefore define a closed, bounded convex set.
The equivalence between \(g_t(a)\le h_t\) and \(a_t\le T_h(a)_t\) has the correct inequality direction. Positive seeding permits the use of Section 3.
The constructed vector \(h_d\) satisfies both its coordinate bounds and its budget bound. The fixed point \(x\) has coordinates strictly below one, so its logarithmic fixed-point equation is valid.
Convexity justifies the scaled feasible vector. The coefficient calculation is correct:
\[
(1-\delta)(1-3\sigma)\ge1-4\sigma.
\]
Taking the supremum over original allocations does not assume that the supremum is attained.
No issue.
The gradient bound \(G\) correctly controls the maximum-norm Lipschitz constant on the bounding box.
The proposed center has the claimed nonlinear slack: the logarithmic estimate is valid for the full stated range of \(\delta\). Its budget slack is greater than \(\kappa/2\). The proposed radius fits within every box constraint and preserves both budget and nonlinear feasibility. The outer radius is sufficient in dimension \(2\tau\).
All these rational quantities have polynomial encoding length. In particular, dependence on large contact rates occurs through their binary lengths and the precision parameters, rather than through their numerical magnitude.
For nonlinear separation, an approximation exceeding \(u/2\) implies a strictly positive true constraint value. Convexity then supplies a valid rational cut direction. In the acceptance branch, all true violations are at most \(u\), and the displayed convex combination lies in \(C\) within distance \(t/4\). The proximity certificate is therefore correct.
The logarithm series has the stated geometrically decreasing tail. Its scaling and rational arithmetic support polynomial-time certified evaluation at the required absolute precision.
The cited theorem applies to compact convex bodies with supplied inner and outer balls, and its weak-optimization output includes both distance-to-feasibility and additive objective guarantees. These match the guarantees used here. See definitions (5)–(7) and Theorem 3.1 in [Grötschel, Lovász, and Schrijver](https://ir.cwi.nl/pub/10046/10046D.pdf).
Minor issue: The write-up describes rational separating hyperplanes but leaves their cut-vector normalization implicit. To make the theorem application formally verifiable as an implementation, specify the exact weak-separation output convention and the polynomial-time rational normalization used for both linear and nonlinear cuts. This requires no new mathematics and does not undermine the result.
Clipping cannot increase distance to the selected feasible comparison point. The objective, budget, and nonlinear violation bounds after clipping follow with the stated constants.
Adding \(G\theta\) to each coordinate of \(\bar h\) makes \(\bar a\) a subsolution with positive seeding. Section 3 then applies.
The exponential arguments are bounded by two, so the stated certified Taylor evaluation and upward rational rounding are valid. The rounding tolerance can be achieved in polynomial bit complexity.
The budget calculation checks:
\[
(G+1)\theta+\zeta=\delta/16,
\]
and \(b+\delta/16<\kappa\). The output is therefore feasible.
Finally,
\[
2\theta\le\delta=\sigma\kappa\le\sigma\mathrm{OPT}
\]
correctly converts the additive optimization error into the claimed multiplicative loss. Since \(5\sigma=5\epsilon/16\le\epsilon\), the requested approximation follows.
No issue.
Specify the formal weak-separation contract, including its cut-vector normalization, and state how the returned rational vectors meet that contract in polynomial bit complexity. No substantive revision of the mathematical 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.