Online Matching in Sparse Random Graphs: Non-Asymptotic Performances of Greedy Algorithm.

Nathan Noiry Vianney Perchet Flore Sentenac

Published in: NeurIPS (2021)

Keyphrases

greedy algorithm
random graphs
worst case
greedy algorithms
objective function
graph theoretic
structured sparsity
dynamic programming
greedy strategy
influence maximization
greedy heuristic
set cover
search algorithm
randomized algorithm
influence spread
small world
phase transition
knapsack problem
squeaky wheel