"Local Search" Algorithms for Facility Location Problems
- Series
- ACO Student Seminar
- Time
- Wednesday, March 31, 2010 - 13:30 for 1 hour (actually 50 minutes)
- Location
- ISyE Executive Classroom
- Speaker
- Anand Louis – CS ACO, Georgia Tech
Local search is one of the oldest known optimization techniques. It has
been studied extensively by Newton, Euler, etc. It is known that this
technique gives the optimum solution if the function being optimized is
concave(maximization) or convex (minimization). However, in the general
case it may only produce a "locally optimum" solution. We study how to
use this technique for a class of facility location problems and give
the currently best known approximation guarantees for the problem and a
matching "locality gap".