Campus Event Calendar
Event Entry
What and Who
Approximation algorithms reading group
Spyros Angelopoulos
Max-Planck-Institut für Informatik - D1
Lecture
AG 1
AG Audience
English
Note: We use this to send email in the morning.
Date, Time and Location
Thursday, 28 February 2008
14:30
-- Not specified --
E1 4
Rotunda 3rd floor
Saarbrücken
Abstract
I will present the main ideas of the paper "A General Approach to Online
Network Optimization Problems" by Alon et al. (SODA 2004)
The paper introduces a framework for maintaining fractional solutions for
online cut/connectiity problems, with competitive
ratio logarithmic in the number of edges in the graph. As a next step, one
typically performs a rounding of the fractional
solutions to integral ones, again in an online manner. I will illustrate
how the authors apply the framework to some
well known optimization problems.
Contact
Khaled Elbassioni
--email hidden
passcode not visible
logged in users only
Khaled Elbassioni, 02/27/2008 16:00 -- Created document.