A simple approximation algorithm for minimum weight partial connected set cover

DOI10.1007/s10878-017-0122-4zbMath1383.90036OpenAlexW2593090687MaRDI QIDQ1680500

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)

Cites Work

• Unnamed Item
• Unnamed Item
• An approximation algorithm for maximum weight budgeted connected set cover
• Improved performance of the greedy algorithm for partial cover
• The relation of connected set cover and group Steiner tree
• A unified approach to approximating partial covering problems
• Approximating fault-tolerant group-Steiner problems
• On the positive-negative partial set cover problem
• Algorithms for connected set cover problem and fault-tolerant connected set cover problem
• Approximation algorithms for combinatorial problems
• On the ratio of optimal integral and fractional covers
• Maximum lifetime connected coverage with two active-phase sensors
• Using Homogeneous Weights for Approximating the Partial Cover Problem
• Partial Interval Set Cover – Trade-Offs between Scalability and Optimality
• A threshold of ln n for approximating set cover
• Covering Analysis of the Greedy Algorithm for Partial Cover
• Saving an epsilon
• A Greedy Heuristic for the Set-Covering Problem
• Approximation algorithms for partial covering problems
• Improved Approximation Algorithms for (Budgeted) Node-Weighted Steiner Problems
• Analyzing the Optimal Neighborhood: Algorithms for Budgeted and Partial Connected Dominating Set Problems
• Approximation Algorithms for Constrained Node Weighted Steiner Tree Problems
• Connected Set Cover Problem and Its Applications
• Approximation algorithms for minimum weight partial connected set cover problem

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