Local ratio method on partial set multi-cover
From MaRDI portal
Publication:2410050
DOI10.1007/s10878-016-0066-0zbMath1383.90034OpenAlexW2509865736MaRDI QIDQ2410050
Yingli Ran, Yishuo Shi, Zhao Zhang
Publication date: 17 October 2017
Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s10878-016-0066-0
Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27)
Related Items
An improved approximation algorithm for the \(k\)-prize-collecting minimum power cover problem, On resilient feature selection: computational foundations of \(r\)-\(\mathbb{C} \)-reducts, Approximation algorithm for partial set multicover versus full set multicover, Approximation algorithm for the partial set multi-cover problem, A bicriteria algorithm for the minimum submodular cost partial set multi-cover problem, An approximation algorithm for the partial covering 0-1 integer program, A primal-dual algorithm for the minimum partial set multi-cover problem, Breaking thermaxBarrier: Enhanced Approximation Algorithms for Partial Set Multicover Problem, A primal-dual approximation algorithm for the \(k\)-prize-collecting minimum power cover problem, A primal-dual algorithm for the minimum power partial cover problem, Approximation algorithms for the covering-type \(k\)-violation linear program, Approximation algorithm for minimum partial multi-cover under a geometric setting
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Improved performance of the greedy algorithm for partial cover
- Partial multicovering and the \(d\)-consecutive ones property
- Approximation algorithm for partial positive influence problem in social network
- On positive influence dominating sets in social networks
- Approximation algorithms for combinatorial problems
- On the ratio of optimal integral and fractional covers
- Approximating covering integer programs with multiplicity constraints
- On the approximability of positive influence dominating set in social networks
- Approximation algorithms for covering/packing integer programs
- A Constant-Factor Approximation Algorithm for Packet Routing and Balancing Local vs. Global Criteria
- Using Homogeneous Weights for Approximating the Partial Cover Problem
- Positive Influence Dominating Set in Online 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
- On the Greedy Heuristic for Continuous Covering and Packing Problems
- Approximation algorithms for partial covering problems
- Improved Approximation Guarantees for Packing and Covering Integer Programs
- Reducibility among Combinatorial Problems
- An approximation algorithm for the partial vertex cover problem in hypergraphs
