## תקציר

The DB-GST problem is given an undirected graph G(V,E), and a collection of groups S={S_{i}}_{i=1}^{q},S_{i}⊆V, find a tree that contains at least one vertex from every group S_{i}, so that the maximum degree is minimal. This problem was motivated by On-Line algorithms Hajiaghayi (2016), and has applications in VLSI design and fast Broadcasting. In the WDB-GST problem, every vertex v has individual degree bound d_{v}, and every e∈E has a cost c(e)>0. The goal is, to find a tree that contains at least one terminal from every group, so that for every v, deg_{T}(v)≤d_{v}, and among such trees, find the one with minimum cost. We give the first approximation for this problem, an (O(log^{2}n),O(log^{2}n)) bicriteria approximation ratio the WDB-GST problem on trees inputs. This implies an O(log^{2}n) approximation for DB-GST on tree inputs. The previously best known ratio for the WDB-GST problem on trees was a bicriterion (O(log^{2}n),O(log^{3}n)) (the approximation for the degrees is O(log^{3}n)) ratio which is folklore. Getting O(log^{2}n) approximation requires careful case analysis and was not known. Our result for WDB-GST generalizes the classic result of Garg et al. (2016) that approximated the cost within O(log^{2}n), but did not approximate the degree. Our main result is an O(log^{3}n) approximation for BD-GST on Bounded Treewidth graphs. The DB-Steiner k-tree problem is given an undirected graph G(V,E), a collection of terminals S⊆V, and a number k, find a tree T(V^{′},E^{′}) that contains at least k terminals, of minimum maximum degree. We prove that if the DB-GST problem admits a ρ ratio approximation, then the DB-Steiner k-tree problem, admits an O(log^{2}k⋅ρ) expected approximation. We also show that if there are k groups, there exists an algorithm that is able to coverk/4 of the groups with minimum maximal degree, then there is a deterministic O(logn⋅ρ) approximation for DB-Steiner k-tree problem. Using the work of Guo et al. (2020) we derive an O(log^{3}n) approximation for DB-Steiner k-tree problem on general graphs, that runs in quasi-polynomial time.

שפה מקורית | אנגלית |
---|---|

עמודים (מ-עד) | 229-239 |

מספר עמודים | 11 |

כתב עת | Discrete Applied Mathematics |

כרך | 309 |

מזהי עצם דיגיטלי (DOIs) | |

סטטוס פרסום | פורסם - 15 מרץ 2022 |

### הערה ביבליוגרפית

Publisher Copyright:© 2021