Max-Planck-Institut für Informatik
max planck institut
informatik
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
Language:English
Date, Time and Location
Date:Tuesday, 17 November 2009
Time:13:00
Duration:30 Minutes
Location:Saarbrücken
Building:E1 4
Room:024
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
Name(s):Spyros Angelopoulos
Video Broadcast
Video Broadcast:NoTo Location:
Tags, Category, Keywords and additional notes
Note:
Attachments, File(s):
  • Spyros Angelopoulos, 11/11/2009 07:08 PM
  • Spyros Angelopoulos, 11/11/2009 07:07 PM -- Created document.