An approximation algorithm for maximum weight budgeted connected set cover

DOI10.1007/s10878-015-9838-1zbMath1347.90074OpenAlexW1992451418MaRDI QIDQ281790

Yingli Ran, Zhao Zhang, Jun Liang, Ker-I. Ko

Publication date: 11 May 2016

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

Full work available at URL: https://doi.org/10.1007/s10878-015-9838-1

zbMATH Keywords

approximation algorithmbudgeted set coverconnected set cover

Mathematics Subject Classification ID

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

Related Items (3)

Constant Approximation for the Lifetime Scheduling Problem of p-Percent Coverage ⋮ A simple approximation algorithm for minimum weight partial connected set cover ⋮ In Memoriam: Ker-I Ko (1950–2018)

Cites Work

• Minimum connected dominating sets and maximal independent sets in unit disk graphs
• Algorithms for connected set cover problem and fault-tolerant connected set cover problem
• The budgeted maximum coverage problem
• Efficient recovery from power outage (extended abstract)
• An analysis of approximations for maximizing submodular set functions—I
• 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

This page was built for publication: An approximation algorithm for maximum weight budgeted connected set cover