Approximation algorithms for minimum weight partial connected set cover problem

DOI10.1007/S10878-014-9782-5MaRDI QIDQ5963645zbMATH OpenOpenAlexFDO

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

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

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

• 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
• 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?)
• 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

(7)

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

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)