An approximation algorithm for submodular hitting set problem with linear penalties

Shaojing Du (), Suogang Gao (), Bo Hou () and Wen Liu ()
Additional contact information
Shaojing Du: Hebei Normal University
Suogang Gao: Hebei Normal University
Bo Hou: Hebei Normal University
Wen Liu: Hebei Normal University

Journal of Combinatorial Optimization, 2020, vol. 40, issue 4, No 13, 1065-1074

Abstract: Abstract The hitting set problem is a generalization of the vertex cover problem to hypergraphs. Xu et al. (Theor Comput Sci 630:117–125, 2016) presented a primal-dual algorithm for the submodular vertex cover problem with linear/submodular penalties. Motivated by their work, we study the submodular hitting set problem with linear penalties (SHSLP). The goal of the SHSLP is to select a vertex subset in the hypergraph to cover some hyperedges and penalize the uncovered ones such that the total cost of covering and penalty is minimized. Based on the primal-dual scheme, we obtain a k-approximation algorithm for the SHSLP, where k is the maximum number of vertices in all hyperedges.

Keywords: Hitting set; Submodular; Penalty; Approximation algorithm; Primal-dual (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s10878-020-00653-6 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:40:y:2020:i:4:d:10.1007_s10878-020-00653-6

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-020-00653-6

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().