A bicriteria algorithm for the minimum submodular cost partial set multi-cover problem
From MaRDI portal
Publication:2282997
DOI10.1016/j.tcs.2019.03.004zbMath1436.90128arXiv1701.05339OpenAlexW2921041251WikidataQ128232644 ScholiaQ128232644MaRDI QIDQ2282997
Ding-Zhu Du, Yishuo Shi, Zhao Zhang, Yingli Ran
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
Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Approximation algorithms (68W25)
Related Items (4)
Minimum power partial multi-cover on a line ⋮ Breaking thermaxBarrier: Enhanced Approximation Algorithms for Partial Set Multicover Problem ⋮ A primal-dual approximation algorithm for the \(k\)-prize-collecting minimum power cover problem ⋮ Approximation algorithm for minimum partial multi-cover under a geometric setting
Cites Work
- Unnamed Item
- Improved performance of the greedy algorithm for partial cover
- Approximation algorithm for partial positive influence problem in social network
- On positive influence dominating sets in social networks
- A unified approach to approximating partial covering problems
- A note on submodular function minimization with covering type linear constraints
- Randomized approximation algorithms for set multicover problems with applications to reverse engineering of protein and gene networks
- Approximation algorithms for combinatorial problems
- On the ratio of optimal integral and fractional covers
- An analysis of the greedy algorithm for the submodular set covering problem
- A combinatorial algorithm minimizing submodular functions in strongly polynomial time.
- Greedy \(\varDelta \)-approximation algorithm for covering with arbitrary constraints and submodular cost
- Primal dual algorithm for partial set multi-cover
- Local ratio method on partial set multi-cover
- Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
- Approximation algorithms for covering/packing integer programs
- Using Homogeneous Weights for Approximating the Partial Cover Problem
- Submodular Function Minimization under a Submodular Set Covering Constraint
- A combinatorial, strongly polynomial-time algorithm for minimizing submodular functions
- An Extension of the Lovász Local Lemma, and its Applications to Integer Programming
- On the Approximability of Influence in Social Networks
- A Greedy Heuristic for the Set-Covering Problem
- Approximation Algorithms for the Set Covering and Vertex Cover Problems
- Worst-Case Analysis of Greedy Heuristics for Integer Programming with Nonnegative Data
- Primal-Dual RNC Approximation Algorithms for Set Cover and Covering Integer Programs
- Partial Resampling to Approximate Covering Integer Programs
- Minimizing the Union: Tight Approximations for Small Set Bipartite Vertex Expansion
- Approximation algorithms for partial covering problems
- Packing Interdiction and Partial Covering Problems
- Almost-polynomial ratio ETH-hardness of approximating densest k-subgraph
- Submodular Function Minimization under Covering Constraints
- On Approximating (Sparse) Covering Integer Programs
- Analytical approach to parallel repetition
- A bicriteria approximation algorithm for minimum submodular cost partial multi-cover problem
This page was built for publication: A bicriteria algorithm for the minimum submodular cost partial set multi-cover problem
