- Rating
- 1
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
The paper proposes an influence-maximization algorithm for directed IC networks with a high-probability (1−1/e−epsilon) approximation and an expected-time bound without a multiplicative polynomial dependence on the seed budget k. It reserves at most floor(epsilon k/3) positions for vertices sampled proportionally to reverse-expansion cost. RR searches terminate exactly when they encounter a reserved seed, and greedy coverage fills the remaining positions. An independent estimation phase accumulates a capped search-cost statistic to determine the sample count. Matching that statistic's role in sample count and sample-generation cost removes its unknown mean from the total-work bound. The paper claims O((m+n) epsilon^−3 log(2n/delta)) expected time and an extension to triggering models with explicit sampling costs.
Critical strengths
-
Eliminating the multiplicative budget factor for every valid cardinality budget would improve a concrete limitation of standard RR-based bounds. The paper openly exchanges epsilon^−2 for epsilon^−3 dependence and does not claim a single ordering that solves every budget simultaneously.
-
Reserving any sufficiently small set limits approximation loss, while its cost-weighted distribution controls search work. Keeping estimation independent from both the reserved set and final samples is important. The text correctly distinguishes that independence from the dependence among searches sharing the same reserved set.
Critical weaknesses
-
The supplied manuscript ends on page 11, without Appendices A–D. Those sections are needed for the coverage implementation, prefix-integral argument, exact capped-score procedure, stopping-time guarantees, and extension. For example, Lemma 4.4 asserts the high-probability sample-count sufficiency needed for approximation, but the necessary bridge between the statistic mean and OPT_k is not derived in the available text. This prevents a complete correctness and total-cost assessment of a paper whose principal contribution is its theorem.
-
HIST already uses sentinel-based termination, and the manuscript discusses another budget-independent result with a restriction involving k epsilon. The distinction should be demonstrated across assumptions, approximation, failure probability, and local sampling costs, rather than relying mainly on the headline budget factor. The additional inverse-epsilon factor can offset the advantage at small budgets or high precision; when k<3/epsilon there are no prescribed draws.
Questions for authors
- Where are Appendices A–D in the official submission? Please identify the complete proofs of Lemmas 4.1, 4.3, and 4.4 and Theorem 4.6, together with ScoreRR and BucketGreedy. This is the principal material-access issue affecting the present assessment.
- What exact relation between the capped-score mean and OPT_k establishes sample sufficiency, and how is that high-probability argument separated from the unconditional moment calculation used for runtime? Please include the treatment of searches sharing the same prescribed set and all initialization, storage, and greedy-update costs.
- Can the paper give a theorem-level comparison with HIST and the cited budget-independent predecessor, including the small-k regime and triggering-model access assumptions? Which ranges of k and epsilon yield an asymptotic advantage once the precision dependence is included?
Thank you for explaining which parts of the proof you could not access. We apologize for not making their location clear. The main PDF ends on p. 11; the file under Supplementary Material on the submission page is the full 21-page paper, with Appendices A–D on pp. 12–21. In that file, BucketGreedy is Algorithm B.1 on p. 13, and ScoreRR is Algorithm C.1 on p. 16. The proofs of Lemmas 4.1, 4.3, and 4.4 are on pp. 15, 17, and 18, respectively; the proof of Theorem 4.6 is on pp. 18–19. We will add a direct pointer in the main paper. We also give the key argument here.
The bridge to the optimum is nμ/2≤OPTk (Lemma C.1, pp. 15–16). To see it, independently draw k vertices with probabilities c(v)/C, and let U be the set of distinct draws. For a fixed RR set R of total cost w(R), the probability that U hits it is 1−(1−w(R)/C)k, which is at least 21min{1,kw(R)/C}=X(R)/2. Averaging and applying the RR identity gives nμ/2≤E[σ(U)]≤OPTk, since every realization of U is feasible.
For sample sufficiency, Lemma 4.3 gives Γ/(2τ)≤μ with probability at least 1−δ/2. On this event, 4τ/Γ≥2/μ≥n/OPTk. Also n/k≥n/OPTk, since seeds activate themselves. Thus both terms in aτ=min{n/k,4τ/Γ} are large enough, and the resulting sample count meets the threshold in Theorem 3.5. The fresh final samples contribute at most another δ/2 failure probability.
For runtime, we do not condition on that event. Lemma 4.4 gives the unconditional bound μE[aτ]≤8. Conditional on the estimation phase, N is fixed, while the reserved set B and the final RR samples retain their original distributions. Averaging over B and one fresh sample gives expected work O(Cμ/(b+1)) per search. Linearity of expectation gives O(NCμ/(b+1)) for all searches, even though their costs share B. Theorem 4.6 also charges O(C) for initialization, O(CΓ/k) for estimation, and O(n+I) for greedy selection, where I is the number of retained incidences. Vertex marks are initialized once and only touched entries are reset. Each retained incidence is already charged when stored and is scanned only a constant number of times by BucketGreedy.
Finally, you are right that when k<3/ε there are no reserved draws. In that regime Eq. (C.5) retains the usual ε−2 dependence; when εk grows, its denominator 1+⌊εk/3⌋ gives a growing improvement over the standard general-IC RR upper bound. HIST already uses early stopping, but selects and validates its sentinels for influence; our bound uses their cost-weighted distribution and the independent estimator. Lakshmanan’s Theorem 1 assumes kε<1 and gives success probability at least 3/5, whereas our bound holds for every input budget at the requested accuracy and confidence. For the triggering extension, Definition D.1 and Theorem D.2 (p. 20) explicitly charge preprocessing and the cost of sampling and processing each local triggering set; an edge-linear bound applies only when the local representation supports it.
We hope these pointers and the argument above make it possible to assess the proofs that were missing from the main PDF.