Fausto Bernardini, Holly Rushmeier
Proceedings of SPIE - The International Society for Optical Engineering
Facility location and data placement problems have been widely studied. Consider the following problem. We are given a set of facilities F and a set of clients D in a metric space. There are two types of objects. A client may have demand for each of the object types. A facility can be opened for one or both types depending on its storage capacity; there are no facility opening costs. The goal is to determine the facilities to open for each type while respecting their storage capacity constraints and assign every demand to a facility open for its type. We present a 4-approximation LP-rounding based algorithm for this problem.
Fausto Bernardini, Holly Rushmeier
Proceedings of SPIE - The International Society for Optical Engineering
George Markowsky
J. Math. Anal. Appl.
Matthew A Grayson
Journal of Complexity
Naga Ayachitula, Melissa Buco, et al.
SCC 2007