Dynamic ((1+ε) ln n)-Approximation Algorithms for Minimum Set Cover and Dominating Set.
Shay SolomonAmitai UzradPublished in: STOC (2023)
Keyphrases
- approximation algorithms
- set cover
- dominating set
- facility location problem
- connected dominating set
- np hard
- minimum cost
- greedy heuristics
- constant factor
- special case
- worst case
- vertex cover
- primal dual
- upper bound
- network flow
- disjoint paths
- approximation ratio
- randomized algorithms
- lower bound
- greedy algorithm
- constant factor approximation
- objective function
- linear program
- optimization problems