Online citations, reference lists, and bibliographies.

Greedy Algorithms For The On-Line Steiner Tree And Generalized Steiner Problems

J. Westbrook, Dicky C. K. Yan
Published 1993 · Computer Science

Cite This
Download PDF
Analyze on Scholarcy
Share
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.



This paper is referenced by
Delay-Constrained Routing in Connection-OrientedNetworksA Project
S. R. Murthy (1998)
Towards Design of System Hierarchy (research survey)
Mark Sh. Levin (2012)
10.1006/jagm.1998.0924
Distributed paging for general networks
B. Awerbuch (1996)
10.1016/S0890-5401(03)00055-5
Competitive distributed file allocation
B. Awerbuch (2003)
Capítulo 8 – Árvore de steiner
Marco César Goldbarg (2012)
10.1109/90.793020
A rearrangeable algorithm for the construction delay-constrained dynamic multicast trees
S. Raghavan (1999)
10.1109/SUTC.2006.59
Distributed Steiner-Like Multicast Path Setup for Mesh-based Multicast Routing in Ad Hoc Networks
I. I. Er (2006)
10.1007/978-1-4614-0311-1
Mathematical Aspects of Network Routing Optimization
Carlos A. S. Oliveira (2011)
10.1007/BFb0029573
On-line Network Optimization Problems
Bala Kalyanasundaram (1996)
10.1145/258533.258618
On-line algorithms for Steiner tree problems (extended abstract)
P. Berman (1997)
Optimization problems in telecommunications and the internet
C. Oliveira (2004)
10.18419/opus-3144
Konzeption und Implementierung eines OpenFlow-basierten IP-Multicast-Dienstes für Datenzentren
Jonas Danzl (2013)
Hybrid multicasting using Automatic Multicast Tunnels (AMT)
Dhaifallah Alwadani (2017)
10.1016/j.comnet.2006.03.005
On-line multicast routing with QoS constraints in WDM networks with no wavelength converters
N. Rammohan (2006)
Multicast routing in point-to-point networks under constraints
A. Varma (1996)
10.1016/j.cor.2003.12.007
A survey of combinatorial optimization problems in multicast routing
C. Oliveira (2005)
10.1109/90.490746
Distributed algorithms for multicast path setup in data networks
F. Bauer (1996)
10.1142/S0129054102001527
The Effect of Asymmetry on the On-Line Multicast Routing Problem
M. Faloutsos (2002)
3 Scientific Information 3.1 Summary 3.2 Rationale for the Proposed Project and State of Research 3.2.1 Rationale
()
10.1007/BFb0049409
On-Line Distributed Data Management
Carsten Lund (1994)
10.1109/TIT.2006.874523
Minimum-cost multicast over coded packet networks
D. Lun (2006)
On the Maintenance of Low Cost Multicast Trees with Bandwidth Reservation
D. Cavendish (1999)
10.1016/j.tcs.2004.05.021
On-line generalized Steiner problem
B. Awerbuch (1996)
10.1134/S0005117909030187
Combinatorial optimization in system configuration design
Mark Sh. Levin (2009)
10.1109/49.564136
ARIES: A Rearrangeable Inexpensive Edge-Based On-Line Steiner Algorithm
F. Bauer (1997)
10.1007/3-540-46784-X_2
Invited Lecture: Online Algorithms: A Study of Graph-Theoretic Concepts
S. Albers (1999)
Semantic Scholar Logo Some data provided by SemanticScholar