Answer: A deterministic algorithm achieves \((1-1/e-\varepsilon)\mathrm{OPT}\) in time polynomial in \(m,\tau,L,1/\varepsilon\), with only logarithmic dependence on \(1/\kappa\). Additive approximation is NP-hard even for \(m=1\) and \(\kappa=1/4\); a randomized polynomial-time solver would imply \(\mathrm{NP}=\mathrm{RP}\).
Theorem 4.6 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateOn the foundation of ABRIS framework, assume that the number of RR sets in the attribute-based hypergraph satisfies Eq.(6) with the accuracy criterion αni at the precision parameter ϵ ∈(0, 1). For the special multi-objective optimization problem with F = {E[Iψi(·)]} and T = {αni}, where |F ′| = |F| = |Ψ| = o(k/ log3 k), if using F ′ = {ˆIψi(·)} to estimate F, the MWU method at precision parameter λ returns an (ω(1 −1/e)2 −λ −ϵ)- approximate solution with probability 1 −1/ mini{ni}.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite type set \(T\), positive rational masses \(\mu_t\) summing to \(1\), group memberships \(a_{tj}\), a nonnegative rational type-mixing kernel \(K\), a rational seed-mass budget \(\kappa\), and tolerance \(\varepsilon>0\), choose \(x_t\in[0,\mu_t]\) with \(\sum_t x_t\le\kappa\). Define \(q^{(0)}=x\) and \(q_u^{(r+1)}=x_u+(\mu_u-x_u)(1-\exp(-\sum_t K_{tu}q_t^{(r)}))\), and let \(q(x)\) be its limit. For each group \(j\), let \(\mu_j=\sum_t a_{tj}\mu_t>0\) and \(Q_j(x)=\sum_t a_{tj}q_t(x)\). Compute a feasible \(x\) whose value \(\rho(x)=\min_j Q_j(x)/\mu_j\) is within \(\varepsilon\) of the maximum feasible value.
A society is given by its support: a list \(T\) of \(\tau\ge1\) types with positive binary rational masses \(\mu_t\), summing to \(1\); \(\tau\) counts supported types, not possible types or agents.
There are \(m\ge1\) possibly overlapping groups, with memberships \(a_{tj}\in\{0,1\}\); every type belongs to at least one group and \(\mu_j=\sum_t a_{tj}\mu_t>0\).
Inputs also include \(K\in\mathbb Q_{\ge0}^{\tau\times\tau}\), a seed-mass budget \(\kappa\in\mathbb Q\cap(0,1]\), and rational tolerance \(\varepsilon\in(0,1)\). Let \(L\) be the total binary input length.
A feasible seed allocation satisfies \(0\le x_t\le\mu_t\) and \(\sum_t x_t\le\kappa\). Define \(q^{(0)}=x\) and \(q_u^{(r+1)}=x_u+(\mu_u-x_u)(1-\exp(-\sum_t K_{tu}q_t^{(r)}))\).
Use the coordinatewise limit \(q(x)=\lim_{r\to\infty}q^{(r)}\), selecting the least fixed point above \(x\). Set \(\rho(x)=\min_{1\le j\le m}\sum_t a_{tj}q_t(x)/\mu_j\) and \(\mathrm{OPT}=\sup_{x\text{ feasible}}\rho(x)\).
The additive approximation problem is to compute a feasible rational allocation \(x\) with \(\rho(x)\ge\mathrm{OPT}-\varepsilon\).
Can a polynomial-time algorithm attain \(\rho(x)\ge((1-1/e)^2-\varepsilon)\mathrm{OPT}\), or is attaining this guarantee NP-hard?
Does the additive approximation problem admit an algorithm polynomial in \(m,\tau,L,1/\varepsilon\), or is it NP-hard? Randomized algorithms with success probability at least \(2/3\) are allowed; state any further dependence on \(\kappa\).
For discrete independent-cascade diffusion, attribute-based reverse-reachable sampling combined with multiplicative-weight updates guarantees simultaneous group-target approximation \(\omega(1-1/e)^2-\lambda-\delta\), with probability at least \(1-1/\min_j n_j\), given sufficient samples and \(m=o(k/\log^3 k)\); here \(k\) is the seed count, \(n_j\) the group size, \(\lambda,\delta>0\) accuracy parameters, and \(\omega\to1\) asymptotically. [Lin et al.](https://doi.org/10.1613/JAIR.1.14450)
For general discrete monotone submodular objectives, an asymptotic \((1-1/e)^2-\delta\) approximation is also established under that group-count condition. [Udwani](https://pubsonline.informs.org/doi/10.1287/ijoo.2019.0041) No result settling this specific mass recurrence was identified in the search.
The multiplicative guarantee is attainable in polynomial time. In fact, a deterministic algorithm achieves the stronger guarantee \( \rho(x)\ge (1-1/e-\varepsilon)\mathrm{OPT} \), in time polynomial in \(m,\tau,L,1/\varepsilon\). There is no additional polynomial dependence on \(1/\kappa\); only \(\log(1/\kappa)\), already included in \(L\), is needed.
The additive approximation problem is NP-hard, even with \(m=1\), \(\kappa=1/4\), and contractive diffusion. A randomized algorithm with the requested polynomial running time and success probability would imply \(\mathrm{NP}=\mathrm{RP}\).
The proofs below concern the given mass recurrence directly. They do not require the group-count condition in the discrete results.
Write \(F_x(q)\) for the recurrence map:
\( \displaystyle (F_x(q))_u=x_u+(\mu_u-x_u)\left(1-\exp\left(-\sum_tK_{tu}q_t\right)\right). \)
On the box \(0\le q\le\mu\), this map is coordinatewise nondecreasing and satisfies \(x\le F_x(q)\le\mu\). Consequently, iteration from \(x\) increases to a fixed point. Every fixed point dominates every iterate, so this is the least fixed point.
Set \(p_t=x_t/\mu_t\). Consider the following random rooted tree, with a specified root type \(u\):
Every finite-depth tree is finite almost surely. The probability that the root’s depth-\(r\) tree contains a marked vertex is \(q_u^{(r)}/\mu_u\). Indeed, the depth-zero probability is \(p_u\), and Poisson thinning gives precisely the stated recurrence.
It follows that
\( \displaystyle \frac{q_u(x)}{\mu_u}=\Pr(\text{some vertex of the full tree is marked}). \)
For a finite tree having \(N_t\) vertices of type \(t\), its conditional marking probability is
\( \displaystyle H_N(p)=1-\prod_t(1-p_t)^{N_t}. \)
Thus finite-depth adoption functions are averages of these functions, and the infinite-depth functions are their increasing limits.
Two consequences will be used:
\( \displaystyle q_u(\lambda x)\ge\lambda q_u(x). \)
For the second assertion, \(H_N(\lambda p)\) is concave as a function of \(\lambda\), and vanishes at zero. Apply its concavity inequality, average over finite trees, and then take the increasing depth limit. This argument also applies when some seed coordinates vanish.
We first establish the numerical fact needed by the approximation algorithm.
Lemma. If \(x\) is rational and \(0<x_t\le\mu_t\) for every type, then \(q(x)\), and its first derivatives with respect to rationally scaled seed coordinates, can be approximated to absolute error \(h>0\) in time polynomial in the input length and \(\log(1/h)\).
For positive \(x\), the fixed point is unique.
Suppose \(q,r\) are fixed points and \(\lambda=\max_u q_u/r_u>1\). Concavity of \(F_x\), together with \(F_x(0)=x\), gives
\( \displaystyle F_x(\lambda r)\le\lambda F_x(r)-(\lambda-1)x. \)
Monotonicity and \(q\le\lambda r\) then imply
\( \displaystyle q=F_x(q)\le\lambda r-(\lambda-1)x. \)
This contradicts equality \(q_u=\lambda r_u\) at a coordinate attaining the maximum ratio. If two fixed points differ, one of the two orders of comparison has a maximum ratio exceeding one. Hence they must coincide.
Define
\( \displaystyle C_x=\{w:0\le w\le\mu,\ w\le F_x(w)\}. \)
This is convex because every coordinate of \(F_x(w)-w\) is concave.
Every \(w\in C_x\) satisfies \(w\le q(x)\): iteration from \(w\) increases to a fixed point, which is unique. Since \(q(x)\in C_x\), it is the coordinatewise maximum of \(C_x\). Therefore it is the unique maximizer of
\( \displaystyle \max_{w\in C_x}\sum_u w_u. \)
This convex optimization problem is well bounded with explicitly controlled binary parameters. Let
\( \displaystyle x_{\min}=\min_t x_t,\qquad M=\max\{1,\max_{t,u}K_{tu}\}. \)
At \(w=x/2\), every inequality \(F_x(w)-w\ge0\) has slack at least \(x_{\min}/2\). On the population box, each constraint has gradient norm at most \(\tau M+1\) in the sum norm. Thus a Euclidean ball centered at \(x/2\), of radius
\( \displaystyle r=\frac{x_{\min}}{8(\tau M+1)}, \)
lies in \(C_x\). The set lies in a ball of radius \(2\tau\) about that center. Both radii have polynomial binary description length.
There is also a polynomial-time weak separation oracle. Box violations have exact separating hyperplanes. Inside the box, the concave constraints and their gradients can be evaluated to arbitrary binary precision. If all constraint violations are at most \(d\), mixing the query point with \(x/2\) produces a feasible point at distance at most \(2d\sqrt{\tau}/x_{\min}\). Otherwise, a sufficiently accurate tangent hyperplane separates the query point from \(C_x\).
Here exponential evaluation requires only polynomial time in the requested precision and argument length: sufficiently large positive arguments can be truncated, while the remaining arguments have magnitude bounded by the precision requirement.
The weak separation-to-optimization theorem for a convex body with known inner and outer balls now applies. It produces a rational \(y\) within distance \(\gamma\) of \(C_x\), with objective value at least its optimum minus \(\gamma\), in time polynomial in the dimension, binary radii, and \(\log(1/\gamma)\). This is the standard ellipsoid theorem of [Grötschel, Lovász, and Schrijver](https://www.zib.de/userpage/groetschel/pubnew/paper/groetschellovaszschrijver1981a.pdf).
Because every point of \(C_x\) lies coordinatewise below \(q(x)\), the returned point satisfies
\( \displaystyle \|y-q(x)\|_1\le(2\tau+1)\gamma. \)
Indeed, its positive coordinate errors total at most \(\tau\gamma\), and its objective deficit is at most \(\gamma\). Thus the convex optimization computes \(q(x)\) to any requested absolute precision with polynomial bit complexity.
Let \(J\) be the Jacobian of \(F_x\) with respect to \(q\), evaluated at the fixed point. Writing \(H_u=\sum_tK_{tu}q_t\),
\( \displaystyle J_{ut}=(\mu_u-x_u)e^{-H_u}K_{tu}. \)
The inequality \(H_ue^{-H_u}\le1-e^{-H_u}\) implies
\( \displaystyle Jq\le q-x. \)
Put \(p_{\min}=\min_u x_u/\mu_u>0\). Since \(q\le\mu\),
\( \displaystyle Jq\le(1-p_{\min})q. \)
In the weighted maximum norm \(\|v\|_q=\max_u|v_u|/q_u\), the operator norm of \(J\) is therefore at most \(1-p_{\min}\). In particular, \(I-J\) is invertible, and
\( \displaystyle \|(I-J)^{-1}\|_\infty\le\frac{1}{x_{\min}p_{\min}}. \)
For scaled coordinates \(x_t=b_tz_t\), implicit differentiation gives
\( \displaystyle \frac{\partial q}{\partial z}=(I-J)^{-1}\operatorname{diag}(e^{-H_u})\operatorname{diag}(b_t). \)
All required conditioning parameters enter through their logarithms. More explicitly, a fixed-point error \(\zeta\) changes \(J\) by at most \(\tau^2M^2\zeta\) in maximum row-sum norm. Choosing this below half the inverse-norm bound ensures that matrix inversion remains stable. The resulting derivative error is bounded by an explicit expression polynomial in \(M,\tau,1/x_{\min},1/p_{\min}\), times \(\zeta\).
Accordingly, only a polynomial number of precision bits is needed. Group normalization similarly requires \(\log(1/\mu_j)\) precision bits. This proves the lemma.
Define
\( \displaystyle b_t=\min\{\mu_t,\kappa\},\qquad c_t=\frac{b_t}{\mu_t},\qquad x_t=b_tz_t. \)
Every feasible allocation corresponds exactly to a point in
\( \displaystyle P=\{z\in[0,1]^\tau:\sum_tb_tz_t\le\kappa\}. \)
For group \(j\), let
\( \displaystyle f_j(z)=\frac{\sum_ta_{tj}q_t(bz)}{\mu_j}. \)
Fix \(s>0\) and restrict attention to \(z_t\ge s\). Then \(p_t=c_tz_t\ge sc_t\).
For a finite tree, write \(S=\sum_tN_tp_t\). Differentiating its conditional marking probability with respect to \(z_i\), and deleting the corresponding factor from the product, gives
\( \displaystyle 0\le\partial_iH_N\le\frac{e}{s}Se^{-S}. \)
For a second derivative, deleting two factors gives
\( \displaystyle |\partial_{ij}H_N|\le\frac{e^2}{s^2}S^2e^{-S}. \)
Also \(H_N\ge1-e^{-S}\). Using
\( \displaystyle \frac{S}{e^S-1}\le1,\qquad \frac{S^2}{e^S-1}\le2, \)
and \(\max_{S\ge0}Se^{-S}=1/e\), we obtain
\( \displaystyle 0\le\partial_iH_N\le\min\{1/s,(e/s)H_N\}, \)
\( \displaystyle -\frac{2e^2}{s^2}H_N\le\partial_{ij}H_N\le0. \)
These bounds pass to the full-tree expectation. To justify differentiation, couple all depths within the same full tree. On a finite full tree, the derivatives eventually stabilize. On an infinite tree, \(S\) tends to infinity because every marking probability is positive, so the derivatives tend to zero. Uniform bounds on a neighborhood allow dominated convergence and differentiation under the expectation.
Group functions are convex combinations of root-type adoption probabilities, with weights \(a_{tj}\mu_t/\mu_j\). Hence
\( \displaystyle 0\le\partial_if_j(z)\le\min\{1/s,(e/s)f_j(z)\}, \)
\( \displaystyle -\frac{2e^2}{s^2}f_j(z)\le\partial_{ij}f_j(z)\le0. \)
The essential point is that these bounds contain no inverse power of \(\kappa\).
Let \(c=1-1/e\), and choose
\( \displaystyle \eta=\varepsilon/32,\qquad s=\eta/\tau,\qquad z^0=s\mathbf1,\qquad D=(1-\eta)P. \)
The baseline has seed mass at most \(\eta\kappa\). Any path obtained by starting at \(z^0\) and integrating directions in \(D\) for total time one remains feasible: its budget is at most \(\kappa\), and each coordinate is at most \(s+1-\eta\le1\).
Define the benchmark
\( \displaystyle B=\max_{y\in P}\min_j f_j(z^0+(1-\eta)y). \)
The maximum exists because positive baseline seeding makes the objective continuous on this compact set. Monotonicity and the scaling inequality from Section 1 give
\( \displaystyle B\ge(1-\eta)\mathrm{OPT}. \)
Furthermore, the proportional allocation \(x_t=\kappa\mu_t\) gives every group adoption at least \(\kappa\), so \(\mathrm{OPT}\ge\kappa\).
If \(z\ge z^0\), diminishing partial derivatives imply
\( \displaystyle f_j(z^0+v)-f_j(z)\le\nabla f_j(z)\cdot v\qquad(v\in D). \)
For verification, take the coordinatewise maximum \(w=z\vee(z^0+v)\). Monotonicity bounds the left side by \(f_j(w)-f_j(z)\). Along the segment from \(z\) to \(w\), the gradient can only decrease, and \(0\le w-z\le v\).
Consequently, for every target \(\beta\le B\), there exists one direction \(v\in D\) satisfying simultaneously
\( \displaystyle \nabla f_j(z)\cdot v\ge\beta-f_j(z)\quad\text{for every }j. \)
Take \(v=(1-\eta)y\) from a benchmark optimizer.
For each target \(\beta\), put \(h=\eta\beta\) and
\( \displaystyle C_0=32\tau^2/s^2,\qquad N=\lceil C_0/\eta\rceil. \)
Starting at \(z^0\), perform \(N\) steps. At a step, approximate every group value with error at most \(h\), and every group gradient with sum-norm error at most \(h\). Denote these approximations by \(\widetilde f_j,\widetilde g_j\).
Call a group active when \(\widetilde f_j<\beta\). Solve the rational linear feasibility problem
\( \displaystyle v\in D,\qquad \widetilde g_j\cdot v\ge\beta-\widetilde f_j-2h\quad\text{for active }j. \)
If it is infeasible, abort this target. If \(\beta\le B\), the direction established above is feasible, even after the oracle errors, so the run cannot abort.
Round the returned direction downward to a fixed binary grid fine enough that its true gradient inner products decrease by at most \(h\). The bound \(\partial_if_j\le1/s\) ensures that grid spacing at most \(sh/\tau\) suffices. Downward rounding preserves membership in \(D\). Update \(z\) by \(v/N\).
For an active group, the rounded direction satisfies
\( \displaystyle \nabla f_j(z)\cdot v\ge\beta-f_j(z)-5h. \)
For an inactive group, its true value is already at least \(\beta-h\) and cannot decrease.
All allocations remain rational with polynomial description length: directions use a fixed binary grid, and updates use the common denominator \(N\).
For an active group, \(f_j(z)\le\beta+h\). Along its step, concavity in the nonnegative direction and the relative gradient bound give
\( \displaystyle f_j(z+t v)\le f_j(z)\left(1+\frac{e\tau}{sN}\right)\le4\beta\qquad(0\le t\le1/N). \)
The chosen \(N\) ensures the last inequality. The Hessian bound therefore gives the Taylor estimate
\( \displaystyle f_j(z+v/N)\ge f_j(z)+\frac{\beta-f_j(z)-5h}{N}-\frac{C_0\beta}{N^2}. \)
Let \(d_\ell=\max\{0,\beta-f_j(z^\ell)\}\). For an active group,
\( \displaystyle d_{\ell+1}\le(1-1/N)d_\ell+5h/N+C_0\beta/N^2. \)
For an inactive group, \(d_{\ell+1}\le h\). Both cases are bounded inductively by
\( \displaystyle d_\ell\le(1-1/N)^\ell\beta+(5h+C_0\beta/N)\bigl(1-(1-1/N)^\ell\bigr). \)
Since \(C_0/N\le\eta\) and \((1-1/N)^N\le e^{-1}\), every completed run satisfies
\( \displaystyle \min_jf_j(z^N)\ge(c-6\eta)\beta. \)
Run this procedure for geometric targets
\( \displaystyle \beta_\ell=(\kappa/2)(1+\eta)^\ell\le1, \)
and return the allocation from the largest completed target.
There are \(O(\eta^{-1}\log(2/\kappa))\) targets. Since \(B\ge(1-\eta)\kappa>\kappa/2\), a target immediately below \(B\) completes and is at least \(B/(1+\eta)\). Therefore
\( \displaystyle \rho(x)\ge\frac{(c-6\eta)(1-\eta)}{1+\eta}\mathrm{OPT}\ge(c-8\eta)\mathrm{OPT}\ge(c-\varepsilon)\mathrm{OPT}. \)
The step count is polynomial in \(\tau,1/\varepsilon\). The oracle precision requirements depend on \(\log(1/h)\). At every query,
\( \displaystyle \frac{x_t}{\mu_t}\ge sc_t\ge s\kappa. \)
Thus Section 2’s conditioning requires only \(O(L+\log(1/\varepsilon)+\log\tau)\) precision bits, apart from polynomial factors. The target count and all rational arithmetic also have polynomial complexity.
This proves the claimed running time polynomial in \(m,\tau,L,1/\varepsilon\). Since \(c>c^2\), it establishes the requested \(((1-1/e)^2-\varepsilon)\mathrm{OPT}\) guarantee.
We give a polynomial reduction from CLIQUE.
Start with a graph on \(n\) vertices and a target \(2\le k\le n\). Let \(N\) be the smallest power of two at least \(2n\). Add \(N-n\) mutually adjacent universal vertices, obtaining a graph \(G\). Write
\( \displaystyle r=N-n+k,\qquad \omega=\omega(G). \)
Then the original instance is a yes-instance exactly when \(\omega\ge r\), and always \(\omega\ge N/2\).
Create \(N\) vertex types and one sink type. Give each vertex type mass \(1/(2N)\), and the sink mass \(1/2\). There is one group containing every type, and
\( \displaystyle \kappa=1/4. \)
These masses are dyadic rationals.
Let \(A_G\) be the adjacency matrix and define
\( \displaystyle B=\mathbf1\mathbf1^{\mathsf T}-A_G. \)
For every nonnegative vector \(z\), with \(s=\sum_i z_i\),
\( \displaystyle z^{\mathsf T}Bz\ge s^2/\omega. \)
Here is a proof. Normalize to \(\sum_i y_i=1\). If two supported vertices are nonadjacent, moving their combined weight entirely to one of them can only increase \(y^{\mathsf T}A_Gy\): with their sum fixed, that expression is affine in the split. Repeating this operation leaves support on a clique.
On a clique of size \(\ell\le\omega\),
\( \displaystyle y^{\mathsf T}A_Gy=1-\sum_i y_i^2\le1-1/\ell\le1-1/\omega. \)
Therefore \(y^{\mathsf T}By\ge1/\omega\). Equality is attained by uniform weight on a maximum clique.
Let \(d_i=\sum_jB_{ij}\). Define a nonnegative matrix \(C\) by
\( \displaystyle C_{ij}=B_{ij},\qquad C_{i,\mathrm{sink}}=2-d_i/N,\qquad C_{\mathrm{sink},u}=0. \)
All entries lie between zero and two. Every vertex row has weighted sum
\( \displaystyle \sum_u\mu_uC_{iu}=d_i/(2N)+\tfrac12(2-d_i/N)=1. \)
Set
\( \displaystyle K=\alpha C,\qquad \alpha=\frac{1}{1024N^2}. \)
The recurrence is contractive in the sum norm: its Jacobian’s column sums are at most \(\alpha\sum_u\mu_uC_{tu}\le\alpha<1\).
For any feasible allocation \(x\), let \(q=q(x)\) and \(H_u=\sum_tC_{tu}q_t\). Since \(C_{tu}\le2\) and \(\sum_tq_t\le1\), we have \(H_u\le2\).
Using \(0\le z-(1-e^{-z})\le z^2/2\),
\( \displaystyle q=x+\alpha\operatorname{diag}(\mu-x)C^{\mathsf T}q+e,\qquad \|e\|_1\le2\alpha^2. \)
Furthermore,
\( \displaystyle \|q-x\|_1\le\alpha\sum_tq_t\sum_u\mu_uC_{tu}\le\alpha, \)
and the sum-norm operator bound for \(\operatorname{diag}(\mu-x)C^{\mathsf T}\) is at most one. Consequently,
\( \displaystyle \left\|q-x-\alpha\operatorname{diag}(\mu-x)C^{\mathsf T}x\right\|_1\le3\alpha^2. \)
Write \(z\) for the vertex seed coordinates, \(x_{\mathrm{sink}}\) for the sink seed, and \(s=\sum_i z_i\). Define the rational expression
\( \displaystyle A(x)=\sum_t x_t+\alpha\left(s-z^{\mathsf T}Bz-x_{\mathrm{sink}}\sum_iC_{i,\mathrm{sink}}z_i\right). \)
Because the single group has mass one, the preceding estimate says
\( \displaystyle |\rho(x)-A(x)|\le3\alpha^2. \)
The graph identity and feasibility give
\( \displaystyle A(x)\le\kappa+\alpha(s-s^2/\omega)\le\kappa+\alpha(\kappa-\kappa^2/\omega). \)
The last inequality holds because \(s\mapsto s-s^2/\omega\) increases on \(0\le s\le\kappa=1/4\).
Equality is attained by putting no seed in the sink and distributing total seed mass \(\kappa\) uniformly over a maximum clique. This allocation respects the type caps because \(\omega\ge N/2\). Hence, defining
\( \displaystyle U_\ell=\kappa+\alpha(\kappa-\kappa^2/\ell), \)
we have
\( \displaystyle U_\omega-3\alpha^2\le\mathrm{OPT}\le U_\omega+3\alpha^2. \)
Request additive tolerance
\( \displaystyle \varepsilon_{\mathrm{add}}=\frac{\alpha}{128N^2}. \)
Its inverse is polynomial in \(N\). The consecutive clique gap satisfies
\( \displaystyle U_r-U_{r-1}=\frac{\alpha}{16r(r-1)}\ge\frac{\alpha}{16N^2}. \)
If the CLIQUE instance is a yes-instance, a successful additive solver returns
\( \displaystyle A(x)\ge\rho(x)-3\alpha^2\ge U_r-6\alpha^2-\varepsilon_{\mathrm{add}}>U_{r-1}. \)
The strict inequality follows from
\( \displaystyle 6\alpha^2+\varepsilon_{\mathrm{add}}=\frac{\alpha}{N^2}\left(\frac6{1024}+\frac1{128}\right)<\frac{\alpha}{16N^2}. \)
If the instance is a no-instance, then \(\omega\le r-1\), and every feasible allocation satisfies
\( \displaystyle A(x)\le U_\omega\le U_{r-1}. \)
Thus the exact rational test \(A(x)>U_{r-1}\) distinguishes the instances whenever the approximation succeeds. No evaluation of exponentials is required for this test.
The construction has polynomial input length, \(m=1\), and the fixed budget \(\kappa=1/4\). Therefore a deterministic algorithm polynomial in \(m,\tau,L,1/\varepsilon\) would imply \(\mathrm{P}=\mathrm{NP}\).
For a randomized solver, reject any infeasible output and otherwise apply the rational test. No no-instance can be accepted, while yes-instances are accepted with probability at least \(2/3\). This places CLIQUE in \(\mathrm{RP}\), implying \(\mathrm{NP}=\mathrm{RP}\).
⟨structured verdict parsed — rendered above⟩
The output is sound in substance, with minor gaps in its numerical implementation details. The multiplicative approximation argument and the additive hardness reduction address the assigned continuous recurrence directly. I found no major mathematical gap or false central step.
The claimed deterministic multiplicative guarantee is stronger than the requested guarantee. The additive hardness argument also establishes the stated randomized consequence. The remaining clarifications concern oracle tolerances, a reciprocal in the matrix-conditioning argument, and derivatives at boundary coordinates.
Step-by-step verification
The recurrence preserves the population box and is coordinatewise monotone. Starting from \(x\), its iterates increase and remain bounded by \(\mu\). Continuity therefore makes the coordinatewise limit a fixed point. Induction shows that every fixed point in the population box dominates every iterate.
The branching construction has the correct orientation: children of type \(t\) at a parent of type \(u\) have mean \(\mu_tK_{tu}\). Poisson thinning consequently produces the exponent \(\sum_tK_{tu}q_t^{(r)}\). The depth-zero marking probability is \(x_u/\mu_u\), as required.
Passing to the full tree uses increasing events, so it selects exactly the prescribed least fixed point. It does not silently substitute another fixed point in a supercritical instance.
The finite-tree marking polynomials have nonnegative first derivatives and nonpositive second derivatives, including diagonal derivatives. The scaling inequality follows from their concavity along nonnegative rays and survives the increasing depth limit, including when seed coordinates vanish.
Positive seeds ensure that all fixed-point coordinates are positive, making the ratio comparison legitimate. The extrapolated concavity inequality has the correct direction and strict positive-seed term. At a coordinate attaining the maximum ratio, the resulting inequality contradicts equality.
Although the comparison evaluates \(F_x\) outside the population box, its displayed exponential formula remains monotone and concave on the nonnegative orthant. Thus this use introduces no substantive domain problem.
Each constraint \(F_x(w)_u-w_u\ge0\) defines a convex superlevel set. Iteration from a feasible \(w\) increases to the unique fixed point, so every point of \(C_x\) lies coordinatewise below \(q(x)\). Hence maximizing the coordinate sum indeed singles out \(q(x)\).
The proposed center \(x/2\) has the stated nonlinear-constraint slack. Its distances from both population-box boundaries are at least \(x_{\min}/2\). The gradient bound and radius therefore provide a valid inner ball; the outer radius is also valid. Their binary lengths are polynomially bounded.
The stated mixing estimate for approximately satisfied constraints is consistent with concavity and the center’s slack. The weak-separation-to-optimization theorem invoked here has the relevant hypotheses: a compact convex body, explicitly supplied inner and outer balls, and a polynomial-time weak separation oracle. Its weak optimization conclusion matches the approximate feasibility and objective guarantees used in the output. See [Grötschel–Lovász–Schrijver, Sections 1–3](https://ir.cwi.nl/pub/10046/10046D.pdf).
The conversion from these guarantees to
\(\|y-q(x)\|_1\le(2\tau+1)\gamma\)
is correct. The finite-precision separation implementation needs the minor clarification described below.
The Jacobian entries and the implicit derivative formula are correct. In particular, differentiation with respect to the seed coordinate contributes \(e^{-H_u}\), rather than an additional diffusion term.
The inequality
\(Jq\le q-x\le(1-p_{\min})q\)
correctly yields invertibility in the weighted maximum norm. The ordinary maximum-norm inverse bound is valid, although deliberately loose.
The logarithms of the conditioning parameters have polynomial size. Thus the intended precision argument supports polynomial bit complexity. However, the instruction to make the perturbation smaller than “half the inverse-norm bound” uses the bound in the wrong direction; its reciprocal is needed. This is a minor, routine correction to the implementation specification, not a failure of the fixed-point argument.
The factors \(e\) and \(e^2\) correctly account for deleting one or two marking factors. The inequalities involving \(S/(e^S-1)\), \(S^2/(e^S-1)\), and \(Se^{-S}\) give the stated derivative bounds.
On an infinite tree, every type has positive marking probability at the points under consideration. Since there are finitely many types, the accumulated quantity \(S\) diverges with depth. The displayed bounds consequently force the first and second derivatives to tend to zero. The uniform bounds justify the expectation limits in the interior.
The group weights are nonnegative and sum to one, so averaging preserves all bounds. Crucially, these estimates introduce no inverse power of \(\kappa\).
At coordinates with marking probability one, the neighborhood language needs a one-sided boundary interpretation, as noted below.
The transformation \(x_t=b_tz_t\) represents every feasible allocation: the budget already implies \(x_t\le\kappa\), so replacing the coordinate cap by \(\min\{\mu_t,\kappa\}\) loses nothing.
The baseline consumes at most \(\eta\kappa\). Integrating directions from \(D\) for total time one preserves both the budget and coordinate caps.
The positive baseline gives continuity on the benchmark’s compact domain. Monotonicity and the scaling inequality establish
\(B\ge(1-\eta)\mathrm{OPT}\)
without assuming that the original, possibly discontinuous objective attains its supremum. The proportional allocation also correctly establishes \(\mathrm{OPT}\ge\kappa\).
The coordinatewise-maximum argument establishes the diminishing-returns comparison used to obtain one direction satisfying every group inequality simultaneously.
The oracle-error allowances are consistent. The value error, gradient error, linear-program relaxation, and downward rounding together yield the stated \(5h\) allowance. Downward rounding preserves membership in \(D\), and the gradient bound justifies the proposed grid spacing.
A fixed binary grid and the common update denominator give polynomial allocation description length.
For an active group, the value bound along the step is valid with the chosen \(N\). Combining it with the Hessian bound gives a Taylor-loss coefficient bounded by \(C_0\); the numerical comparison required here is \(4e^2<32\).
The deficit recurrence is valid for active groups. For inactive groups, monotonicity preserves the bound by \(h\), which is compatible with the displayed inductive envelope.
Thus every completed run achieves
\(\min_jf_j(z^N)\ge(c-6\eta)\beta\).
This conclusion applies even to a completed target above \(B\), so selecting the largest completed target is legitimate.
The geometric search contains a completed target within the required factor of \(B\). The final constant inequalities hold for the prescribed range of \(\eta\). The resulting guarantee implies the requested squared-constant guarantee.
The step count, target count, rational lengths, and required precision are polynomial in the claimed parameters. The established dependence on the budget is through its binary length, rather than a polynomial factor in \(1/\kappa\).
Adding mutually adjacent universal vertices increases the clique number by exactly the number added. The padded instance has polynomial size and clique number at least \(N/2\).
The support-merging argument correctly handles nonadjacent supported vertices: the adjacency quadratic is affine in their weight split. Each merge reduces support without decreasing that quadratic. The final clique calculation proves the asserted inequality, with equality on a maximum clique.
The zero-vector case is immediate; normalization is otherwise legitimate.
The matrix entries are nonnegative and at most two. The weighted vertex-row sums equal one, while the sink row is zero. With the recurrence’s matrix orientation, these are precisely the sums needed for the claimed Jacobian column bound.
The contraction claim is therefore valid. The bounds \(H_u\le2\), \(\|q-x\|_1\le\alpha\), and the exponential remainder estimate give the stated \(3\alpha^2\) first-order error.
Summing the first-order term produces exactly \(A(x)\), including the negative sink-seeding term.
Dropping the nonpositive sink term and using the graph inequality gives the asserted upper bound. The scalar expression is increasing over the relevant seed-mass interval.
Uniform seeding on a maximum clique attains equality. Its coordinate caps hold because \(\omega\ge N/2\). Consequently, the two-sided bound around \(U_\omega\) follows.
The consecutive-clique gap is
\(U_r-U_{r-1}=\alpha/(16r(r-1))\),
and its stated lower bound is valid.
The total error allowance satisfies
\(6\alpha^2+\varepsilon_{\mathrm{add}}
=(7/512)\alpha/N^2
<\alpha/(16N^2)\).
Thus a successful approximation on a yes-instance passes the strict rational test. Every feasible allocation on a no-instance fails it, independently of approximation success.
The tolerance has polynomially bounded inverse, and the construction uses the fixed budget \(1/4\). This establishes hardness for the requested additive approximation scheme; it does not claim hardness for a fixed constant tolerance.
Rejecting infeasible outputs makes the randomized decision procedure one-sided. The resulting implication \(\mathrm{NP}=\mathrm{RP}\) is justified.
Issues and minimum requested clarification
The continuous complexity classification below refers to the established additive hardness. The multiplicative guarantee is also established in substance; these different approximation requirements do not constitute a split by input representation.
⟨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.