Seminar by Prof. Naveen Garg
A local search algorithm for the k-median problem
Prof. Naveen Garg
Department of Computer Science and Engineering
Indian Institute of Technology Delhi
New Delhi, India
Date: Thursday, November 13, 2003
Time: 3:30 PM
Venue: CS-101
Abstract
Local search is typically the heuristic of choice for solving many hard combinatorial optimization problems. However, its only for a few problems that researchers have been able to prove good worst case bounds on the performance of local search. In this talk I will present a local search algorithm for the k-median problem and argue that it always gives a solution which is within 5 times the optimum; further, this bound is tight. The k-median problem is a facility location problem in which one has to locate at most k facilities in a manner so that the total distance traveled by a client to reach the nearest facility is minimized.