Approximation algorithm for partial set multicover versus full set multicover

DOI10.1142/S179383091850026XMaRDI QIDQ4634530zbMATH OpenOpenAlexFDO

Authors Pengcheng Liu, Xiaohui Huang

Publication date 10 April 2018

Published in Discrete Mathematics, Algorithms and Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1142/s179383091850026x

zbMATH Keywords

greedy algorithmpartial set multicoverperformance ratio

Mathematics Subject Classification ID

Approximation algorithms (68W25) Combinatorial optimization (90C27)

Recommendations

• Local ratio method on partial set multi-cover
• Approximation algorithm for the partial set multi-cover problem
• Primal dual algorithm for partial set multi-cover
• A primal-dual algorithm for the minimum partial set multi-cover problem
• A bicriteria algorithm for the minimum submodular cost partial set multi-cover problem

Cites work

• A threshold of ln n for approximating set cover
• Analytical approach to parallel repetition
• Approximation algorithm for partial positive influence problem in social network
• Approximation algorithms for partial covering problems
• Design and analysis of approximation algorithms
• FAST INFORMATION PROPAGATION IN SOCIAL NETWORKS
• Improved performance of the greedy algorithm for partial cover
• Local ratio method on partial set multi-cover
• On positive influence dominating sets in social networks
• Positive Influence Dominating Set in Online Social Networks
• Primal-Dual RNC Approximation Algorithms for Set Cover and Covering Integer Programs
• The design of approximation algorithms
• TWO ALGORITHMS FOR CONNECTED r-HOP k-DOMINATING SET
• 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

(14)

• Approximation algorithm for the partial set multi-cover problem
• Approximation algorithm for minimum power partial multi-coverage in wireless sensor networks
• A primal-dual algorithm for the minimum power partial cover problem
• A bicriteria algorithm for the minimum submodular cost partial set multi-cover problem
• A primal-dual algorithm for the minimum partial set multi-cover problem
• Primal dual algorithm for partial set multi-cover
• Local ratio method on partial set multi-cover
• Partial Interval Set Cover – Trade-Offs between Scalability and Optimality
• Exact algorithms for set multicover and multiset multicover problems
• scientific article; zbMATH DE number 1754596 (Why is no real title available?)
• Approximation preserving reductions for set covering, vertex covering and independent set hierarchies under differential approximationa
• Breaking ther_maxBarrier: Enhanced Approximation Algorithms for Partial Set Multicover Problem
• A bicriteria approximation algorithm for minimum submodular cost partial multi-cover problem
• Minimum power partial cover with fairness constraint

This page was built for publication: Approximation algorithm for partial set multicover versus full set multicover

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