An approximation algorithm for the k-generalized Steiner forest problem
2021
In this paper, we introduce the k-generalized Steiner forest (k-GSF) problem, which is a natural generalization of the k-Steiner forest problem and the generalized Steiner forest problem. In this problem, we are given a connected graph $$G =(V,E)$$
with non-negative costs $$c_{e}$$
for the edges $$e\in E$$
, a set of disjoint vertex sets $${\mathcal {V}}=\{V_{1},V_{2},\ldots ,V_{l}\}$$
and a parameter $$k\le l$$
. The goal is to find a minimum-cost edge set $$F\subseteq E$$
that connects at least k vertex sets in $${\mathcal {V}}$$
. Our main work is to construct an $$O(\sqrt{l})$$
-approximation algorithm for the k-GSF problem based on a greedy approach and an LP-rounding technique.
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
17
References
0
Citations
NaN
KQI