CombOpt Reading Group- Zishen Qu

Title:Local Search Guarantees on Facility Location Problems

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.