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

<< Previous Entry Next Entry >> New Event Entry Edit this Entry Login to DB (to update, delete)
What and Who
Title:Greedy Algorithms for Steiner Forest
Speaker:Amit Kumar
coming from:IIT Delhi
Speakers Bio:
Event Type:AG1 Mittagsseminar (own work)
Visibility:D1, D2, D3, D4, D5, RG1, SWS, MMCI
We use this to send out email in the morning.
Level:AG Audience
Language:English
Date, Time and Location
Date:Tuesday, 9 June 2015
Time:13:00
Duration:30 Minutes
Location:Saarbr├╝cken
Building:E1 4
Room:024
Abstract
We consider the following simple algorithm for the Steiner forest problem: find the closest pair of terminals which have not been connected to their respective mates yet, and connect them by a shortest path. Contract the edges in this path and repeat this process till we get a feasible solution. We show that this is a constant factor approximation algorithm. We apply this result to obtain simple cost sharing schemes for the Steiner

forest problem.

This is joint work with Anupam Gupta.

Contact
Name(s):Andreas Wiese
EMail:awiese@mpi-inf.mpg.de
Video Broadcast
Video Broadcast:NoTo Location:
Tags, Category, Keywords and additional notes
Note:
Attachments, File(s):

Created by:Andreas Wiese, 05/21/2015 12:59 PMLast modified by:Uwe Brahm/MPII/DE, 11/24/2016 04:13 PM
  • Andreas Wiese, 05/27/2015 12:57 PM
  • Andreas Wiese, 05/21/2015 12:59 PM -- Created document.