PTAS for Minimum Cost Multi-covering with Disks.
Ziyun HuangQilong FengJianxin WangJinhui XuPublished in: SODA (2021)
Keyphrases
- minimum cost
- approximation algorithms
- np hard
- network flow
- capacity constraints
- network flow problem
- spanning tree
- special case
- network simplex algorithm
- primal dual
- network design problem
- worst case
- undirected graph
- approximation ratio
- weighted sum
- approximation schemes
- simulated annealing
- polynomial time approximation
- minimum cost flow