Approximation algorithm for partial set multicover versus full set multicover

DOI10.1142/S179383091850026XzbMath1434.68681OpenAlexW2786639653MaRDI QIDQ4634530

Pengcheng Liu, Xiao-hui 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 algorithmperformance ratiopartial set multicover

Mathematics Subject Classification ID

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

Related Items

Approximation algorithm for minimum power partial multi-coverage in wireless sensor networks ⋮ Breaking ther_maxBarrier: Enhanced Approximation Algorithms for Partial Set Multicover Problem ⋮ A primal-dual algorithm for the minimum power partial cover problem

Cites Work

• 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
• Design and analysis of approximation algorithms
• Local ratio method on partial set multi-cover
• Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
• Using Homogeneous Weights for Approximating the Partial Cover Problem
• The Design of Approximation Algorithms
• A threshold of ln n for approximating set cover
• FAST INFORMATION PROPAGATION IN SOCIAL NETWORKS
• Positive Influence Dominating Set in Online Social Networks
• Worst-Case Analysis of Greedy Heuristics for Integer Programming with Nonnegative Data
• Primal-Dual RNC Approximation Algorithms for Set Cover and Covering Integer Programs
• Approximation algorithms for partial covering problems
• TWO ALGORITHMS FOR CONNECTED r-HOP k-DOMINATING SET
• Analytical approach to parallel repetition