Home News About Us Contact Contributors Disclaimer Privacy Policy Help FAQ

Home
Search
Quick Search
Advanced
Fulltext
Browse
Collections
Persons
My eDoc
Session History
Login
Name:
Password:
Documentation
Help
Support Wiki
Direct access to
document ID:


          Institute: MPI für Informatik     Collection: Algorithms and Complexity Group     Display Documents



ID: 356676.0, MPI für Informatik / Algorithms and Complexity Group
Improved bounds for the online steiner tree problem in graphs of bounded edge-asymmetry
Authors:Angelopoulos, Spyros
Language:English
Publisher:SIAM
Place of Publication:Philadelphia, USA
Date of Publication (YYYY-MM-DD):2007
Title of Proceedings:Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2007
Start Page:248
End Page:257
Place of Conference/Meeting:New Orleans, Louisiana, USA
(Start) Date of Conference/Meeting
 (YYYY-MM-DD):
2008-01-07
End Date of Conference/Meeting 
 (YYYY-MM-DD):
2008-01-09
Audience:Experts Only
Intended Educational Use:No
Abstract / Description:In this paper we consider the Online Steiner Tree problem in weighted directed
graphs of bounded edge-asymmetry α. The edge-asymmetry of a directed graph is
defined as the maximum ratio of the cost (weight) of antiparallel edges in the
graph. The problem has applications in multicast routing over a network with
non-symmetric links. We improve the previously known upper and lower bounds on
the competitive ratio of any deterministic algorithm due to Faloutsos et al. In
particular, we show that a better analysis of a simple greedy algorithm yields
a competitive ratio of O (min {k, α log k/log log α}), where k denotes the
number of terminals requested. On the negative side, we show a lower bound of Ω
(min{k1-ε, α log k/log log k}) on the competitive ratio of every deterministic
algorithm for the problem, for any arbitrarily small constant ε.
Last Change of the Resource (YYYY-MM-DD):2008-03-26
External Publication Status:published
Document Type:Conference-Paper
Communicated by:Kurt Mehlhorn
Affiliations:MPI für Informatik/Algorithms and Complexity Group
Identifiers:LOCALID:C12573CC004A8E26-EF04F0E72F2B7B32C12573D400486F40-...
The scope and number of records on eDoc is subject to the collection policies defined by each institute - see "info" button in the collection browse view.