Approximation algorithms for the capacitated correlation clustering problem with penalties.
Sai JiGaidi LiDongmei ZhangXianzhao ZhangPublished in: J. Comb. Optim. (2023)
Keyphrases
- approximation algorithms
- correlation clustering
- network design problem
- np hard
- facility location problem
- special case
- hierarchical clustering
- worst case
- vertex cover
- minimum cost
- hard constraints
- lower bound
- scheduling problem
- optimal solution
- np complete
- branch and bound algorithm
- integer programming
- primal dual
- linear programming
- approximation ratio
- map inference
- routing problem
- graphical models