Geometric Median

October 14, 2015

The geometric median of a set of points is the point minimizing the sum of distances to the points. The problem of finding an efficient algorithm to compute the median, known as the Fermat-Weber problem, has remained an active area of research for many years. In this talk we present the first linear-time algorithm for computing the median, and the first optimal algorithm for approximating the median.

*Joint work with Yin Tat Lee, Gary Miller and Aaron Sidford.*

*
Presented in Partial Fulfillment of the CSD Speaking Skills Requirement.
*