Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop


Show entries of:

this year (2019) | last year (2018) | two years ago (2017) | Notes URL

Action:

login to update

Options:








Author, Editor

Author(s):

Angelopoulos, Spyros

dblp



Editor(s):





BibTeX cite key*:

Angelopoulos2007SODA1

Title, Booktitle

Title*:

Improved bounds for the online steiner tree problem in graphs of bounded edge-asymmetry

Booktitle*:

Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2007

Event, URLs

URL of the conference:

http://www.siam.org/meetings/da07/

URL for downloading the paper:

http://portal.acm.org/citation.cfm?doid=1283383.1283410

Event Address*:

New Orleans, Louisiana, USA

Language:

English

Event Date*
(no longer used):


Organization:

Association for Computing Machinery (ACM) and Society for Industrial and Applied Mathematics (SIAM)

Event Start Date:

7 January 2008

Event End Date:

9 January 2008

Publisher

Name*:

SIAM

URL:

http://www.siam.org

Address*:

Philadelphia, USA

Type:


Vol, No, Year, pp.

Series:


Volume:


Number:


Month:

January

Pages:

248-257

Year*:

2007

VG Wort Pages:


ISBN/ISSN:


Sequence Number:


DOI:




Note, Abstract, ©


(LaTeX) Abstract:

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 ε.

URL for the Abstract:

http://portal.acm.org/citation.cfm?doid=1283383.1283410

Keywords:

Online Algorithms, Steiner Tree Problem

HyperLinks / References / URLs:

http://portal.acm.org/citation.cfm?doid=1283383.1283410



Download
Access Level:

Public

Correlation

MPG Unit:

Max-Planck-Institut für Informatik



MPG Subunit:

Algorithms and Complexity Group

Audience:

popular

Appearance:

MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort



BibTeX Entry:

@INPROCEEDINGS{Angelopoulos2007SODA1,
AUTHOR = {Angelopoulos, Spyros},
TITLE = {Improved bounds for the online steiner tree problem in graphs of bounded edge-asymmetry},
BOOKTITLE = {Proceedings of the Eighteenth Annual {ACM}-{SIAM} Symposium on Discrete Algorithms, {SODA} 2007},
PUBLISHER = {SIAM},
YEAR = {2007},
ORGANIZATION = {Association for Computing Machinery (ACM) and Society for Industrial and Applied Mathematics (SIAM)},
PAGES = {248--257},
ADDRESS = {New Orleans, Louisiana, USA},
MONTH = {January},
}


Entry last modified by Spyros Angelopoulos, 03/20/2009
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
Spyros Angelopoulos
Created
01/18/2008 02:11:10 PM
Revisions
3.
2.
1.
0.
Editor(s)
Spyros Angelopoulos
Uwe Brahm
Anja Becker
Spyros Angelopoulos
Edit Dates
03/20/2009 04:03:15 PM
01/20/2009 07:09:56 PM
06.03.2008 14:27:22
01/18/2008 02:11:10 PM
Show details for Attachment SectionAttachment Section
Hide details for Attachment SectionAttachment Section