TY - GEN

T1 - Bicriteria Approximation Algorithms for Priority Matroid Median

AU - Bajpai, Tanvi

AU - Chekuri, Chandra

N1 - Publisher Copyright:
© 2023 Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. All rights reserved.

PY - 2023/9

Y1 - 2023/9

N2 - 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 F and a set of clients C that lie in a metric space (F ∪ C, d), and a matroid M = (F, I) over the facilities. In addition, each client j has a specified radius rj ≥ 0 and each facility i ∈ F has an opening cost fi > 0. The goal is to choose a subset S ⊆ F of facilities to minimize Pi∈F fi + Pj∈C d(j, S) subject to two constraints: (i) S is an independent set in M (that is S ∈ I) and (ii) for each client j, its distance to an open facility is at most rj (that is, d(j, S) ≤ rj). For this problem we describe the first bicriteria (c1, c2) approximations for fixed constants c1, c2: the radius constraints of the clients are violated by at most a factor of c1 and the objective cost is at most c2 times the optimum cost. We also improve the previously known bicriteria approximation for the uniform radius setting (rj := L ∀j ∈ C).

AB - 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 F and a set of clients C that lie in a metric space (F ∪ C, d), and a matroid M = (F, I) over the facilities. In addition, each client j has a specified radius rj ≥ 0 and each facility i ∈ F has an opening cost fi > 0. The goal is to choose a subset S ⊆ F of facilities to minimize Pi∈F fi + Pj∈C d(j, S) subject to two constraints: (i) S is an independent set in M (that is S ∈ I) and (ii) for each client j, its distance to an open facility is at most rj (that is, d(j, S) ≤ rj). For this problem we describe the first bicriteria (c1, c2) approximations for fixed constants c1, c2: the radius constraints of the clients are violated by at most a factor of c1 and the objective cost is at most c2 times the optimum cost. We also improve the previously known bicriteria approximation for the uniform radius setting (rj := L ∀j ∈ C).

KW - fair clustering

KW - k-median

KW - matroid

UR - http://www.scopus.com/inward/record.url?scp=85171987685&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85171987685&partnerID=8YFLogxK

U2 - 10.4230/LIPIcs.APPROX/RANDOM.2023.7

DO - 10.4230/LIPIcs.APPROX/RANDOM.2023.7

M3 - Conference contribution

AN - SCOPUS:85171987685

T3 - Leibniz International Proceedings in Informatics, LIPIcs

BT - Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2023

A2 - Megow, Nicole

A2 - Smith, Adam

PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing

T2 - 26th International Conference on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2023 and the 27th International Conference on Randomization and Computation, RANDOM 2023

Y2 - 11 September 2023 through 13 September 2023

ER -