论文标题
优先基质中位数
Bicriteria Approximation Algorithms for Priority Matroid Median
论文作者
论文摘要
近年来，公平考虑因素激发了新的聚类问题和算法。在本文中，我们考虑了当前研究的优先级$ K $ -Median问题的优先级矩阵中位数问题。该输入由一组设施$ \ MATHCAL {F} $和一组客户$ \ Mathcal {C} $组成，该设施位于公制空间$（\ Mathcal {f} \ Cup \ Cup \ Cup \ Mathcal {c}，d），d），d），d）$ {m Mathcal $ \ Mathcal {m MathC {m Mathc =（fc）在设施上。此外，每个客户端$ j $都有指定的半径$ r_j \ ge 0 $，并且每个设施$ i \ in \ mathcal {f} $都有开放费用$ f_i $。目标是选择一个设施的子集$ s \ subseteq \ Mathcal {f} $，以最大程度地减少$ \ sum_ {i \ in \ Mathcal {f}} f_i + sum_ + sum_ { $ \ MATHCAL {M} $（即$ s \ in \ Mathcal {i} $）和（ii）对于每个客户端$ J $，其与开放设施的距离最多为$ r_j $（也就是说，$ d（j，s）\ le l _ r_j $）。对于这个问题，我们描述了第一个双晶尺$（C_1，C_2）$ c_1，C_2 $的近似值：客户的半径约束最多违反$ C_1 $，并且客观成本最多是$ C_2 $ C_2 $是最佳成本的倍。我们还改进了均匀半径设置的先前已知的两次近似值（$ r_j：= l $ $ \ $ \ forall j \ in \ mathcal {c} $）。
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 $\mathcal{F}$ and a set of clients $\mathcal{C}$ that lie in a metric space $(\mathcal{F} \cup \mathcal{C},d)$, and a matroid $\mathcal{M}=(\mathcal{F},\mathcal{I})$ over the facilities. In addition each client $j$ has a specified radius $r_j \ge 0$ and each facility $i \in \mathcal{F}$ has an opening cost $f_i$. The goal is to choose a subset $S \subseteq \mathcal{F}$ of facilities to minimize the $\sum_{i \in \mathcal{F}} f_i + \sum_{j \in \mathcal{C}} d(j,S)$ subject to two constraints: (i) $S$ is an independent set in $\mathcal{M}$ (that is $S \in \mathcal{I}$) and (ii) for each client $j$, its distance to an open facility is at most $r_j$ (that is, $d(j,S) \le 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$ $\forall j \in \mathcal{C}$).
