Ruixiong Tian, Zhe Xiang, et al.
Qinghua Daxue Xuebao/Journal of Tsinghua University
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.
Ruixiong Tian, Zhe Xiang, et al.
Qinghua Daxue Xuebao/Journal of Tsinghua University
Timothy J. Wiltshire, Joseph P. Kirk, et al.
SPIE Advanced Lithography 1998
David W. Jacobs, Daphna Weinshall, et al.
IEEE Transactions on Pattern Analysis and Machine Intelligence
W.C. Tang, H. Rosen, et al.
SPIE Optics, Electro-Optics, and Laser Applications in Science and Engineering 1991