Campus Event Calendar
Event Entry
What and Who
MINI-COURSE ON APPROXIMATION ALGORITHMS
Zeev Nutov
Max-Planck-Institut für Informatik - AG 1
AG1 Advanced Mini-Course
AG 1, AG 2
AG Audience
English
Note: We use this to send email in the morning.
Date, Time and Location
Thursday, 17 February 2000
13:30
90 Minutes
MPI
024
Saarbrücken
Abstract
In the minimum multicut problem one is given a set of $k$ pairs of nodes
and the aim is to find a minimum capacity cut that separates every pair.
This problem is a natural generalization of the minimum (s,t)-cut problem.
I will present an $O(log k)$-approximation algorithm due to Garg, Vazirani & Yanakakis.
Contact
Zeev Nutov
--email hidden
passcode not visible
logged in users only