Campus Event Calendar
Event Entry
What and Who
Flows on Few Paths: Algorithms and Lower Bounds
Maren Martens
Max-Planck-Institut für Informatik - AG 1
AG1 Mittagsseminar (own work)
AG 1, AG 2, AG 3, AG 4, AG 5
AG Audience
English
Note: We use this to send email in the morning.
Date, Time and Location
Wednesday, 7 July 2004
13:00
30 Minutes
46.1 - MPII
024
Saarbrücken
Abstract
The talk will be about algorithms for the unsplittable flow problem and its generalization the k-splittable flow problem where the number of paths used by a commodity is bounded by k. For the unsplittable flow problem I will prove a lower bound on the performance of randomized rounding. Furthermore I will give approximation algorithms for the k-splittable flow problem with additional constraints on the amount of flow being sent along each path.
Contact
Maren Martens
--email hidden
passcode not visible
logged in users only
Tags, Category, Keywords and additional notes
network flows
Maren Martens, 05/18/2004 17:54 -- Created document.