Wednesday, October 14, 2015 - 12:00pm to 1:00pm
Location:ASA Conference Room 6115 - Moved to 8102 Gates&Hillman Centers
Speaker:JAKUB PACHOCKI, Ph.D. Student /JAKUB%20PACHOCKI
For More Information, Contact:deb @ cs.cmu.edu
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 are 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.