An approximation algorithm for submodular hitting set problem with linear penalties
- PDF / 268,451 Bytes
- 10 Pages / 439.37 x 666.142 pts Page_size
- 83 Downloads / 214 Views
An approximation algorithm for submodular hitting set problem with linear penalties Shaojing Du1 · Suogang Gao1 · Bo Hou1 · Wen Liu1 Accepted: 18 September 2020 / Published online: 25 September 2020 © Springer Science+Business Media, LLC, part of Springer Nature 2020
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 kapproximation algorithm for the SHSLP, where k is the maximum number of vertices in all hyperedges. Keywords Hitting set · Submodular · Penalty · Approximation algorithm · Primal-dual
1 Introduction The hitting set problem involves a hypergraph H = (V , C ), where V is a finite set with elements called vertices and C is a family of subsets of V called hyperedges. Assume |V | = n and |C | = m. Let k be the maximum size of all hyperedges and Δ be the maximum degree of all vertices. A hitting set of H , also called a vertex cover of
B
Wen Liu [email protected] Shaojing Du [email protected] Suogang Gao [email protected] Bo Hou [email protected]
1
School of Mathematical Sciences, Hebei Normal University, Shijiazhuang 050024, People’s Republic of China
123
1066
Journal of Combinatorial Optimization (2020) 40:1065–1074
H , is a subset A ⊆ V such that each hyperedge in C contains at least one vertex from A. The hitting set problem is to select a hitting set of minimum size. For each vertex u ∈ V , if there is an associated nonnegative weight cost w(u), we obtain the weighted version of the problem, the goal of which is to select a hitting set of minimum cost. The hitting set problem in a hypergraph is a generalization of the vertex cover problem in a graph. It is equivalent to the set cover problem by changing the roles of vertices and hyperedges. All these problems are NP-hard, which implies that they can not be solved efficiently unless P = NP. Williamson (2002) investigated a primal-dual method used to design and analyze algorithms that provide approximate solutions to NP-hard problems in combinatorial optimization. Instances of hitting set problems arise in various applications, such as graphtheoretical and geometric settings. Graph-theoretical examples of hitting set problems include vertex cover, edge cover, feedback vertex set, and dominating set problems. In each of these problems the hypergraph is defined with hyperedges corresponding to the edges, vertices, cycles, and neighborhoods, respectively (Bringmann 2016). In geometric examples of hitting set, the hypergraph is defined by the incidences of low complexity geometric shapes, such as points, intervals,
Data Loading...
