Algorithms Seminar

On Metric Multicovering Problems

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


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 write-up can be found at This is joint work with my PhD students Santanu Bhowmick and Tanmay Inamdar.


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.