Fall 2017

The Non-Uniform k-Center Problem

Wednesday, September 13th, 2017 3:30 pm4:00 pm

Add to Calendar

Given a finite metric space, the usual k-center problem asks where to place the centers of k unit radius "inflatable" balls such that they cover all the points of the space with as small dilation as possible. This problem has been well understood for more than 3 decades. In this talk we will look at the same question when the balls have different radii. I will try to convince you that this is a natural generalization to study; in particular it generalizes the problem with outliers. Technically, one interesting aspect will be connections to the so-called "firefighter" problem.

Joint work with Prachi Goyal and Ravishankar Krishnaswamy

PDF icon The Non-Uniform k-Center Problem632.51 KB