Exact and Approximation Algorithms for Geometric and Capacitated Set Cover Problems with Applications

Piotr Berman, Marek Karpinski, Andrzej Lingas

First, we study geometric variants of the standard set cover motivated by assignment of directional antenna and shipping with deadlines, providing the first known polynomial-time e…