MPI-INF Logo
Campus Event Calendar

Event Entry

What and Who

Greedy Algorithms for Steiner Forest

Amit Kumar
IIT Delhi
AG1 Mittagsseminar (own work)
AG 1, AG 2, AG 3, AG 4, AG 5, RG1, SWS, MMCI  
AG Audience
English

Date, Time and Location

Tuesday, 9 June 2015
13:00
30 Minutes
E1 4
024
Saarbrücken

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

Andreas Wiese
--email hidden
passcode not visible
logged in users only

Andreas Wiese, 05/27/2015 12:57
Andreas Wiese, 05/21/2015 12:59 -- Created document.