A simple approximation algorithm for minimum weight partial connected set cover
From MaRDI portal
Publication:1680500
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
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