Algorithms for NP-Hard Problems (Section 20.3: A Greedy Heuristic for Influence Maximization) [2/2]
Tim Roughgarden Lectures · 18:41
The Kempe–Kleinberg–Tardos (KKT) greedy algorithm for influence maximization inherits the same approximation guarantee as greedy maximum coverage—at least \(1-(1-1/K)^K\) of optimal influence—because influence is a pr...