"Local Search" Algorithms for Facility Location Problems

ACO Student Seminar
Wednesday, March 31, 2010 - 13:30
1 hour (actually 50 minutes)
ISyE Executive Classroom
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".