Algorithms Seminar
On Metric Multicovering Problems
Speaker:  Kasturi Varadarajan

Date: 
Thursday, November 10, 2016 
Time: 
12:00pm  1:00pm 
Location: 
D344 LSRC, Duke 


Abstract
We are given a set of clients and servers, whose locations are points in
some metric space. Each client specifies an integer that indicates how
many servers it needs coverage from. Each server can provide one unit of
coverage to all clients within a ball centered at the server; we are
allowed to choose the radius of this ball arbitrarily, but the cost we
will incur is proportional to the radius of the ball. The goal is to
provide the required coverage to the clients while minimizing the sum of
the costs of the server balls.
We present a method that reduces such multicovering problems to several
instances of regular covering, where the coverage demand of each client
is one. Using this reduction, we incur an overhead that is at most a
multiplicative constant of the cost of the optimal multicover.
A preliminary writeup can be found at https://arxiv.org/abs/1602.04152
This is joint work with my PhD students Santanu Bhowmick and Tanmay Inamdar.
Biography
Kasturi Varadarajan is a Professor of Computer Science at the University of Iowa. He works in various areas of theoretical computer science including computational geometry, combinatorial optimization on graphs, and polynomial time computability of equilibria in games and economic models.