Abstract
We study the on-line Steiner tree problem on a general metric space. We show that a class of greedy on-line algorithms are O(log(d/zs))-competitive and no deterministic algorithm is better than Ω(log(d/zs))-competitive, where s is the number of regular nodes, d the maximum metric distance between any two revealed nodes and z the optimal off-line cost. Our results refine the previous known bound [8] and show that Algorithm SB of Bartal et al. [4] for the on-line File Allocation problem is O(log log N)-competitive on an N-node hypercube or butterfly network.
We consider the on-line generalized Steiner problem on a general metric space. We show that a class of lazy and greedy on-line algorithms are O(√k · log k)-competitive and no on-line algorithms is better than Ω(log k)-competitive, where k is the number of distinct nodes that appear in the request sequence. These are the first algorithms for this problem.
Research partially supported by NSF Grant CCR-9009753.
Research partially supported by NSF Grant DDM-8909660 and a University Fellowship from the Graduate School, Yale University.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
References
N. Alon and Y. Azar, On-Line Steiner Trees in the Euclidean Plane, Proceedings of the 8th Symposium of Computational Geometry, Berlin, 1992.
A. Agrawal, P. Klein and R. Ravi, When Trees Collide: An Approximation Algorithm for the Generalized Steiner Problem in Networks, Proceedings of the 23rd ACM Symposium on Theory of Computing, (1991) 134–144.
B. Awerbuch, Y. Bartal and A. Fiat, Competitive Distributed File Allocation, To appear, 25th ACM Symposium on Theory of Computing, 1993.
Y. Bartal, A. Fiat, and Y. Rabani, Competitive Algorithms for Distributed Data Management, Proceedings of the 24th Annual ACM Symposium on the Theory of Computing, (1992) 39–50.
S. Ben-David, A. Borodin, R. Karp, G. Tardos and A. Wigderson, On the Power of Randomization in Online Algorithms, Proceedings of the 22nd ACM Symposium on Theory of Computing, (1990) 379–386.
F. R. K, Chung and R. L. Graham, On Steiner Trees for Bounded Point Sets, Geometrias Dedicata, 11 (1981) 353–361.
M. Hannan, On Steiner's Problem with Rectilinear Distance, SIAM J. App. Maths., 14 (1966), 255–265.
M. Imaze, and B. M. Waxman, Dynamic Steiner Tree Problem, SIAM J. Disc. Math., 4(3) (1991) 369–384.
R. M. Karp, Reducibility among combinatorial problems, in R. E. Miller and J. W. Thatcher (eds.), Complexity of Computer Computations, Plenum Press, New York, 85–103.
N. Maculan, The Steiner Problem in Graphs, Ann. Dis. Maths., 31 (1987) 185–212.
L. Nastansky, S. M. Selkow, N. F. Stewart, Cost-Minimal Trees in Directed Acyclic Graphs, Zeitschrift für Operations Research, 18 (1974), 59–67.
J. Westbrook and D. C. K. Yan, The Performance of Greedy Algorithms for the On-Line Steiner Tree and Related Problems, Technical Report YALEU/DCS/TR-911, Yale University, November, 1992.
P. Winter, Steiner Problem in Networks: A Survey, Networks, 17 (1987) 129–167.
O. Wolfson and A. Milo, The Multicast Policy and Its Relationship to Replicated Data Placement, ACM Trans. Database Syst., 16(1) (1991) 181–205.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1993 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Westbrook, J., Yan, D.C.K. (1993). Greedy algorithms for the on-line steiner tree and generalized steiner problems. In: Dehne, F., Sack, JR., Santoro, N., Whitesides, S. (eds) Algorithms and Data Structures. WADS 1993. Lecture Notes in Computer Science, vol 709. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-57155-8_285
Download citation
DOI: https://doi.org/10.1007/3-540-57155-8_285
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-57155-1
Online ISBN: 978-3-540-47918-5
eBook Packages: Springer Book Archive