Facility location with matroid or knapsack constraints

Abstract

In the classical k-median problem, we are given a metric space and want to open k centers so as to minimize the sum (over all the vertices) of the distance of each vertex to its nearest open center. In this paper we present the first constant-factor approximation algorithms for two natural generalizations of this problem that handle matroid or knapsack constraints. In the matroid median problem, there is an underlying matroid on the vertices and the set of open centers is constrained to be independent in this matroid. When the matroid is uniform, we recover the k-median problem. Another previously studied special case is the red-blue median problem where we have a partition matroid with two parts. Our algorithm for matroid median is based on rounding a natural linear programming relaxation in two stages, and it relies on a connection to matroid intersection. In the knapsack median problem, centers have weights and the total weight of open centers is constrained to be at most a given capacity. When all weights are uniform, this reduces to the k-median problem. The algorithm for knapsack median is based on a novel LP relaxation that constrains the set of centers that each vertex can get connected to. The rounding procedure uses a two-stage approach similar to that for matroid median.