A bicriteria algorithm for the minimum submodular cost partial set multi-cover problem

DOI10.1016/J.TCS.2019.03.004MaRDI QIDQ2282997zbMATH OpenOpenAlexWikidataFDO

Authors Yishuo Shi, Yingli Ran, Zhao Zhang, Du Ding-Zhu

Publication date 27 December 2019

Published in Theoretical Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

bicriteria algorithmmulti-coverpartial coversubmodular cover

Mathematics Subject Classification ID

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

Abstract: This paper studies randomized approximation algorithm for a variant of the set cover problem called minimum submodular cost partial multi-cover (SCPMC), in which each element $e$ has a covering requirement $r_e$ and a profit $p_e$, and the cost function on sub-collection of sets is submodular, the goal is to find a minimum cost sub-collection of sets which fully covers at least $q$-percentage of total profit, where an element $e$ is fully covered by sub-collection $S^{\prime }$ if and only if it belongs to at least $r_e$ sets of $mathcal{S}^{\prime }$. Previous work shows that such a combination enormously increases the difficulty of studies, even when the cost function is linear. In this paper, assuming that the maximum covering requirement $r_{max}=ma{x}_e{r}_e$ is a constant and the cost function is nonnegative, monotone nondecreasing, and submodular, we give the first randomized bicriteria algorithm for SCPMC the output of which fully covers at least $(q-varepsilon)$-percentage of all elements and the performance ratio is $O(b/varepsilon)$ with a high probability, where $$ and $f$ is the maximum number of sets containing a common element. The algorithm is based on a novel non-linear program. Furthermore, in the case when the covering requirement $requiv1$, a bicriteria $O(f/varepsilon)$-approximation can be achieved even when monotonicity requirement is dropped off from the cost function.

Recommendations

• Approximation algorithm for the partial set multi-cover problem
• Algorithms for covering multiple submodular constraints and applications
• Approximation algorithm for partial set multicover versus full set multicover
• Local ratio method on partial set multi-cover
• Primal dual algorithm for partial set multi-cover

Cites work

• A bicriteria approximation algorithm for minimum submodular cost partial multi-cover problem
• A combinatorial algorithm minimizing submodular functions in strongly polynomial time.
• A Greedy Heuristic for the Set-Covering Problem
• A note on submodular function minimization with covering type linear constraints
• A unified approach to approximating partial covering problems
• Almost-polynomial ratio ETH-hardness of approximating densest k-subgraph
• An analysis of the greedy algorithm for the submodular set covering problem
• An Extension of the Lovász Local Lemma, and its Applications to Integer Programming
• Analytical approach to parallel repetition
• Approximation algorithm for partial positive influence problem in social network
• Approximation algorithms for combinatorial problems
• Approximation algorithms for covering/packing integer programs
• Approximation algorithms for partial covering problems
• Approximation Algorithms for the Set Covering and Vertex Cover Problems
• Greedy -approximation algorithm for covering with arbitrary constraints and submodular cost
• scientific article; zbMATH DE number 3904328 (Why is no real title available?)
• Improved performance of the greedy algorithm for partial cover
• Local ratio method on partial set multi-cover
• Minimizing the union: tight approximations for small set bipartite vertex expansion
• On approximating (sparse) covering integer programs
• On positive influence dominating sets in social networks
• On the approximability of influence in social networks
• On the ratio of optimal integral and fractional covers
• Packing interdiction and partial covering problems
• Primal dual algorithm for partial set multi-cover
• Primal-Dual RNC Approximation Algorithms for Set Cover and Covering Integer Programs
• Randomized approximation algorithms for set multicover problems with applications to reverse engineering of protein and gene networks
• Submodular function minimization under a submodular set covering constraint
• Submodular Function Minimization under Covering Constraints
• 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

(15)

• Approximation algorithm for the partial set multi-cover problem
• Online bicriteria algorithms to balance coverage and cost in team formation
• A primal-dual approximation algorithm for the \(k\)-prize-collecting minimum power cover problem
• Greedy guarantees for minimum submodular cost submodular/non-submodular cover problem
• Approximation algorithm for minimum partial multi-cover under a geometric setting
• Algorithms for covering multiple submodular constraints and applications
• Primal dual algorithm for partial set multi-cover
• Local ratio method on partial set multi-cover
• Minimum power partial multi-cover on a line
• Approximation algorithm for partial set multicover versus full set multicover
• Breaking ther_maxBarrier: Enhanced Approximation Algorithms for Partial Set Multicover Problem
• Approximation and Online Algorithms
• A bicriteria approximation algorithm for minimum submodular cost partial multi-cover problem
• On generalizations of partial scenario set cover
• Approximation algorithm for the minimum interval partial multi-cover problem

This page was built for publication: A bicriteria algorithm for the minimum submodular cost partial set multi-cover problem

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