Joint Theory Seminar/Computer Science Speaking Skills Talk

April 20, 2016  12:00PM—1:00PM

Location:
ASA Conference Room 6115 - Gates & Hillman Centers

Speaker:
GURU GURUGANESH, PH.D. Student
/GURU%20GURUGANESH

In the aversion k-clustering problem, given a metric space, we want to cluster the points into k clusters. The cost incurred by each point is the distance to the furthest point in its cluster, and the cost of the clustering is the sum of all these per-point-costs. This problem is motivated by questions in generating automatic abstractions of extensive-form games. We reduce this problem to a local k-median problem where each facility has a prescribed radius and can only connect to clients within that radius. Our main results are a constant-factor bicriteria approximation algorithm for the local k-median problem, and hence a constant-factor approximation algorithm for the aversion k-clustering problem. We use a primal-dual approach; our technical contribution is a non-local rounding step which we feel is of broader interest. Presented in Partial Fulfillment of the CSD Speaking Skills Requirement.

Add event to Google
Add event to iCal