The sequential sum problem and performance bounds on the greedy algorithm for the on-line Steiner problem.
Zevi MillerDan PritikinManley PerkelIvan Hal SudboroughPublished in: Networks (2005)
Keyphrases
- greedy algorithm
- worst case
- objective function
- randomized algorithm
- greedy algorithms
- lower bound
- approximation guarantees
- upper bound
- dynamic programming
- average case
- set cover
- knapsack problem
- np hard
- influence maximization
- greedy strategy
- influence spread
- greedy heuristic
- optimization problems
- social media
- special case