Title:Local Search Guarantees on Facility Location Problems
|Affiliation:||University of Waterloo|
Abstract: We will show that guarantees can be given on algorithms for the k-median problem based on local search heuristics. With single swaps, a (5 + epsilon)-approximation can be achieved, and with multiple swaps, a (3+2/p)-approximation. We will prove that such algorithms run in polynomial time and that similar techniques can be applied to the metric uncapacitated facility location problem.
200 University Avenue West
Waterloo, ON N2L 3G1