Campus Event Calendar
Event Entry
What and Who
Approximation Algorithms Reading Group
Naveen Garg
Max-Planck-Institut für Informatik - D 1
Talk
AG 1, AG 2, AG 3, AG 4, AG 5, SWS
AG Audience
English
Note: We use this to send email in the morning.
Date, Time and Location
Thursday, 26 October 2006
14:30
-- Not specified --
E1 4
Rotunda on 3rd floor
Saarbrücken
Abstract
Topic: Oblivious routing in general networks.
A surprising result due to Racke shows that every network has an oblivious routing scheme such that the congestion incurred on any edge when demands are routed according to this scheme, is no more than log3 n times the optimum congestion for these set of demands.
Racke's original construction ran in exponential time. In a subsequent paper the construction is made polynomial time with a slight worsening of the guarantee to log^4n. The proofs are also simplified.
The guarantee is improved to log^2n loglog n in a later paper.
Contact
Naveen Garg
--email hidden
passcode not visible
logged in users only
Tags, Category, Keywords and additional notes
Naveen Garg, 10/20/2006 12:30 -- Created document.