|Mittagsseminar Talk Information|
Date and Time: Tuesday, September 23, 2003, 12:15 pm
Duration: This information is not available in the database
Location: This information is not available in the database
Speaker: Vinayak Pandit (IBM India)
Local Search Heuristics for k-median, and facility location problems
The local search heuristics are very popular among practitioners in the area
of operations research, pattern recognitions, and related areas. Some of the
famous problems for which local search is a method of choice include
travelling salesman problem, k-median problem, and k-means clustering.
Unfortunately, most local search heuristics are not easy to analyse, and
prove properties about optimality, or worst case analysis. In this talk, we
present an analysis of the local search heuristics for the k-median problem.
Significantly, this analysis yields the best known approximation ratio for
k-median problem. In my talk, I will consider a simple local search
heuristic for the k-median problem, and prove that its local optimal is
at most 5 times more than the global optimal. Our analysis also works for
facility location problems.
Upcoming talks | All previous talks | Talks by speaker | Upcoming talks in iCal format (beta version!)
Previous talks by year: 2013 2012 2011 2010 2009 2008 2007 2006 2005 2004 2003 2002 2001 2000 1999 1998 1997 1996
Information for students and suggested topics for student talks
Automatic MiSe System Software Version 1.3392 | admin login