Bicriteria Approximation Algorithms for Priority Matroid Median Tanvi BajpaiChandra Chekuri July 10 2023

2025-04-27 0 0 1.33MB 27 页 10玖币
侵权投诉
Bicriteria Approximation Algorithms for Priority Matroid Median
Tanvi Bajpai∗Chandra Chekuri†
July 10, 2023
Abstract
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
Fand a set of clients Cthat lie in a metric space (F ∪ C, d), and a matroid M= (F,I) over
the facilities. In addition, each client jhas 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) Sis 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 c1and
the objective cost is at most c2times the optimum cost. We also improve the previously known
bicriteria approximation for the uniform radius setting (rj:= L∀j∈ C).
1 Introduction
Clustering and facility-location problems are widely studied in areas such as machine learning,
operations research, and algorithm design. Among these, center-based clustering problems in metric
spaces form a central topic and will be our focus. The input for these problems is a set of clients
Cand a set of facilities Ffrom a metric space (F ∪ C, d). The goal is to select a subset of facilities
S⊆ F to open, subject to various constraints, so as to minimize an objective that depends on the
distances of the clients to the chosen centers; we use d(j, S) to denote the quantity mini∈Sd(j, i)
which is the distance from jto S. Typical objectives are of the form (Pj∈C d(j, S)p)1/p for some
parameter p(the ℓpnorm of the distances). When the constraint on facilities is that at most kcan
be chosen (that is, |S| ≤ k), we obtain several standard and well-studied problems such as k-Center
(p=∞), k-Median (p= 1), and k-Means (p= 2) problems. These problems are extensively studied
from many perspectives [HS85,Ple87,CGTS02,ANFSW20,AV07,KMN+02,JV01]. These are also
well-studied in the geometric setting when Fis the continuous space Rℓfor some finite dimension
ℓ. In this paper we restrict our attention to the discrete setting, and in particular, to the median
objective (p= 1).
The Matroid Median problem is a generalization of the k-Median clustering problem. Here, the
cardinality constraint kon Sis replaced by specifying a matroid M= (F,I) on the facility set F
∗Dept. of Computer Science, Univ. of Illinois, Urbana-Champaign, Urbana, IL 61801. tbajpai2@illinois.edu.
Partly supported by NSF grant CCF-1910149.
†Dept. of Computer Science, Univ. of Illinois, Urbana-Champaign, Urbana, IL 61801. chekuri@illinois.edu.
Partly supported by NSF grant CCF-1910149.
1
arXiv:2210.01888v2 [cs.DS] 6 Jul 2023
and requiring that S∈ I (we refer a reader unfamiliar with matroids to Section 2formal definitions
and details). The k-Median clustering problem can be written as an instance of Matroid Median
where Mis the uniform matroid of rank k. The Matroid Median problem was first introduced by
Krishnaswamy et al. [KKN+11] as a generalization of k-Median and Red-Blue Median [HKK10].
Motivated by the versatility of the Matroid Median problem, and several other considera-
tions that we will discuss shortly, in this paper we study the Priority Matroid Median problem
(PMatMed). Formally, in PMatMed we are given a set of clients Cand facilities Ffrom a metric
space (F ∪ C, d) where each facility i∈ F has a facility opening cost fi, and each client j∈ C
has a radius value rj. We are also given a matroid M= (F,I) over the facilities. The goal is
to select a subset of facilities Sthat is an independent set of the matroid Mwhere the objective
Pj∈C d(j, S) + Pi∈Sfi(i.e. the cost induced by selected facilities) is minimized, and the radius
constraint d(j, S)≤rjis satisfied for all clients j∈ C.
Most of the center-based clustering problems are NP-Hard even in very restricted settings. We
focus on polynomial-time approximation algorithms which have an extensive history in center-
based clustering. Moreover, due to the nature of the constraints in PMatMed, we can only obtain
bicriteria approximation guarantees that violate both the objective and the radius constraints. An
(α, β)-approximation algorithm for PMatMed is a polynomial-time algorithm that either correctly
states that no feasible solution is possible or outputs a set of facilities S∈ I (hence satisfies the
matroid constraint) such that (i) d(j, S)≤αrjfor all clients j∈ C and (ii) the cost objective value
of Sis at most β·OP T where OP T is the cost of an optimum solution.
1.1 Motivation, Applications to Fair Clustering, and Related Work
Our study of PMatMed is motivated, at a high-level, by two considerations. First, there has been
past work that combines the k-Median objective with that of the k-Center objective. Alamdari and
Shmoys [AS17] considered the k-Median problem with the additional constraint that each client is
served within a given uniform radius Land obtained a (4,8)-approximation. Their work is partially
motivated by the ordered median problem [NP06,AS19,BSS18]. Kamiyama [Kam20] studied a
generalization of this uniform radius requirement on clients to the setting of Matroid Median and
derived a (11,16)-approximation algorithm. Note that this is a special case of PMatMed where
rj=Lfor each j. We call this the UniPMatMed problem.
Another motivation for studying PMatMed is the recent interest in fair clustering in the broader
context of algorithmic fairness. The goal is to capture and address social concerns in applications
that rely on clustering procedures and algorithms. Various notions of fair clustering have been
proposed. Chierchetti et al. [CKLV17] formulated the Fair k-Center problem: clients belong to
one or more groups based on various attributes. The objective is to return a clustering of points
where each chosen center services a representative number of clients from every group. This notion
has since been classified as one that seeks to achieve group fairness. Several other group fair
clustering problems have since been introduced and studied [BIPV19,KAM19,ABV21,GSV21].
Subsequently, clustering formulations that aimed to encapsulate individual fairness were explored
which seek to ensure that each individual is treated fairly. One such formulation was introduced
by Jung et al. [JKL19]. This formulation is related to the well-studied k-Center clustering and
is the following. Given npoints in a metric space representing users, and an integer k, find a set
of kcenters Ssuch that d(j, S) is at most rjwhere rjdenotes the smallest radius around jthat
contains n/k points. Such a clustering is fair to individual users since no user will be forced to
travel outside their neighborhood. Jung et al. [JKL19] showed that the problem is NP-Hard and
2
described a simple greedy algorithm that finds kcenters Ssuch that d(j, S)≤2rjfor all j. Jung
et al.’s model can be related to an earlier model of Plesn´ık who considered the Weighted k-Center
problem [Ple87]. In Plesn´ık’s version, each user jspecifies an arbitrary radius rj>0 and the goal
is to find kcenters Sto serve each user within their radius requirement. Plesn´ık showed that a
simple variant of a well-known algorithm for k-Center due to Hochbaum and Shmoys [HS85] yields
a 2-approximation. Plesn´ık’s problem has been relabeled as the Priority k-Center problem in recent
work [BCCN21].
Priority clustering: The model of Jung et al. motivated several variations and generalizations
of the Priority k-Center problem. Bajpai et al. [BCCN21] defined, and provided constant factor
approximations, for Priority k-Supplier (where facilities and clients are considered to be disjoint
sets), as well as Priority Matroid and Knapsack Center, where facilities are subject to matroid
and knapsack constraints, respectively. Mahabadi and Vakilian [MV20] explored and developed
approximation algorithms for Priority k-Median and Priority k-Means problems; their motiva-
tion was to combine the individual fairness requirements in terms of radii proposed by Jung et
al., with the traditional objectives of clustering. They obtained bicriteria approximation algo-
rithms via local-search. The approximation bounds were later improved via LP-based techniques.
Chakrabarty and Negahbani [CN21] obtained an (8,8)-approximation for Priority k-Median and a
(8,16)-approximation for Priority k-Means. Vakilian and Yalcner [VY21] further improved these
results via a nice black box reduction of Priority k-Median to the Matroid Median problem! Via
their reduction they obtained (3,7.081 + ϵ)-approximation for the Priority k-Median problem (re-
lying on the algorithm for Matroid Median from [KLS18]). They extended the algorithmic ideas
from Matroid Median to handle ℓpnorm objectives and were thus able to derive algorithms for
Priority k-Means as well. The advantage of the reduction to Matroid Median is the guarantee of 3
on the radius dilation. This is optimal even for the k-Supplier problem [HS85].
1.2 Results and Technical Contribution
In this paper, we define the PMatMed problem and derive the first (c1, c2)-bicriteria approximation
algorithms where c1, c2are both constants. There are different trade-offs between c1and c2that
we can achieve. Since PMatMed simultaneously generalizes k-Supplier and Matroid Median, the
best c1we can hope for is 3, and the best c2that we can hope for is ≈8, which comes from current
algorithms for Matroid Median [KLS18,Swa16]. We prove the following theorem which captures
two results, one optimizing for the radius guarantee, and the other for the cost guarantee.
Theorem 1. There is a (21,12)-approximation algorithm for the Priority Matroid Median Problem.
There is also a (36,8)-approximation algorithm.
As we previously mentioned, [VY21], via their black box reduction to Matroid Median achieve a
(3, α) approximation for Priority k-Median where αis the best approximation for Matroid Median.
We conjecture that there is a (3, O(1))-approximation for PMatMed. This is interesting and open
even for the special case with uniform radii under partition matroid constraint.
Our second set of results are for UniPMatMed. Recall that [Kam20] obtained a (11,16)-
approximation for this problem. We prove the following theorem that strictly dominates the bound
from [Kam20]. In addition, we show that a tighter radius guarantee is achievable.
Theorem 2. There is a (9,8)-approximation algorithm for the Uniform Priority Matroid Median
Problem. For any fixed ϵ > 0there is a (5 + 8ϵ, 4 + 2
ϵ)-approximation.
3
Remark 3. We believe that we can extend the ideas from this paper to obtain bicriteria approx-
imation algorithms for Priority Matroid objectives that involve the ℓpnorm of distances (Priority
Matroid Median is when ℓp:= 1). Such an approximation algorithm would result in a radius factor
dependent on p. [VY21] already showed that Matroid Median can be extended to the p-norm
objective.
Now, we give a brief overview of our technical approach. The reader may wonder about the
reduction of Priority k-Median to Matroid Median [VY21]. Can we make use of this for PMatMed?
Indeed one can employ the same reduction, however, the resulting instance is no longer an instance
of Matroid Median but an instance of Matroid Intersection Median which is inapproximable [Swa16].
The reduction works in the special case of Priority k-Median since the intersection of a matroid
with a cardinality constraint yields another matroid. We therefore address PMatMed directly. Our
approximation algorithms are based on a natural LP relaxation. It is not surprising that we need
to build upon the techniques for Matroid Median since it is a special case. We build extensively
on the LP-based 8-approximation for Matroid Median given by Swamy [Swa16] which improved
the first constant factor approximation algorithm of Krishnaswamy et al. [KKN+11]. Although
the Matroid Median approximation has been improved to 7.081 [KLS18], the approach in [KLS18]
seems more difficult to adapt to PMatMed.
Our main technical contribution is to handle the non-uniform radii constraints imposed in
PMatMed in the overall approach for Matroid Median. We note that the rounding algorithms
for Matroid Median are quite complex, and involve several non-trivial stages: filtering, finding half
integral solutions via an auxiliary polytope, and finally rounding to an integral solution via matroid
intersection [KKN+11,Swa16,KLS18]. Kamiyama adapted the ideas in [KKN+11] to UniPMatMed
and his work involves four stages of reassigments that are difficult to follow. The non-uniform radii
case introduces additional complexity. We explain the differences between the uniform radii case
and the non-uniform radii case briefly. The LP relaxation opens fractional facilities and assigns each
client jto fractionally open facilities. In the LP for PMatMed we write a natural constraint that j
cannot be assigned to any facility iwhere d(i, j)> rj. Let ¯
Cjdenote the distance paid by jin the
LP solution. The preceding constraint ensures that ¯
Cj≤rj. For UniPMatMed,rj=Lfor all j∈ C.
LP-based approximation algorithms for k-Median use filtering and other rounding steps by sorting
clients in increasing order of ¯
Cjvalues since they are directly relevant to the objective. When one
considers uniform radius constraint, one can still effectively work with ¯
Cjvalues since we have
¯
Cj≤Lfor all j. However, when clients have non-uniform radii we can have the following situation;
there can be clients jand ksuch that ¯
Cj≪¯
Ckbut rj≫rk. Thus the radius requirements may
not correspond to the fractional distances paid in the LP.
We handle the above mentioned complexity via two careful adaptations to Matroid Median
rounding. One of these changes occurs in the second stage of Matroid Median rounding, where we
construct a half-integral solution using an auxiliary polytope. We must take care to ensure that the
half-integral solution constructed in this stage is one that will not violate the radius requirements
for clients. To do so, we create additional constraints in the auxiliary polytope. These constraints
ensure the half-integral solution satisfies certain properties that are crucial to obtain a constant
factor radius guarantee.
The second change occurs in the first filtering stage and plays a role not only for adapting
Matroid Median to PMatMed, but also for each of our other results. We first provide an abstract
way to describe the filtering stage that allows us to specificy the order in which points are considered,
and the distances each point can travel to be reassigned. For our first PMatMed result, the ordering
4
and distances are based on both ¯
Cjand rj. For UniPMatMed, we slightly alter the ordering and
distances (using the above observations and some ideas from [Kam20]). Our remaining results will
also involve changes to the filtering stage. This seems to indicate that filtering plays a large role in
the cost and radius trade-off.
Organization: In Section 2, we discuss preliminaries. In particular, we provide definitions and
relevant information regarding matroids, define PMatMed and provide its LP relaxation, and discuss
the generalized filtering procedure we will use in our algorithm. In Section 3we present our
algorithm for PMatMed and show that it can be used to obtain (21,12)-approximate solutions for
instances of PMatMed. In Section 4, we describe how to modify our algorithm for PMatMed to
obtain a (9,8)-approximate solution for instances of UniPMatMed, and the remaining results. In
Section 5, we describe how to acheive a (36,8)-approximate solutions for instances of PMatMed.
Finally, we discuss how to acheive a tighter bound for UniPMatMed in Section 6.
2 Preliminaries
2.1 Matroids, Matroid Intersection and Polyhedral Results
We assume some basic knowledge about matroids, but provide a few relevant definitions for sake
of completeness; we refer the reader to [S+03] for more details. A matroid M= (S, I) consists of
a finite ground set Sand a collection of independent sets I ⊆ 2Sthat satisfy the following axioms:
(i) ∅∈I(non-emptiness of I) (ii) A∈ I and B⊂Aimplies B∈ I (downward closure) and (iii)
A, B ∈ I with |A|<|B|implies there is i∈B\Asuch that A∪ {i} ∈ I (exchange property). The
rank function of a matroid, rM: 2S→Z≥0assigns to each X⊆Sthe cardinality of a maximum
independent subset in X. It is known that rMis a monotone submodular function. The matroid
polytope for a matroid M, denoted by PMis the convex hull of the characteristic vectors of the
independent sets of M. This can be characterized via the rank function:
PM={v∈RS| ∀X⊆S:v(X)≤rM(X) and ∀e∈S:v(e)≥0}.
Assuming an independence oracle1or a rank function oracle for M, one can optimize and separate
over PMin polynomial time. A partition matroid M= (S, I) is a special type of matroid that
is defined via a partition S1, S2, . . . , Shof Sand non-negative integers k1, . . . , kh. A set X⊆Sis
independent, that is X∈ I, iff |X∩Si| ≤ kifor 1 ≤i≤h. A simple partition matroid is one in
which ki= 1 for each i.
Given two matroids M= (S, I1) and N= (S, I2), on the same ground set, their intersection
is defined as M ∩ N := (S, I1∩ I2) consisting of sets that are independent in both Mand N.
Computing a maximum weight independent set in the intersection can be done efficiently. The
convex hull of the characteristic vectors of the independent sets of M∩N, denoted by PM,N, is
simply the intersection of PMand PN! That is
PM,N ={v∈RS
+| ∀X⊆S:v(X)≤rM(X), v(X)≤rN(X)}.
Thus, one can optimize over PM,Nif one has independence or rank oracles for Mand N. We will
need these results later in the paper. See [S+03] for these classical results.
1An independence oracle returns whether A∈ I for a given A⊆S.
5
摘要：

BicriteriaApproximationAlgorithmsforPriorityMatroidMedianTanviBajpai∗ChandraChekuri†July10,2023AbstractFairnessconsiderationshavemotivatednewclusteringproblemsandalgorithmsinrecentyears.InthispaperweconsiderthePriorityMatroidMedianproblemwhichgeneralizesthePriorityk-Medianproblemthathasrecentlybeens...

展开>> 收起<<
Bicriteria Approximation Algorithms for Priority Matroid Median Tanvi BajpaiChandra Chekuri July 10 2023.pdf

共27页,预览5页

还剩页未读， 继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

相关推荐

更多
立即下载
分类：图书资源 价格：10玖币 属性：27 页 大小：1.33MB 格式：PDF 时间：2025-04-27

开通VIP享超值会员特权

  • 多端同步记录
  • 高速下载文档
  • 免费文档工具
  • 分享文档赚钱
  • 每日登录抽奖
  • 优质衍生服务

作者详情

相关内容

更多

热门标签

人际关系 动力学连接体 力的合成 配电装置 高考理综 全宋诗作者索引 公务员考试
/ 27
评分 收藏
分享
立即下载
客服
关注