Campus Event Calendar
Event Entry
New for: D3
What and Who
Local Search Heuristics for the k-median problem
Rohit Khandekar
Indian Institute of Technology, New Delhi
AG1 Mittagsseminar (own work)
AG 1, AG 2, AG 3, AG 4
AG Audience
English
Note: We use this to send email in the morning.
Date, Time and Location
Friday, 25 May 2001
13:30
45 Minutes
MPI 46.1
024
Saarbrücken
Abstract
Given a set of n cities we wish to locate service-centers in
k of these n cities so that the total distance of the cities to the
nearest service-center is minimised. The talk will discuss a simple
swap heursitic for this problem and show that this heursitic leads to
a 5-approximation algorithm. A generalization of this heursitic leads
to improved performance guarantees approaching 3.
The talk will assume no background knowledge.
Contact
Edgar A. Ramos
--email hidden
passcode not visible
logged in users only
Tags, Category, Keywords and additional notes
Approximation Algorithms , Facility location, Local Search