Answer: Exactly solvable in deterministic polynomial time; therefore the requested \((1-1/e-\epsilon)\)-approximation is computable with success probability \(1\).
Corollary 1 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateAlgorithm 1 guarantees an approximation fac- tor of 1−1 e −ǫ for the IMA problem, where ǫ is any positive real number. The computational complexity of Algorithm 1 is O(B · |V | · g(|V |, |E| + B)), where g(|V |, |E| + B) is the com- plexity of computing an approximation ˜σ(A, S) of σ(A, S) in a graph with |V | nodes and |E| + B edges. More pre- cisely, it runs in B iterations, each of which requires es- timating the expected spread of O(|V |) node sets.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given types \(T\) with rational masses \(\mu_t\), seed types \(A\), baseline LTM predecessor probabilities \(p^0_{st}\), and explicit feasible integral link bundles \(\mathcal K_t\) with added probabilities \(\eta_s(K)\), choose fractions \(y_{tK}\) summing to \(1\) for each non-seed type, subject to the per-capita budget \(\sum_{t\notin A}\mu_t\sum_{K\in\mathcal K_t}y_{tK}|K|\le\beta\), to maximize activated mass. For each bundle, define activation by \(h_{tK}=\sum_{s\in A}(p^0_{st}+\eta_s(K))+\sum_{s\notin A}p^0_{st}\bar h_s\), with \(\bar h_s=\sum_K y_{sK}h_{sK}\) and seed activation equal to \(1\); use the least nonnegative solution. Is a \((1-1/e-\epsilon)\)-approximation computable in time polynomial in the number of types \(\tau\), the number of listed bundles \(\kappa\), input bit length \(L\), and \(1/\epsilon\), or does this model admit a stronger algorithm or a hardness classification?
A society is given by its support: a list \(T\) of \(\tau\) types with positive binary-rational masses \(\mu_t\), where \(\sum_{t\in T}\mu_t=1\); \(\tau\) is the support size, not the number of possible types. A nonempty proper subset \(A\subset T\) consists of seed types.
For each non-seed type \(t\), the input gives baseline predecessor probabilities \(p^0_{st}\ge0\), candidate new links \(C_t\subseteq A\times\{t\}\), and a fixed nonnegative rational weight \(q_{st}\) for each candidate link; candidate links are absent from the baseline. Require \(\sum_{s\in T}p^0_{st}+\sum_{(s,t)\in C_t}q_{st}\le1\), with unused probability representing no predecessor.
An explicitly listed family \(\mathcal K_t\subseteq2^{C_t}\) contains the empty bundle. Define \(\eta_s(K)=q_{st}\) when \((s,t)\in K\), and \(\eta_s(K)=0\) otherwise. Each link costs one unit. Write \(m=\sum_{t\notin A}|C_t|\), \(\kappa=\sum_{t\notin A}|\mathcal K_t|\), and let \(L\) be the total input bit length.
Given a binary-rational per-capita budget \(\beta>0\), choose fractions \(y_{tK}\ge0\) satisfying \(\sum_{K\in\mathcal K_t}y_{tK}=1\) and \(\sum_{t\notin A}\mu_t\sum_{K\in\mathcal K_t}y_{tK}|K|\le\beta\).
Set \(\bar h_s=1\) for seeds. For non-seeds, activation is defined by the least componentwise nonnegative solution of \(h_{tK}=\sum_{s\in A}(p^0_{st}+\eta_s(K))+\sum_{s\notin A}p^0_{st}\bar h_s\) and \(\bar h_t=\sum_{K\in\mathcal K_t}y_{tK}h_{tK}\). Maximize total activated mass \(F(y)=\sum_{s\in A}\mu_s+\sum_{t\notin A}\mu_t\bar h_t\).
For every rational \(0<\epsilon<1-1/e\), can a \((1-1/e-\epsilon)\)-approximation to this maximum be computed in time polynomial in \(m,\tau,\kappa,L,1/\epsilon\), allowing randomization with success probability at least \(2/3\), or is attaining this ratio NP-hard?
For finite directed networks under the Linear Threshold Model, adding unit-cost links from fixed seeds under a cardinality budget admits a sampling-based greedy \((1-1/e-\epsilon)\)-approximation. [Verified source](https://www.ijcai.org/proceedings/2019/0304.pdf)
No result settling this precise support-distribution model was located in the literature search.
The stated support-distribution problem is exactly solvable in deterministic polynomial time. Consequently, the requested \((1-1/e-\epsilon)\)-approximation is computable with success probability \(1\).
The proof uses the activation equations exactly as given. Their non-seed coefficient matrix is independent of the chosen bundle fractions. The main point requiring care is how to enforce the *least* nonnegative solution when that matrix has closed stochastic classes.
Write \(N=T\setminus A\), and define, for \(t,s\in N\),
\(B_{ts}=p^0_{st}\).
Thus \(B\) is nonnegative and substochastic: every row sum is at most \(1\). Define
\(a_t=\sum_{s\in A}p^0_{st},\qquad r_{tK}=\sum_{(s,t)\in K}q_{st},\qquad b_t(y)=a_t+\sum_{K\in\mathcal K_t}y_{tK}r_{tK}\).
Because the bundle fractions for each type sum to \(1\), averaging the prescribed equations gives
\(x=b(y)+Bx,\qquad x_t=\bar h_t\quad(t\in N).\)
Conversely, any nonnegative solution \(x\) of this averaged equation determines a solution of the original equations by setting
\(h_{tK}=a_t+r_{tK}+\sum_{s\in N}B_{ts}x_s.\)
These correspondences also preserve the least solution. Indeed, if \(x\le x'\) componentwise, nonnegativity of \(B\) implies that the corresponding bundle activation vectors satisfy \(h\le h'\).
For every permitted choice of bundle fractions, the probability restriction implies
\(0\le b_t(y)\le a_t+\sum_{(s,t)\in C_t}q_{st}\le 1-\sum_{s\in N}B_{ts}.\)
Consequently,
\(b(y)+B\mathbf 1\le\mathbf 1.\)
Starting with \(x^{(0)}=0\), define
\(x^{(j+1)}=b(y)+Bx^{(j)}.\)
Nonnegativity makes this sequence componentwise nondecreasing, and the preceding inequality bounds every iterate by \(\mathbf 1\). Its componentwise limit \(x^*(y)\) therefore exists and satisfies the averaged equation.
If \(z\ge0\) is any other solution, induction gives \(x^{(j)}\le z\) for every \(j\), so \(x^*(y)\le z\). Thus \(x^*(y)\) is precisely the least nonnegative solution, and
\(0\le x^*(y)\le\mathbf 1.\)
The iteration here proves existence and leastness; the polynomial-time algorithm below does not approximate activation by running this iteration.
Construct the dependency graph on \(N\), with an arc \(t\to s\) exactly when \(B_{ts}>0\). This orientation follows predecessor dependencies.
Let
\(D=\left\{t\in N:\sum_{s\in N}B_{ts}<1\right\}.\)
Let \(R\) consist of all vertices that can reach \(D\), allowing paths of length zero, and put \(U=N\setminus R\). These sets depend only on the baseline matrix.
For every \(t\in U\), its row sum in \(B\) equals \(1\): otherwise \(t\in D\subseteq R\).
Moreover, there is no dependency arc from \(U\) to \(R\), since such an arc would give its starting vertex a path to \(D\). Hence
\(B_{UR}=0.\)
For \(t\in U\), the input restriction gives
\(1+a_t+\sum_{(s,t)\in C_t}q_{st}\le1.\)
All summands after \(1\) are nonnegative, so \(a_t=0\) and every candidate weight into \(t\) is zero. Therefore \(b_U(y)=0\) for every \(y\).
The iteration from Section 2 consequently satisfies \(x_U^{(j)}=0\) for every \(j\). Taking its limit proves
\(x_U^*(y)=0.\)
When \(R\) is empty there is nothing to prove. Otherwise write \(Q=B_{RR}\).
Suppose \(z=Qz\) and \(z\ne0\), and let
\(M=\max_{t\in R}|z_t|>0.\)
At any vertex \(t\) attaining this maximum,
\(M=|z_t|\le\sum_{s\in R}Q_{ts}|z_s|\le M\sum_{s\in R}Q_{ts}\le M.\)
Equality throughout implies that the row sum of \(Q\) at \(t\) equals \(1\), and that every successor \(s\) with \(Q_{ts}>0\) also satisfies \(|z_s|=M\).
By the definition of \(R\), there is a positive-edge path from \(t\) to some \(d\in D\). Every vertex on this path belongs to \(R\), because it too can reach \(D\). Repeatedly applying the preceding implication yields \(|z_d|=M\).
But at \(d\),
\(\sum_{s\in R}Q_{ds}\le\sum_{s\in N}B_{ds}<1,\)
so the equation at \(d\) gives
\(M=|z_d|\le M\sum_{s\in R}Q_{ds}<M,\)
a contradiction. Thus the kernel of \(I-Q\) is zero, proving nonsingularity.
For each permitted \(y\), the equations
\(x=b(y)+Bx,\qquad x_U=0\)
have exactly one solution. Indeed, their restriction to \(R\) is
\((I-B_{RR})x_R=b_R(y),\)
which has a unique solution by Lemma 2. Lemma 1 shows that the least solution satisfies these equations, so their unique solution is exactly \(x^*(y)\).
In particular, activation is affine in \(y\), even when \(I-B\) itself is singular.
Introduce variables \(y_{tK}\) and \(x_t\). Maximize
\(\sum_{s\in A}\mu_s+\sum_{t\in N}\mu_t x_t\)
subject to the following linear constraints:
Every feasible allocation in the original problem extends to a feasible point of this linear program: take its least activation vector, whose bounds and vanishing coordinates were proved above.
Every feasible point of this linear program represents the original activation correctly: its allocation satisfies the original bundle and budget constraints, and Section 3 proves that its activation vector must equal the least solution.
The objective is therefore exactly \(F(y)\) in both directions. This is an exact formulation.
The zero constraints on \(U\) are essential. For example, a closed baseline cycle with row sums \(1\) and no seed input admits constant positive fixed points, although its least nonnegative solution is zero.
The dependency graph has at most \(\tau\) vertices and \(\tau^2\) arcs. Exact rational row-sum comparisons and graph reachability compute \(D\), \(R\), and \(U\) in polynomial time.
The linear program has \(\kappa+|N|\) variables and \(O(\kappa+\tau)\) constraints. Its coefficients are obtained from input rationals by sums and products, together with bundle cardinalities bounded by \(m\). Because bundles are explicitly listed, constructing all coefficients requires polynomial time in \(m,\tau,\kappa,L\). Their total encoding length is also polynomial in these parameters.
We apply the standard rational linear-programming theorem: a feasible rational linear program with finite optimum admits an exact rational optimal solution computable in deterministic time polynomial in its encoding length. Polynomial-time solution and polynomial-size exact optimal solutions are covered in [Goemans’s linear-programming notes](https://ocw.mit.edu/courses/6-854j-advanced-algorithms-fall-2008/908fe54d659623efadda2d033b895caf_notes_lp.pdf).
Its hypotheses hold here:
Thus the algorithm returns an exact optimal allocation \(y^{\mathrm{opt}}\) in time polynomial in \(m,\tau,\kappa,L\). For every allowed \(\epsilon\),
\(F(y^{\mathrm{opt}})=\operatorname{OPT}\ge(1-1/e-\epsilon)\operatorname{OPT}.\)
The running time is independent of \(\epsilon\), and hence satisfies the requested polynomial bound in \(1/\epsilon\) as well. Randomization is unnecessary.
⟨structured verdict parsed — rendered above⟩
The argument is sound under the intended rational-input interpretation. It establishes an exact deterministic polynomial-time algorithm, with one minor clarification needed about the encoding of baseline probabilities.
The prover addresses the actual support-distribution model: it optimizes the fractions \(y_{tK}\) over explicitly listed bundles, uses the per-capita budget, and respects the prescribed least nonnegative activation solution. It does not rely on transferring the finite-network approximation theorem.
Minor issue: The task explicitly specifies rational masses, candidate weights, and budget, but does not explicitly specify that the baseline probabilities \(p^0_{st}\) are rational. Section 5 assumes this when asserting that all LP coefficients are rational and that exact comparisons take polynomial time.
Under the evidently intended interpretation that all numerical inputs have ordinary binary rational encodings counted in \(L\), this is an expositional clarification. The prover should state that interpretation explicitly. An unspecified representation of arbitrary real baseline probabilities would not support the stated bit-complexity conclusion.
The definition \(B_{ts}=p^0_{st}\) uses the correct orientation: row \(t\) contains the predecessor probabilities affecting type \(t\).
The averaged equation
\[
x=b(y)+Bx
\]
follows correctly from the bundle normalization. The baseline seed contribution and the baseline non-seed contribution are independent of the bundle, while the candidate contribution averages to the stated term.
The converse construction of \(h_{tK}\) is also correct: substituting the constructed values into the bundle average recovers \(x_t\) using the averaged equation.
The least-solution correspondence is justified. Every nonnegative original solution yields a nonnegative averaged solution, and the displayed reconstruction is componentwise monotone in \(x\). Thus the least averaged solution reconstructs a solution no larger than any other original solution. This remains valid for bundles assigned fraction zero, since their individual activation equations are still included.
The bound
\[
0\le b_t(y)\le 1-\sum_{s\in N}B_{ts}
\]
is correct. Each bundle is a subset of the candidate links, all weights are nonnegative, and the fractions form a convex combination.
Consequently, the iteration starting at zero is componentwise nondecreasing and bounded above by the all-ones vector. Since the dimension is finite, its componentwise limit exists; passing to the limit through the finite matrix sums yields a fixed point.
The induction comparing every iterate with any nonnegative fixed point proves leastness. The bound \(0\le x^*(y)\le\mathbf 1\) therefore holds for every permitted allocation.
No convergence-rate claim is needed: the prover explicitly uses iteration only to establish existence and leastness.
All steps are valid:
Therefore \(x_U^*(y)=0\) is proved uniformly over all allocations. Zero-weight candidate links cause no exception.
The maximum-absolute-coordinate argument correctly proves nonsingularity.
At a coordinate attaining \(M>0\), the inequalities can all be equal only if the corresponding row sum of \(Q\) is one and every positive-weight successor also attains absolute value \(M\).
Every vertex in \(R\) has a positive-edge path to \(D\), and every vertex along that path remains in \(R\). The equality implication therefore propagates along the path. At its endpoint, the strictly deficient row gives the stated contradiction.
The argument also covers a path of length zero. The empty-\(R\) case is explicitly handled.
With \(x_U=0\), the equations on \(R\) have a unique solution by Lemma 2. The equations on \(U\) are satisfied because \(b_U(y)=0\) and \(B_{UR}=0\). Lemma 1 identifies this unique solution with the least activation vector.
Both directions of the LP correspondence are therefore proved:
The objectives agree exactly. The bounds on \(x\) do not exclude any original allocation.
The closed-cycle example correctly explains why fixed-point equations and activation bounds alone would not enforce leastness.
Subject to the rational-input clarification, the complexity claims are valid.
The graph has at most \(\tau^2\) arcs, and exact row-sum comparisons and reachability are polynomial-time operations. Explicit bundle listing makes the required cardinalities and weight sums computable in polynomial time.
The variable and constraint counts are correct. Rational sums and the products appearing in budget coefficients have polynomial encoding length; no matrix inverse is explicitly required by the algorithm.
The stated rational LP theorem is applicable. The empty-bundle allocation proves feasibility, the simplex and activation bounds make the feasible region compact, and the objective is finite. The cited [Goemans notes](https://ocw.mit.edu/courses/6-854j-advanced-algorithms-fall-2008/908fe54d659623efadda2d033b895caf_notes_lp.pdf) cover rational input encoding, polynomial-size exact vertex solutions, and polynomial-time linear programming.
The proof does not assume an interior of positive dimension, so equality constraints and degenerate feasible regions create no additional gap.
An exact optimum satisfies the requested approximation inequality because the objective is nonnegative and the requested factor lies strictly between zero and one. Determinism gives success probability one. Independence from \(\epsilon\) satisfies the requested runtime dependence.
The only necessary clarification is to state that baseline probabilities are binary-encoded rationals whose encoding lengths are included in \(L\). No additional activation lemma or optimization 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.