Campus Event Calendar
Event Entry
What and Who
Approximation algorithms reading group
Julian Mestre
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, 7 February 2008
14:30
-- Not specified --
E1 4
Rotunda 3rd floor
Saarbrücken
Abstract
Ttitle: Dual fitting and factor revealing programs
Abstract:
Dual fitting is a general technique for analyzing heuristics. The idea is
to construct a non-feasible dual solution with enough cost to pay for the
primal solution; then this dual solution is scaled down by a r factor to
make it feasible. The best (i.e., smallest) possible value for r is found
via a factor revealing program.
I'll show how this ideas can be applied to the analysis of a greedy
algorithm for the cycle cover problem.
Reference: "Cycle Cover with Short Cycles" by Immorlica, Mahdian, and
Mirrokni. (STACS 05)
Contact
Khaled Elbassioni
--email hidden
passcode not visible
logged in users only
Khaled Elbassioni, 02/06/2008 12:25 -- Created document.