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 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.

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 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 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

Provided by Higher Education Press
Citation: A primal-dual approximation algorithm for the k-prize-collecting minimum vertex cover problem with submodular penalties (2023, August 23) retrieved 22 July 2024 from https://techxplore.com/news/2023-08-primal-dual-approximation-algorithm-k-prize-collecting-minimum.html
This document is subject to copyright. Apart from any fair dealing for the purpose of private study or research, no part may be reproduced without the written permission. The content is provided for information purposes only.

Explore further

Algorithms developed to tackle tenuous group query

3 shares

Feedback to editors