A simple approximation algorithm for minimum weight partial connected set cover

DOI10.1007/S10878-017-0122-4MaRDI QIDQ1680500zbMATH OpenOpenAlexFDO

Authors Yubai Zhang, Yingli Ran, Zhao Zhang

Publication date 16 November 2017

Published in Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s10878-017-0122-4

zbMATH Keywords

approximation algorithmbudgeted connected set coverpartial connected set cover

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27)

Recommendations

• Approximation algorithms for minimum weight partial connected set cover problem
• An approximation algorithm for maximum weight budgeted connected set cover
• Algorithms for connected set cover problem and fault-tolerant connected set cover problem
• Complexity and approximation of the connected set-cover problem
• Parallel approximation for partial set cover

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1445375 (Why is no real title available?)
• A Greedy Heuristic for the Set-Covering Problem
• A threshold of ln n for approximating set cover
• A unified approach to approximating partial covering problems
• Algorithms for connected set cover problem and fault-tolerant connected set cover problem
• An approximation algorithm for maximum weight budgeted connected set cover
• Analyzing the optimal neighborhood: algorithms for budgeted and partial connected dominating set problems
• Approximating fault-tolerant group-Steiner problems
• Approximation Algorithms for Constrained Node Weighted Steiner Tree Problems
• Approximation algorithms for combinatorial problems
• Approximation algorithms for minimum weight partial connected set cover problem
• Approximation algorithms for partial covering problems
• Connected Set Cover Problem and Its Applications
• Covering analysis of the greedy algorithm for partial cover
• Improved approximation algorithms for (budgeted) node-weighted Steiner problems
• Improved performance of the greedy algorithm for partial cover
• Maximum lifetime connected coverage with two active-phase sensors
• On the positive-negative partial set cover problem
• On the ratio of optimal integral and fractional covers
• Partial Interval Set Cover – Trade-Offs between Scalability and Optimality
• Saving an epsilon: a 2-approximation for the \(k\)-MST problem in graphs
• The relation of connected set cover and group Steiner tree
• Using homogeneous weights for approximating the partial cover problem

Cited in

(6)

• Analyzing the optimal neighborhood: algorithms for partial and budgeted connected dominating set problems
• An approximation algorithm for maximum weight budgeted connected set cover
• Algorithms for connected set cover problem and fault-tolerant connected set cover problem
• The relation of connected set cover and group Steiner tree
• Approximation algorithms for minimum weight partial connected set cover problem
• Parallel approximation for partial set cover

This page was built for publication: A simple approximation algorithm for minimum weight partial connected set cover

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