A note on the submodular vertex cover problem with submodular penalties

作者：Kamiyama Naoyuki^*

来源：Theoretical Computer Science, 2017, 659: 95-97.

DOI：10.1016/j.tcs.2016.10.017

• Submodular functions
• The vertex cover problem
• The set cover problem

In this paper, we prove that there exists a combinatorial 3-approximation algorithm for the submodular vertex cover problem with submodular penalties introduced by Xu, Wang, Du, and Wu.

• 出版日期2017-1-10