A primal-dual approximation algorithm for the k-prize-collecting minimum vertex cover problem with submodular penalties.
Xiaofei LiuWeidong LiJinhua YangPublished in: Frontiers Comput. Sci. (2023)
Keyphrases
- primal dual
- prize collecting
- approximation algorithms
- np hard
- convergence rate
- dynamic programming
- semidefinite programming
- objective function
- randomly generated
- hybrid algorithm
- linear program
- worst case
- special case
- combinatorial optimization
- particle swarm optimization
- solution quality
- multi objective
- computational complexity
- optimal solution
- simplex algorithm
- integrality gap
- image processing