Parallel approximation for partial set cover

DOI10.1016/J.AMC.2021.126358MaRDI QIDQ2243336zbMATH OpenOpenAlexFDO

Authors Yingli Ran, Zhao Zhang, Ying Zhang

Publication date 11 November 2021

Published in Applied Mathematics and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.amc.2021.126358

zbMATH Keywords

parallel algorithmapproximation ratiominimum partial set coverminimum power partial cover

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Graph theory (05Cxx)

Recommendations

• scientific article; zbMATH DE number 1754596
• Approximation algorithms for partial covering problems
• Primal dual algorithm for partial set multi-cover
• A simple approximation algorithm for minimum weight partial connected set cover
• Approximation algorithm for the partial set multi-cover problem

Cites work

• scientific article; zbMATH DE number 107951 (Why is no real title available?)
• A Distributed (2+ε)-Approximation for Vertex Cover in O(logδ/ε log log δ) Rounds
• A Primal-Dual Parallel Approximation Technique Applied to Weighted Set and Vertex Covers
• A Simple Parallel Algorithm for the Maximal Independent Set Problem
• A constant-factor approximation for multi-covering with disks
• A primal-dual algorithm for the minimum partial set multi-cover problem
• A unified approach to approximating partial covering problems
• Algorithms for facility location problems with outliers. (Extended abstract)
• Algorithms – ESA 2005
• An analysis of the greedy algorithm for the submodular set covering problem
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• Approximation algorithms for partial covering problems
• Distributed algorithms for covering, packing and maximum weighted matching
• Improved performance of the greedy algorithm for partial cover
• Minimum power partial multi-cover on a line
• On partial covering for geometric set systems
• Primal-Dual RNC Approximation Algorithms for Set Cover and Covering Integer Programs
• Using homogeneous weights for approximating the partial cover problem
• Vertex cover might be hard to approximate to within \(2 - \varepsilon \)

Cited in

(7)

• Distributed and Parallel Algorithms for Set Cover Problems with Small Neighborhood Covers
• Parallel algorithm for minimum partial dominating set in unit disk graph
• Parallel algorithms for minimum general partial dominating set and maximum budgeted dominating set in unit disk graph
• Parallel and serial heuristics for the minimum set cover problem
• A simple approximation algorithm for minimum weight partial connected set cover
• On approximating partial scenario set cover
• Partial Interval Set Cover – Trade-Offs between Scalability and Optimality

This page was built for publication: Parallel approximation for partial set cover

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