[Colloquium] THEORY SEMINAR TODAY: Ankan Saha

[Katie Casey]

DEPARTMENT OF COMPUTER SCIENCE

UNIVERSITY OF CHICAGO

Date: Tuesday, November 30, 2010 
Time: 3:00 p.m.
Place: Ryerson 251, 1100 E. 58th Street

----------------------------------------------

Speaker:		Ankan Saha

From:		University of Chicago

Web page:	http://www.cs.uchicago.edu/people/ankans

Title: 		New Approximation Algorithms for Minimum Enclosing Shapes

Abstract:  	Given $n$ points in a $d$ dimensional Euclidean space, the Minimum Enclosing Ball (MEB) problem is to find the ball with the smallest radius which contains all $n$ points. We give two approximation algorithms for producing an enclosing ball whose radius is at most $\epsilon$ away from the optimum. The first requires $O(nd\mathcal{L}/sqrt{\epsilon})$ effort, where $\mathcal{L}$ is a constant that depends on the scaling of the data. The second is a $O^*(nd\mathcal{Q}/\sqrt{\epsilon})$ approximation algorithm, where $\mathcal{Q}$ is an upper bound on the norm of the points. For the Minimum Enclosing Convex Polytope (MECP) problem we give $O(mnd\mathcal{L}/\epsilon)$ and $O^*(mnd\mathcal{Q}/\epsilon)$ approximation algorithms, where $m$ is the number of faces of the
polytope. Our algorithms borrow heavily from convex duality and recently developed techniques in non-smooth optimization.

Joint work with SVN Vishwanathan and Xinhua Zhang.

Refreshments will be served prior to the talk at 2:30 in Ryerson 255.