Approximation algorithm for the partial set multi-cover problem

DOI10.1007/S10898-019-00804-YMaRDI QIDQ2010112zbMATHOpenAlexFDO

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)

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

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)

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

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

Cites work

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

Cited in

(25)

• A unified approach to approximating partial covering problems
• A new approximation algorithm for \(k\)-set cover problem
• Dynamic programming based algorithms for set multicover and multiset multicover problems
• Constant approximation for the lifetime scheduling problem of \(p\)-percent coverage
• scientific article; zbMATH DE number 1754596 (Why is no real title available?)
• On approximating partial scenario set cover
• Approximation algorithm for minimum partial multi-cover under a geometric setting
• A bicriteria algorithm for the minimum submodular cost partial set multi-cover problem
• Approximation algorithm for partial set multicover versus full set multicover
• A primal-dual algorithm for the minimum partial set multi-cover problem
• A Unified Approach to Approximating Partial Covering Problems
• Tight approximation bounds for maximum multi-coverage
• Breaking ther_maxBarrier: Enhanced Approximation Algorithms for Partial Set Multicover Problem
• Partial Interval Set Cover – Trade-Offs between Scalability and Optimality
• Local ratio method on partial set multi-cover
• A primal-dual approximation algorithm for the \(k\)-prize-collecting minimum power cover problem
• A fast approximation algorithm for the multicovering problem
• A 6/5-Approximation Algorithm for the Maximum 3-Cover Problem
• Primal dual algorithm for partial set multi-cover
• Calculating approximation guarantees for partial set cover of pairs
• Approximation algorithms for the partial assignment problem
• scientific article; zbMATH DE number 784428 (Why is no real title available?)
• Parallel approximation for partial set cover
• Partial sublinear time approximation and inapproximation for maximum coverage
• A bicriteria approximation algorithm for minimum submodular cost partial multi-cover problem

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)