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
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)
Distributed paging for general networks
B. Awerbuch (1996)
Competitive distributed file allocation
B. Awerbuch (2003)
Capítulo 8 – Árvore de steiner
Marco César Goldbarg (2012)
A rearrangeable algorithm for the construction delay-constrained dynamic multicast trees
S. Raghavan (1999)
Distributed Steiner-Like Multicast Path Setup for Mesh-based Multicast Routing in Ad Hoc Networks
I. I. Er (2006)
Mathematical Aspects of Network Routing Optimization
Carlos A. S. Oliveira (2011)
On-line Network Optimization Problems
Bala Kalyanasundaram (1996)
On-line algorithms for Steiner tree problems (extended abstract)
P. Berman (1997)
Optimization problems in telecommunications and the internet
C. Oliveira (2004)
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)
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)
A survey of combinatorial optimization problems in multicast routing
C. Oliveira (2005)
Distributed algorithms for multicast path setup in data networks
F. Bauer (1996)
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
On-Line Distributed Data Management
Carsten Lund (1994)
Minimum-cost multicast over coded packet networks
D. Lun (2006)
On the Maintenance of Low Cost Multicast Trees with Bandwidth Reservation
D. Cavendish (1999)
On-line generalized Steiner problem
B. Awerbuch (1996)
Combinatorial optimization in system configuration design
Mark Sh. Levin (2009)
ARIES: A Rearrangeable Inexpensive Edge-Based On-Line Steiner Algorithm
F. Bauer (1997)
Invited Lecture: Online Algorithms: A Study of Graph-Theoretic Concepts
S. Albers (1999)
Semantic Scholar Logo Some data provided by SemanticScholar