DIMACS Theoretical Computer Science Seminar

Title: Approximating k-Median via Pseudo-Approximation

Speaker: Shi Li, Princeton University

Date: Wednesday, April 24, 2013 11:00-12:00pm

Location: DIMACS Center, CoRE Bldg, Room 431, Rutgers University, Busch Campus, Piscataway, NJ


We present a novel approximation algorithm for $k$-median that achieves an approximation guarantee of $1+\sqrt{3}+\epsilon$, improving upon the decade-old ratio of $3+\epsilon$. Our approach is based on two components, each of which, we believe, is of independent interest.

First, we show that in order to give an $\alpha$-approximation algorithm for $k$-median, it is sufficient to give a {pseudo-approximation algorithm} that finds an $\alpha$-approximate solution by opening $k+O(1)$ facilities. This is a rather surprising result as there exist instances for which opening $k+1$ facilities may lead to a significant smaller cost than if only $k$ facilities were opened.

Second, we give such a pseudo-approximation algorithm with $\alpha=1+\sqrt{3}+\epsilon$. Prior to our work, it was not even known whether opening $k + o(k)$ facilities would help improve the approximation ratio.

See: http://paul.rutgers.edu/~yixinxu/theory-spring13.html