J.P. Locquet, J. Perret, et al.
SPIE Optical Science, Engineering, and Instrumentation 1998
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.
J.P. Locquet, J. Perret, et al.
SPIE Optical Science, Engineering, and Instrumentation 1998
David Cash, Dennis Hofheinz, et al.
Journal of Cryptology
Y.Y. Li, K.S. Leung, et al.
J Combin Optim
David W. Jacobs, Daphna Weinshall, et al.
IEEE Transactions on Pattern Analysis and Machine Intelligence