MPI-INF Logo
Campus Event Calendar

Event Entry

New for: D3

What and Who

Parameterized competitive analysis of online Steiner tree problems

Spyros Angelopoulos
Max-Planck-Institut für Informatik - D1
AG1 Mittagsseminar (own work)
AG 1, AG 4, RG1, MMCI, AG 3, AG 5, SWS  
AG Audience
English

Date, Time and Location

Tuesday, 17 November 2009
13:00
30 Minutes
E1 4
024
Saarbrücken

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, and fails to distinguish algorithms based on their anticipated relative performance.


We show how parameterized competitive analysis can help resolve this problem. As case studies, we consider the on-line variants of the Priority Steiner tree and the Euclidean Steiner tree problems, as well as the online Steiner tree problem in directed graphs.

Contact

Spyros Angelopoulos
--email hidden
passcode not visible
logged in users only

Spyros Angelopoulos, 11/11/2009 19:08
Spyros Angelopoulos, 11/11/2009 19:07 -- Created document.