Title: The Matroid Median Problem

Abstract: In the classical k-median problem, given a set of locations in a metric space the goal is to open at most k centers so as to minimize the sum (over all locations) of the distance of each location to its nearest open center. We consider a substantial generalization (Matroid Median) where centers are constrained to be independent in some matroid, and provide a constant factor approximation algorithm. Two previously considered special cases are (1) k-median: uniform matroid of rank k, and (2) Red-blue median: partition matroid with two parts.

Our algorithm is based on rounding a natural LP relaxation in two phases: in the first phase, we sparsify the structure of the fractional solution while increasing the
objective function value by only a constant factor. This enables us to formulate another LP in the second phase, which we show is integral via a connection to matroid intersection.