Max-Planck-Institut für Informatik
max planck institut
mpii logo Minerva of the Max Planck Society

MPI-INF or MPI-SWS or Local Campus Event Calendar

New for: D3
<< Previous Entry Next Entry >> New Event Entry Edit this Entry Login to DB (to update, delete)
What and Who
Title:Parameterized competitive analysis of online Steiner tree problems
Speaker:Spyros Angelopoulos
coming from:Max-Planck-Institut für Informatik - D1
Speakers Bio:
Event Type:AG1 Mittagsseminar (own work)
Visibility:D1, D4, RG1, MMCI, D3, D5, SWS
We use this to send out email in the morning.
Level:AG Audience
Date, Time and Location
Date:Tuesday, 17 November 2009
Duration:30 Minutes
Building:E1 4
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.

Name(s):Spyros Angelopoulos
Video Broadcast
Video Broadcast:NoTo Location:
Tags, Category, Keywords and additional notes
Attachments, File(s):
  • Spyros Angelopoulos, 11/11/2009 07:08 PM
  • Spyros Angelopoulos, 11/11/2009 07:07 PM -- Created document.