Bicriteria Approximation Algorithms for Priority Matroid Median
share
Fairness considerations have motivated new clustering problems and algorithms in recent years. In this paper we consider the Priority Matroid Median problem which generalizes the Priority k-Median problem that has recently been studied. The input consists of a set of facilities ℱ and a set of clients 𝒞 that lie in a metric space (ℱ∪𝒞,d), and a matroid ℳ=(ℱ,ℐ) over the facilities. In addition each client j has a specified radius r_j ≥ 0 and each facility i ∈ℱ has an opening cost f_i. The goal is to choose a subset S ⊆ℱ of facilities to minimize the ∑_i ∈ℱ f_i + ∑_j ∈𝒞 d(j,S) subject to two constraints: (i) S is an independent set in ℳ (that is S ∈ℐ) and (ii) for each client j, its distance to an open facility is at most r_j (that is, d(j,S) ≤ r_j). For this problem we describe the first bicriteria (c_1,c_2) approximations for fixed constants c_1,c_2: the radius constraints of the clients are violated by at most a factor of c_1 and the objective cost is at most c_2 times the optimum cost. We also improve the previously known bicriteria approximation for the uniform radius setting (r_j := L ∀ j ∈𝒞).
READ FULL TEXT