Approximation algorithm for the partial set multi-cover problem

DOI10.1007/S10898-019-00804-YzbMATH Open1433.90144arXiv1811.08185OpenAlexW2954159299MaRDI QIDQ2010112FDOQ2010112

Authors: Yishuo Shi, Yingli Ran, Zhao Zhang, James Willson, Guangmo Tong, Du Ding-Zhu 

Publication date: 3 December 2019

Published in: Journal of Global Optimization (Search for Journal in Brave)

Abstract: Partial set cover problem and set multi-cover problem are two generalizations of set cover problem. In this paper, we consider the partial set multi-cover problem which is a combination of them: given an element set $E$, a collection of sets $mathcalSsubseteq{2}^E$, a total covering ratio $q$ which is a constant between 0 and 1, each set $SinmathcalS$ is associated with a cost $c_S$, each element $einE$ is associated with a covering requirement $r_e$, the goal is to find a minimum cost sub-collection $mathcal{S}^{\prime }subseteqmathcalS$ to fully cover at least $q|E|$ elements, where element $e$ is fully covered if it belongs to at least $r_e$ sets of $mathcal{S}^{\prime }$. Denote by $r_{max}=max{r}_{e}coloneinE$ the maximum covering requirement. We present an $(O(frac{r}_{max}lo{g}^{2}nvarepsilon),1-varepsilon)$-bicriteria approximation algorithm, that is, the output of our algorithm has cost at most $O(frac{r}_{max}lo{g}^{2}nvarepsilon)$ times of the optimal value while the number of fully covered elements is at least $(1-varepsilon)q|E|$.

Full work available at URL: https://arxiv.org/abs/1811.08185

Recommendations

• Approximation algorithm for partial set multicover versus full set multicover
• Local ratio method on partial set multi-cover
• A bicriteria algorithm for the minimum submodular cost partial set multi-cover problem
• Approximation algorithms for partial covering problems
• Primal dual algorithm for partial set multi-cover

zbMATH Keywords

approximation algorithmbicriteria algorithmminimum densest sub-collectionpartial set multi-cover

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27)

Cites Work

• Reducibility among Combinatorial Problems
• Approximation algorithms for combinatorial problems
• A Greedy Heuristic for the Set-Covering Problem
• Approximation Algorithms for the Set Covering and Vertex Cover Problems
• On the ratio of optimal integral and fractional covers
• Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
• Using homogeneous weights for approximating the partial cover problem
• Algorithms for facility location problems with outliers. (Extended abstract)
• Approximation algorithms for partial covering problems
• Title not available (Why is that?)
• Title not available (Why is that?)
• Worst-Case Analysis of Greedy Heuristics for Integer Programming with Nonnegative Data
• Improved performance of the greedy algorithm for partial cover
• Title not available (Why is that?)
• Analytical approach to parallel repetition
• A unified approach to approximating partial covering problems
• Prize-collecting Steiner network problems
• Approximating Steiner networks with node-weights
• Set connectivity problems in undirected graphs and the directed Steiner network problem
• Primal-Dual RNC Approximation Algorithms for Set Cover and Covering Integer Programs
• Approximating minimum-cost connectivity problems via uncrossable bifamilies
• Approximation algorithm for partial positive influence problem in social network
• Almost-polynomial ratio ETH-hardness of approximating densest k-subgraph
• Prize-collecting survivable network design in node-weighted graphs
• Primal dual algorithm for partial set multi-cover
• Local ratio method on partial set multi-cover

Cited In (16)

• Title not available (Why is that?)
• A 6/5-Approximation Algorithm for the Maximum 3-Cover Problem
• Approximation algorithm for minimum partial multi-cover under a geometric setting
• A fast approximation algorithm for the multicovering problem
• Title not available (Why is that?)
• A new approximation algorithm for \(k\)-set cover problem
• A bicriteria approximation algorithm for minimum submodular cost partial multi-cover problem
• Breaking ther_maxBarrier: Enhanced Approximation Algorithms for Partial Set Multicover Problem
• Dynamic programming based algorithms for set multicover and multiset multicover problems
• A unified approach to approximating partial covering problems
• Approximation algorithms for the partial assignment problem
• On approximating partial scenario set cover
• Constant Approximation for the Lifetime Scheduling Problem of p-Percent Coverage
• A Unified Approach to Approximating Partial Covering Problems
• A primal-dual approximation algorithm for the \(k\)-prize-collecting minimum power cover problem
• Partial Interval Set Cover – Trade-Offs between Scalability and Optimality

This page was built for publication: Approximation algorithm for the partial set multi-cover problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2010112)