Back to Search
Start Over
Combination Algorithms for Steiner Tree Variants.
- Source :
-
Algorithmica . Jan2023, Vol. 85 Issue 1, p153-169. 17p. - Publication Year :
- 2023
-
Abstract
- We give better approximation ratios for two Steiner Tree variants by combining known algorithms: the optimum 3 -decomposition and iterative randomized rounding. The first problem is Steiner Tree with minimum number of Steiner points and bounded edge length problem ( S M T - M S P ). The input consists of a set of terminals R in the Euclidean space R 2 . A feasible solution is a Steiner tree τ spanning R with Steiner points S such that every edge in τ has length at most 1 . The objective is to minimize S . Previously, the best approximation ratio for S M T - M S P was 1 + ln (4) + ϵ ≈ 2.386 . We present a polynomial time algorithm with ratio 2.277 . The second problem is Steiner Tree in quasi-bipartite graphs. It is a Steiner Tree problem on graph G = (V , E , c) with terminal set R when the edge set E does not include any edge between two vertices in V \ R . The best-known approximation ratio for this problem is 73 60 , We improve this ratio to 298 245 . [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 01784617
- Volume :
- 85
- Issue :
- 1
- Database :
- Academic Search Index
- Journal :
- Algorithmica
- Publication Type :
- Academic Journal
- Accession number :
- 161359790
- Full Text :
- https://doi.org/10.1007/s00453-022-01009-8