This article has been reviewed according to Science X's editorial process and policies. Editors have highlighted the following attributes while ensuring the content's credibility:
fact-checked
proofread
A primal-dual approximation algorithm for the k-prize-collecting minimum vertex cover problem with submodular penalties
![A combinatorial 3-approximation algorithm (Algorithm 2) based on the guessing technique and the primal-dual framework. Credit: Liu, X., Li, W. & Yang, J. A primal-dual approximation algorithm for the k-prize-collecting minimum vertex cover problem with submodular penalties](https://scx1.b-cdn.net/csz/news/800a/2023/a-primal-dual-approxim.jpg)
The k-prize-collecting minimum vertex cover problem with submodular penalties (k-PCVCS) is a generalization of the minimum vertex cover problem, which is one of the most important and fundamental problems in graph theory and combinatorial optimization.
This problem is to select a vertex set that covers at least k edges, and the objective is to minimize the total cost of the vertices in the selected set plus the penalty of the uncovered edge set, where the penalty is determined by a submodular function.
To solve the k-PCVCS, Xiaofei Liu et al. published their new research in Frontiers of Computer Science.
In the research, they first proved that Algorithm 1 can be implemented in O(n16r+n17), where r is the time for one function evaluation. Then, they proved that Algorithm 2 is a 3-approximation algorithm for the k-PCVCS. Specifically, if the penalty function is linear, Algorithm 2 is a 2-approximation algorithm.
Future work may focus on studying the version with general penalties, such as, subadditive or supermodular penalties. Meanwhile, the k-PCVCS with hard capacities deserves to be explored, in which each vertex v is covered at most Cv edges.
More information: Xiaofei Liu et al, A primal-dual approximation algorithm for the k-prize-collecting minimum vertex cover problem with submodular penalties, Frontiers of Computer Science (2022). DOI: 10.1007/s11704-022-1665-9