On Metric Multicovering Problems
||Thursday, November 10, 2016
||12:00pm - 1:00pm
||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 https://arxiv.org/abs/1602.04152
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.