CombOpt Reading Group- Zishen Qu

Friday, October 26, 2018 1:00 pm - 1:00 pm EDT (GMT -04:00)

Title:Local Search Guarantees on Facility Location Problems

Speaker: Zishen Qu
Affiliation: University of Waterloo
Room: MC 5479

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.