Approximation algorithms for minimum weight partial connected set cover problem
From MaRDI portal
Publication:5963645
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
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
Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27)
Cites Work
- A threshold of ln n for approximating set cover
- Approximation algorithms for combinatorial problems
- A Greedy Heuristic for the Set-Covering Problem
- On the ratio of optimal integral and fractional covers
- An analysis of the greedy algorithm for the submodular set covering problem
- Algorithms for connected set cover problem and fault-tolerant connected set cover problem
- Analyzing the optimal neighborhood: algorithms for budgeted and partial connected dominating set problems
- Improved performance of the greedy algorithm for partial cover
- Title not available (Why is that?)
- Saving an epsilon: a 2-approximation for the \(k\)-MST problem in graphs
- Title not available (Why is that?)
- Title not available (Why is that?)
- Approximating fault-tolerant group-Steiner problems
- The relation of connected set cover and group Steiner tree
- Connected Set Cover Problem and Its Applications
- Approximation algorithms for constrained node weighted Steiner tree problems
- Title not available (Why is that?)
- Title not available (Why is that?)
Cited In (6)
- Title not available (Why is that?)
- An approximation algorithm for maximum weight budgeted connected set cover
- Title not available (Why is that?)
- Complexity and approximation of the connected set-cover problem
- A simple approximation algorithm for minimum weight partial connected set cover
- 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)
