Title: Constructing $\epsilon$-approximations.
Speaker: Yuriy Mileyko

Abstract:
Given a set of points in some space and a collection of sets, it is often useful to find a subset of the 
given points such that its distribution relative to the set collection is 'approximately' the same as the 
distribution of the whole set. For example, suppose we want to know how many people live within 5 miles 
from a liquor store. In order to aswer this question, we wouldn't even consider asking everybody; in fact, 
we probably would just pick a 'large enough' sample of people for our inquiry and then say that the 
resulting number is 'close' to the actual one. Such a sample represents an $\epsilon$-approximation, where 
$\epsilon$ denotes the resulting relative error. Interestingly, the 'large enough' part does not depent on 
the population size, only on the relative error.
In this talk, I will give a formal definition of an $\epsilon$-approximation and discuss several 
algorithms for constructing $\epsilon$-approximations for a given set system. If time permits, I will also 
go over some applications.