An approximation algorithm for maximum weight budgeted connected set cover

DOI10.1007/S10878-015-9838-1MaRDI QIDQ281790zbMATH OpenOpenAlexFDO

Authors 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

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

Recommendations

• A simple approximation algorithm for minimum weight partial connected set cover
• The budgeted maximum coverage problem
• Approximation algorithms for minimum weight partial connected set cover problem
• scientific article; zbMATH DE number 1953104

Cites work

• Algorithms for connected set cover problem and fault-tolerant connected set cover problem
• An analysis of approximations for maximizing submodular set functions—I
• Analyzing the optimal neighborhood: algorithms for budgeted and partial connected dominating set problems
• Approximation Algorithms for Constrained Node Weighted Steiner Tree Problems
• Efficient recovery from power outage (extended abstract)
• Improved approximation algorithms for (budgeted) node-weighted Steiner problems
• Minimum connected dominating sets and maximal independent sets in unit disk graphs
• The budgeted maximum coverage problem

Cited in

(8)

• A simple approximation algorithm for minimum weight partial connected set cover
• The multi-budget maximum weighted coverage problem
• In Memoriam: Ker-I Ko (1950–2018)
• scientific article; zbMATH DE number 1953104 (Why is no real title available?)
• scientific article; zbMATH DE number 6815827 (Why is no real title available?)
• Constant approximation for the lifetime scheduling problem of \(p\)-percent coverage
• Approximation algorithms for minimum weight partial connected set cover problem
• A note on `Algorithms for connected set cover problem and fault-tolerant connected set cover problem'

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

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