License
when quoting this document, please refer to the following
URN: urn:nbn:de:0030-drops-21210
URL: http://drops.dagstuhl.de/opus/volltexte/2009/2121/
Angelopoulos, Spyros

Parameterized Analysis of Online Steiner Tree Problems

pdf-format:
Dokument 1.pdf (172 KB)

Abstract

Steiner tree problems occupy a central place in both areas of approximation and on-line algorithms. Many variants have been studied from the point of view of competitive analysis, and for several of these variants tight bounds are known. However, in several cases, worst-case analysis is overly pessimistic, which fails to explain the relative performance of algorithms. We show how adaptive analysis can help resolve this problem. As case studies, we consider the Steiner tree problem in directed graphs, and the Priority Steiner tree problem.

BibTeX - Entry

@InProceedings{angelopoulos:DSP:2009:2121,
  author =	{Spyros Angelopoulos},
  title =	{Parameterized Analysis of Online Steiner Tree Problems},
  booktitle =	{Adaptive, Output Sensitive, Online and Parameterized Algorithms},
  year =	{2009},
  editor =	{J{\'e}r{\'e}my Barbay and Rolf Klein and Alejandro Ortiz-L{\'o}pez and Rolf Niedermeier},
  number =	{09171},
  series =	{Dagstuhl Seminar Proceedings},
  ISSN =	{1862-4405},
  publisher =	{Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2009/2121},
  annote =	{Keywords: Online algorithms, Steiner tree problems, adaptive and parameteried analysis}
}

Keywords: Online algorithms, Steiner tree problems, adaptive and parameteried analysis
Seminar: 09171 - Adaptive, Output Sensitive, Online and Parameterized Algorithms
Issue date: 2009
Date of publication: 31.07.2009

DROPS-Home | Fulltext Search | Imprint Published by LZI