Facility location with red-blue demands

Abstract

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.