Campus Event Calendar
Event Entry
What and Who
Approximation Algorithms via Iterative Rounding
Piotr Krysta
Max-Planck-Institut für Informatik, Saarbrücken, Germany
Seminar des Graduiertenkollegs
AG 1, AG 2
AG Audience
English
Note: We use this to send email in the morning.
Date, Time and Location
Monday, 25 January 99
16:00
-- Not specified --
45
015
Saarbrücken
Abstract
I will talk about a new technique for designing approximation algorithms,
called iterative rounding. It was introduced in a FOCS 98 paper by Kamal Jain.
We consider an LP relaxation for a given problem P. We then solve LP optimally,
producing an aptimal basic solution, say [0,1]-vector x. Now, a key idea is
that if we can prove that there is a component of x of value at least 1/2, then
rounding this component to 1, i.e. including the component into our integral
solution, incorporates by a factor of 2 to our solution estimation.
This technique has been used for the Survivable Network Design problem, giving
a first constant factor 2-approximation algorithm.
called iterative rounding. It was introduced in a FOCS 98 paper by Kamal Jain.
We consider an LP relaxation for a given problem P. We then solve LP optimally,
producing an aptimal basic solution, say [0,1]-vector x. Now, a key idea is
that if we can prove that there is a component of x of value at least 1/2, then
rounding this component to 1, i.e. including the component into our integral
solution, incorporates by a factor of 2 to our solution estimation.
This technique has been used for the Survivable Network Design problem, giving
a first constant factor 2-approximation algorithm.
Contact
Ülkü Coruh
0681/9325-526
--email hidden
passcode not visible
logged in users only