Answer: Yes. A polynomial-time algorithm returns a feasible binary-rational allocation \(x\) satisfying the stronger bound \(W(x)\geq\sqrt{1-1/e}\,\mathrm{OPT}-\epsilon\).
Lemma 1 — class: other
PDF text-layer excerpt — equations and symbol order may be approximateIn the influence maximization problem, any welfare function that satisfies principles 1-5 is monotone and submodular.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite type set \(T\), rational type masses \(\mu_t>0\) summing to \(1\), community labels \(c(t)\), rational transmission rates \(\kappa_{st}\), a seed budget \(\beta\), and \(\alpha\in(0,1)\), let \(x_t\in[0,\mu_t]\) with \(\sum_t x_t\le\beta\). Define limiting reached fractions by \(y_t=1-(1-x_t/\mu_t)\exp(-\sum_s\mu_s\kappa_{st}y_s)\), taking the least fixed point, and set \(\mu_c=\sum_{t:c(t)=c}\mu_t\), \(u_c(x)=\sum_{t:c(t)=c}\mu_t y_t/\mu_c\), and \(W_\alpha(x)=\sum_c\mu_c u_c(x)^\alpha/\alpha\). Does this typed-population welfare objective retain a monotone diminishing-returns property that yields a polynomial-time \(1-1/e\)-approximation to its maximum, with running time measured in \(\tau=|T|\) and the input bit length?
A society is given by its support: a nonempty list \(T\) of \(\tau=|T|\) types with positive binary-rational masses \(\mu_t\) summing to \(1\). Here \(\tau\) is the support size, not the number of possible types. Community labels \(c:T\to\{1,\ldots,m\}\) form a partition into \(m\) nonempty communities.
The remaining inputs are binary-rational transmission intensities \(\lambda_{st}\geq0\), a binary-rational seed budget \(\beta\in[0,1]\), and binary-rational accuracy \(\epsilon\in(0,1)\); \(L\) is the total input bit length. Intensities may be asymmetric and may have nonzero diagonal entries.
A feasible allocation has real coordinates \(0\leq x_t\leq\mu_t\) and \(\sum_t x_t\leq\beta\). Set \(q_t=x_t/\mu_t\), \(a_t^{(0)}=q_t\), and \(a_t^{(r+1)}=q_t+(1-q_t)\left(1-\exp\left(-\sum_{s\in T}\mu_s\lambda_{st}a_s^{(r)}\right)\right)\). Define \(a_t=\lim_{r\to\infty}a_t^{(r)}\), using this initialization even when other fixed points exist.
Let \(\mu_c=\sum_{t:c(t)=c}\mu_t\), \(u_c(x)=\mu_c^{-1}\sum_{t:c(t)=c}\mu_ta_t\), \(W(x)=2\sum_{c=1}^{m}\mu_c\sqrt{u_c(x)}\), and \(\mathrm{OPT}=\sup\{W(x):x\text{ is feasible}\}\).
Does an algorithm running in \(\operatorname{poly}(m,\tau,L,1/\epsilon)\) return a feasible binary-rational allocation \(x\) satisfying \(W(x)\geq(1-1/e)\mathrm{OPT}-\epsilon\) for every instance?
For finite Independent Cascade networks, community-size-weighted square-root welfare is monotone and submodular; greedy selection under a cardinality budget has a \((1-1/e)\) guarantee with exact value access. [Source](https://arxiv.org/html/2006.07906).
A different continuous marketing model has a \((1-1/e-\epsilon)\) approximation for independent strategy activations and total-spread-plus-budget-saving welfare. [Source](https://ojs.aaai.org/index.php/AAAI/article/view/5332). No result settling the precise recurrence and welfare objective above was located.
Yes. There is a polynomial-time algorithm returning a feasible binary-rational allocation \(x\) with the stronger guarantee
\(W(x)\geq \sqrt{1-1/e}\,\mathrm{OPT}-\epsilon.\)
The proof uses a convex relaxation and a rounding procedure that ensures every type receives a strictly positive seed whenever \(\beta>0\). Strict positivity is what makes the relaxation compatible with the specified initialization.
Write \(B_{ts}=\mu_s\lambda_{st}\), so that \((Ba)_t=\sum_s\mu_s\lambda_{st}a_s\). For \(q\in[0,1]^\tau\), define
\(F_q(a)_t=1-(1-q_t)\exp(-(Ba)_t).\)
The prescribed iteration starts at \(a^{(0)}=q\). Since \(B\) has nonnegative entries, \(F_q\) is coordinatewise nondecreasing. Also, \(F_q(q)\geq q\), and \(F_q\) maps \([0,1]^\tau\) into itself. Consequently, the iterates increase coordinatewise to a limit \(a(q)\). Continuity gives \(F_q(a(q))=a(q)\).
For every fixed point \(d\in[0,1]^\tau\), we have \(d=F_q(d)\geq q\). Induction then gives \(a^{(r)}\leq d\), so \(a(q)\) is the least fixed point.
We need a stronger comparison when every seed coordinate is positive.
Lemma. Suppose \(q_t>0\) for every \(t\). If \(b\in[0,1]^\tau\) satisfies \(b\leq F_q(b)\), then \(b\leq a(q)\).
Proof. Put \(a=a(q)\). Since \(a\geq q\), every coordinate of \(a\) is positive. Suppose, contrary to the claim, that
\(r=\max_t b_t/a_t>1.\)
Choose \(i\) attaining this maximum. Each coordinate of \(F_q\) is concave as a function of its activation argument, and the same formula defines a nondecreasing map on the entire nonnegative orthant. Concavity applied to \(a=r^{-1}(ra)+(1-r^{-1})0\) gives
\(F_q(ra)\leq rF_q(a)-(r-1)F_q(0)=ra-(r-1)q.\)
Because \(b\leq ra\), we obtain
\(b_i\leq F_q(b)_i\leq F_q(ra)_i\leq ra_i-(r-1)q_i<ra_i=b_i,\)
a contradiction. This proves the lemma.
For \(y,b\in[0,1]^\tau\), define the exponential-hazard map
\(H_y(b)_t=1-\exp(-y_t-(Bb)_t).\)
Introduce variables \(v_c\in[0,1]\), one per community, and let \(K\) be the set of triples \((y,b,v)\) satisfying
Every constraint is convex: the exponential has an affine argument, and the last constraint is a convex quadratic minus a linear function. Thus \(K\) is compact and convex.
Consider the linear objective
\(C(y,b,v)=2\sum_c\mu_cv_c,\qquad V=\max_{(y,b,v)\in K}C(y,b,v).\)
Since \(v_c\leq1\) and \(\sum_c\mu_c=1\), we have \(V\leq2\).
If \((y,b,v)\in K\) has every \(y_t>0\), then \(x_t=\mu_ty_t\) is feasible for the original problem. Moreover, \(1-e^{-y_t}\leq y_t\), so
\(b\leq H_y(b)\leq F_y(b).\)
The lemma implies \(b\leq a(y)\). Hence
\(W(x)\geq2\sum_c\mu_c\sqrt{\mu_c^{-1}\sum_{t:c(t)=c}\mu_tb_t}\geq C(y,b,v).\)
The qualification \(y_t>0\) matters: at \(y=0\), the convex inequalities can admit positive activation vectors although the prescribed iteration remains identically zero. Section 4 ensures strict positivity.
Let \(\alpha=1-1/e\). We prove
\(V\geq\sqrt{\alpha}\,\mathrm{OPT}.\)
Take any feasible original allocation, with seed fractions \(q\) and prescribed limit \(a=a(q)\). Concavity of \(z\mapsto1-e^{-z}\) on \([0,1]\) gives
\(1-e^{-q_t}\geq\alpha q_t.\)
For a fixed coordinate \(t\), put \(h=(Ba)_t\geq0\), and consider
\(f(s)=F_{sq}(sa)_t=1-(1-sq_t)e^{-sh},\qquad 0\leq s\leq1.\)
Its second derivative is
\(f''(s)=-e^{-sh}\bigl(h^2(1-sq_t)+2hq_t\bigr)\leq0.\)
Since \(f(0)=0\), concavity implies
\(F_{\alpha q}(\alpha a)_t=f(\alpha)\geq\alpha f(1)=\alpha a_t.\)
The map \(F_q\) is nondecreasing in its seed argument. Therefore,
\(H_q(\alpha a)=F_{1-e^{-q}}(\alpha a)\geq F_{\alpha q}(\alpha a)\geq\alpha a.\)
Thus the triple defined by
\(y=q,\qquad b=\alpha a,\qquad v_c=\sqrt{\alpha u_c(x)}\)
belongs to \(K\), and its objective is \(\sqrt{\alpha}W(x)\). Taking the supremum over feasible original allocations proves the claimed bound on \(V\). No attainment of \(\mathrm{OPT}\) is needed.
We now justify the computational step, including its dependence on small masses and budgets.
If \(\beta=0\), return \(x=0\). The prescribed iteration is then zero, so \(\mathrm{OPT}=0\). Assume henceforth that \(\beta>0\).
Let
\(n=2\tau+m,\qquad H=1+\max_t\sum_sB_{ts},\qquad G=8H,\qquad \sigma=\beta/32.\)
Represent all the inequalities defining \(K\) as \(g_j(z)\leq0\), where \(z=(y,b,v)\). Define the rational point \(z_0\) by
\(y_t=\beta/2,\qquad b_t=\beta/8,\qquad v_c=\beta/16.\)
Every defining inequality has slack at least \(\sigma\) at \(z_0\). For the exponential constraints, use
\(1-e^{-\beta/2}\geq\beta/2-\beta^2/8\geq3\beta/8,\)
which gives
\(g_t(z_0)\leq\beta/8-1+e^{-\beta/2}\leq-\beta/4.\)
For the community constraints,
\(g_c(z_0)=\beta^2/256-\beta/8\leq-31\beta/256.\)
The box and budget constraints also have slack at least \(\sigma\).
On the box \(\Omega=[-1/H,1+1/H]^n\), every \(g_j\) is \(G\)-Lipschitz in Euclidean norm. Indeed, \(y_t+(Bb)_t\geq-1\) there, so the exponential is at most \(e<3\). The exponential constraint’s gradient has norm at most \(1+3H\), the community constraint’s gradient has norm at most \(5\), and the affine constraint gradients have norm at most \(1\).
It follows that
\(B_2(z_0,\sigma/G)\subseteq K\subseteq B_2(z_0,n).\)
Both radii and the center have polynomial encoding length.
For completeness, the transcendental constraints permit a weak separation oracle in the ordinary binary model.
Given a rational query \(z\) and tolerance \(\delta>0\), first separate any violated box constraint exactly. Otherwise, \(z\in[0,1]^n\). Set
\(\nu=\min\{\sigma/6,\delta\sigma/(6n)\}.\)
Approximate every \(g_j(z)\) within \(\nu\), and every gradient coordinate within \(\nu/(2n)\).
If an approximate constraint value exceeds \(2\nu\), its true value exceeds \(\nu\). Convexity gives, for every \(w\in K\),
\(\nabla g_j(z)\cdot(w-z)\leq-g_j(z)<-\nu.\)
Replacing the gradient by its rational approximation changes this inner product by at most \(\nu/2\), because \(\|w-z\|_1\leq n\). The approximate gradient therefore supplies a strict rational separating hyperplane.
If no approximate value exceeds \(2\nu\), every true value is at most \(3\nu\). With \(\theta_0=3\nu/\sigma\leq1/2\), convexity shows that
\((1-\theta_0)z+\theta_0z_0\in K.\)
Its distance from \(z\) is at most \(3\nu n/\sigma\leq\delta\), so the oracle may certify approximate membership.
These computations take polynomial time. At queries inside the unit box, the only transcendental quantity is \(e^{-h}\) for a nonnegative rational \(h\). To obtain absolute error \(2^{-p}\), sufficiently large \(h\) can be replaced by zero; otherwise, range reduction, Taylor approximation on \([0,1]\), and repeated squaring use polynomially many bit operations. Approximating gradients merely requires extra precision proportional to the encoding length of \(B\).
The standard weak separation-to-optimization theorem now applies: for a compact convex body with known inner and outer balls and a polynomial-time weak separation oracle, linear weak optimization is polynomial-time. In the form used here, it returns a rational point within distance \(\eta\) of \(K\), whose objective is within \(\eta\) of the maximum. This is the formulation in Sections 1–3 of [Grötschel, Lovász, and Schrijver, *The ellipsoid method and its consequences in combinatorial optimization*](https://ir.cwi.nl/pub/10046/10046D.pdf).
Choose
\(\eta=\epsilon\sigma/(64G),\qquad \theta=2G\eta/\sigma=\epsilon/32.\)
Obtain a rational \(z\) with
\(\operatorname{dist}(z,K)\leq\eta,\qquad C(z)\geq V-\eta.\)
Because \(\eta<1/H\), this point lies in \(\Omega\). Lipschitz continuity gives \(g_j(z)\leq G\eta\). Set
\(\widehat z=(1-\theta)z+\theta z_0.\)
For every defining constraint, convexity yields
\(g_j(\widehat z)\leq(1-\theta)G\eta-\theta\sigma\leq-G\eta.\)
Thus \(\widehat z=(\widehat y,\widehat b,\widehat v)\) is exactly feasible and has positive seed coordinates. Also, since \(C(z_0)\geq0\) and \(V\leq2\),
\(C(\widehat z)\geq(1-\theta)(V-\eta)\geq V-2\theta-\eta\geq V-\epsilon.\)
To ensure a dyadic output even if intermediate rational denominators are arbitrary, let \(\mu_{\min}=\min_t\mu_t\). Choose a positive dyadic number \(h\) satisfying
\(h\leq\mu_{\min}\eta/(4n),\)
and return
\(x_t=h\left\lfloor\mu_t\widehat y_t/h\right\rfloor.\)
Rounding down preserves \(x_t\leq\mu_t\) and \(\sum_tx_t\leq\beta\). Put \(q_t=x_t/\mu_t\). Then
\(0\leq\widehat y_t-q_t<h/\mu_t\leq\eta/(4n).\)
Consequently, replacing \(\widehat y\) by \(q\) changes the full variable vector by Euclidean norm at most \(\eta/4\). The constraint margins and the Lipschitz bound imply that \((q,\widehat b,\widehat v)\) remains in \(K\).
The lower-box constraint margin gives \(\widehat y_t\geq G\eta\), so every rounded \(q_t\) is still strictly positive. The comparison lemma therefore applies, giving
\(W(x)\geq C(q,\widehat b,\widehat v)=C(\widehat z)\geq V-\epsilon\geq\sqrt{1-1/e}\,\mathrm{OPT}-\epsilon.\)
All precision parameters have polynomial encoding length: the logarithms of \(H\), \(1/\beta\), and \(1/\mu_{\min}\) are polynomially bounded by the input length. Hence optimization, repair, and rounding take time polynomial in \(m,\tau,L,\log(1/\epsilon)\), and therefore satisfy the requested polynomial bound.
Finally, \(\sqrt{1-1/e}\geq1-1/e\) and \(\mathrm{OPT}\geq0\), proving the requested guarantee for every instance.
⟨structured verdict parsed — rendered above⟩
The argument is correct in substance and resolves the target, with one minor omission in the separation-oracle interface. I found no false central step, major gap, or failing edge case. The stronger approximation guarantee follows once that routine detail is made explicit.
The definition \(B_{ts}=\mu_s\lambda_{st}\) correctly represents the recurrence, including asymmetric intensities and nonzero diagonal entries.
The fixed-point construction is valid:
The stronger comparison lemma is also correct. Strictly positive \(q\) ensures that all ratios \(b_t/a_t\) are defined. Coordinatewise concavity on the nonnegative orthant justifies
\[
F_q(ra)\leq rF_q(a)-(r-1)F_q(0).
\]
The extension outside the unit cube is explicitly stated and legitimate. At a maximizing coordinate, positivity of \(q_i\) makes the final inequality strict, yielding the claimed contradiction.
This lemma does not assume irreducibility or symmetry.
Every displayed constraint defining \(K\) is convex. The box constraints make the set bounded and closed. Its nonemptiness is subsequently established by the explicit interior point when \(\beta>0\); the zero triple is also feasible.
The objective bound \(V\leq2\) follows from the community masses summing to one.
For strictly positive \(y\), the comparison
\[
H_y(b)\leq F_y(b)
\]
has the correct direction because \(e^{-y_t}\geq1-y_t\). Thus feasibility supplies a subsolution for \(F_y\), and the comparison lemma yields \(b\leq a(y)\). The community constraints then imply \(W(x)\geq C(y,b,v)\).
The write-up correctly identifies the initialization problem at zero seeds and does not apply the comparison lemma there.
The inequality
\[
1-e^{-q_t}\geq(1-1/e)q_t
\]
holds throughout the required interval \(q_t\in[0,1]\).
Recomputing the derivative gives precisely
\[
f''(s)=-e^{-sh}\bigl(h^2(1-sq_t)+2hq_t\bigr).
\]
It is nonpositive for the stated ranges, including \(h=0\). Since \(f(0)=0\) and \(f(1)=a_t\), the scaling inequality follows.
Monotonicity in the seed argument then establishes feasibility of the proposed relaxation triple. Its community variables lie in the unit interval and satisfy their quadratic constraints with equality. Its objective is exactly \(\sqrt{1-1/e}\,W(x)\).
Taking the supremum is valid without assuming attainment of \(\mathrm{OPT}\).
The case \(\beta=0\) is handled correctly: the prescribed iteration stays zero regardless of \(B\).
For positive \(\beta\), all stated interior-point margins check out:
Thus the common margin \(\sigma=\beta/32\) is valid.
On \(\Omega\), the exponential argument satisfies \(y_t+(Bb)_t\geq-1\). The stated exponential, quadratic, and affine gradient bounds are valid, so \(G=8H\) is sufficient.
The proposed inner ball stays inside \(\Omega\); consequently the Lipschitz argument establishing its containment in \(K\) is valid. The outer radius \(n\) is sufficient.
Small masses and budgets affect logarithmic precision requirements, as claimed.
The approximate constraint and gradient calculations correctly produce either:
The interpolation used in the second branch is valid because the constraints are convex and the interior point has margin \(\sigma\).
The exponential evaluation discussion supports polynomial bit complexity: large nonnegative arguments can be truncated, and the remaining arguments admit polynomial precision evaluation. Gradient evaluation requires only polynomial additional precision for the rational coefficients.
The cited source defines weak optimization with the distance and additive objective guarantees used here, and its Theorem 3.1 supplies the separation-to-optimization implication under the known-ball assumptions. Those geometric assumptions have been established. [Grötschel–Lovász–Schrijver, Sections 1–3](https://ir.cwi.nl/pub/10046/10046D.pdf).
Minor issue — separating-vector normalization. The oracle returns an approximate gradient as its separating direction without explicitly normalizing it to the convention in the cited weak-separation definition. Its strict separation inequality is established, but that interface detail is omitted.
Minimum clarification: Specify the rational normalization used for the returned separating vector, verify the required norm condition, and note that its encoding length remains polynomial. This is routine bookkeeping, requiring no new mathematical argument.
The parameters satisfy \(\theta=\epsilon/32\) and \(\eta<1/H\), so the optimizer’s output lies in \(\Omega\).
Distance at most \(\eta\) from \(K\) implies \(g_j(z)\leq G\eta\). Mixing with \(z_0\) gives
\[
g_j(\widehat z)\leq-G\eta,
\]
with the correct sign and sufficient margin for every constraint.
The objective calculation is valid even though \(z\) is only approximately feasible. In particular,
\[
C(\widehat z)\geq V-2\theta-\eta\geq V-\epsilon.
\]
The final inequality has ample slack with the chosen constants.
Rounding down preserves the allocation bounds and budget. The seed-fraction error satisfies
\[
0\leq\widehat y_t-q_t<\frac{\eta}{4n},
\]
so the full-vector Euclidean displacement is at most \(\eta/4\). The existing constraint margins therefore preserve membership in \(K\).
The lower-box margin supplies \(\widehat y_t\geq G\eta\), which exceeds the rounding loss. Hence every rounded seed fraction remains strictly positive, and the comparison lemma applies.
A dyadic mesh meeting the stated bound can be selected with polynomial encoding length. The output coordinates consequently have polynomial encoding length.
The resulting stronger guarantee implies the requested one because \(\mathrm{OPT}\geq0\) and \(\sqrt{1-1/e}\geq1-1/e\).
⟨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.