Approximation algorithms for minimum weight partial connected set cover problem

DOI10.1007/S10878-014-9782-5zbMATH Open1360.90224OpenAlexW2051063311MaRDI QIDQ5963645FDOQ5963645

Authors Dongyue Liang, Zhao Zhang, Xianliang Liu, Wei Wang, Yao-Lin Jiang

Publication date 23 February 2016

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

Full work available at URL https://doi.org/10.1007/s10878-014-9782-5

zbMATH Keywords

approximation algorithmgreedy algorithmset coversubmodular function

Mathematics Subject Classification ID

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

Recommendations

• A simple approximation algorithm for minimum weight partial connected set cover
• An approximation algorithm for maximum weight budgeted connected set cover
• Using homogeneous weights for approximating the partial cover problem
• Approximation algorithm for the minimum weight connected \(k\)-subgraph cover problem
• scientific article; zbMATH DE number 1305393

Cites work

• scientific article; zbMATH DE number 1305393 (Why is no real title available?)
• scientific article; zbMATH DE number 1182766 (Why is no real title available?)
• scientific article; zbMATH DE number 1947055 (Why is no real title available?)
• scientific article; zbMATH DE number 1754596 (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
• Algorithms for connected set cover problem and fault-tolerant connected set cover problem
• An analysis of the greedy algorithm for the submodular set covering problem
• Analyzing the optimal neighborhood: algorithms for budgeted and partial connected dominating set problems
• Approximating fault-tolerant group-Steiner problems
• Approximation algorithms for combinatorial problems
• Approximation algorithms for constrained node weighted Steiner tree problems
• Connected Set Cover Problem and Its Applications
• Improved performance of the greedy algorithm for partial cover
• On the ratio of optimal integral and fractional covers
• Saving an epsilon: a 2-approximation for the \(k\)-MST problem in graphs
• The relation of connected set cover and group Steiner tree

Cited in

(6)

• scientific article; zbMATH DE number 6815827 (Why is no real title available?)
• Efficient constant-factor approximate enumeration of minimal subsets for monotone properties with weight constraints
• An approximation algorithm for maximum weight budgeted connected set cover
• A simple approximation algorithm for minimum weight partial connected set cover
• Complexity and approximation of the connected set-cover problem
• scientific article; zbMATH DE number 784428 (Why is no real title available?)

This page was built for publication: Approximation algorithms for minimum weight partial connected set cover problem

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