Non-Greedy Online Steiner Trees on Outerplanar Graphs
- PDF / 2,039,883 Bytes
- 28 Pages / 439.37 x 666.142 pts Page_size
- 89 Downloads / 180 Views
Non‑Greedy Online Steiner Trees on Outerplanar Graphs Akira Matsubayashi1 Received: 30 August 2017 / Accepted: 12 September 2020 © Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract This paper addresses the classic online Steiner tree problem on edge-weighted graphs. It is known that a greedy (nearest neighbor) online algorithm has a tight competitive ratio for wide classes of graphs, such as trees, rings, any class including series-parallel graphs, and unweighted graphs with bounded diameter. However, we do not know any greedy or non-greedy tight deterministic algorithm for other classes of graphs. In this paper, we observe that a greedy algorithm is Ω(log n)-competitive on outerplanar graphs, where n is the number of vertices, and propose a 5.828-competitive deterministic algorithm on outerplanar graphs. Our algorithm connects a requested vertex and the tree constructed thus far using a path that is constant times longer than the distance between them. We also present a lower bound of 4 for arbitrary deterministic online Steiner tree algorithms on outerplanar graphs. Keywords Steiner tree · Online algorithm · Competitive analysis · Outerplanar graph
1 Introduction This paper addresses the classic online Steiner tree problem (STP) on edge-weighted graphs. We are given a graph G = (VG , EG ) with non-negative edge-weights w ∶ EG → ℝ+ and a subset R of vertices of G. The (offline) Steiner tree problem is to find a Steiner tree, i.e., a subtree T = (VT , ET ) of G that contains all the vertices in R ∑ and minimizes its cost e∈ET w(e) . In the online version of this problem, vertices r1 , ..., r|R| ∈ R are revealed one by one, and for each i ≥ 1 , we must construct a tree containing ri by growing the constructed tree for r1 , ..., ri−1 (null tree for i = 1 ) without information of ri+1 , ..., r|R|. A preliminary version appeared in the proceedings of the 14th International Workshop on Approximation and Online Algorithms (WAOA 2016). * Akira Matsubayashi [email protected]‑u.ac.jp 1
Division of Electrical Engineering and Computer Science, Kanazawa Univ., Kanazawa 920‑1192, Japan
13
Vol.:(0123456789)
Algorithmica
Imase and Waxman [13] proposed a greedy (nearest neighbor) online algorithm that is O(log n)-competitive on arbitrary graphs with n vertices. They also proved that any deterministic algorithm is Ω(log n)-competitive even on series-parallel graphs [13]. Westbrook and Yan [16] refined these upper and lower bounds to Θ(log(diam(G)|R|/opt)) with improving analysis, where diam(G) is the diameter of an underlying graph G, and opt is the cost of a minimum Steiner tree. The refined upper bound implies that the greedy algorithm is O(log diam(G))-competitive for an unweighted graph G. The greedy algorithm is trivially 1- and 2-competitive on trees and rings, respectively [7]. With these results, the greedy algorithm has a tight competitive ratio for trees, rings, any class of graphs including series-parallel graphs, and unweighted graphs with bounded diameter. However, we do not kno
Data Loading...
