Title: Geometric Optimization with Violations.

Speaker: Jeff Phillips

Abstract:

I can present the basic argument of a paper by Matousek on how to solve a class of problems 
called LP-type problems with up to k violations in O(n k^d) time.  d is the inherent 
dimension of the problem and assumed to be small.  Naive bounds are O(n d^k), so this is 
nice.  A classic example is: for a point set of size n, find a circle that contains all 
but k points.  This takes O(n k^3) time.  For d small (i.e. <= 4) there are smaller bounds
in terms of n, but these include complicated data structures that I probably won't want
to talk about.