論文の概要: Approximation Algorithms for Fair Range Clustering

• arxiv url: http://arxiv.org/abs/2306.06778v1
• Date: Sun, 11 Jun 2023 21:18:40 GMT
• ステータス: 処理完了
• システム内更新日: 2023-06-13 16:48:20.875380
• Title: Approximation Algorithms for Fair Range Clustering
• Title（参考訳）: フェアレンジクラスタリングのための近似アルゴリズム
• Authors: S\`edjro S. Hotegni and Sepideh Mahabadi and Ali Vakilian
• Abstract要約: 本稿では、データポイントが異なる人口集団のものであるフェアレンジクラスタリング問題について検討する。 目標は、各グループが少なくともセンターセットで最小限に表現されるように、最小クラスタリングコストで$k$センターを選択することである。 特に、fair range $ell_p$-clusteringは、特別なケースとして$k$-center、$k$-median、$k$-meansをキャプチャする。
• 参考スコア（独自算出の注目度）: 14.380145034918158
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: This paper studies the fair range clustering problem in which the data points are from different demographic groups and the goal is to pick $k$ centers with the minimum clustering cost such that each group is at least minimally represented in the centers set and no group dominates the centers set. More precisely, given a set of $n$ points in a metric space $(P,d)$ where each point belongs to one of the $\ell$ different demographics (i.e., $P = P_1 \uplus P_2 \uplus \cdots \uplus P_\ell$) and a set of $\ell$ intervals $[\alpha_1, \beta_1], \cdots, [\alpha_\ell, \beta_\ell]$ on desired number of centers from each group, the goal is to pick a set of $k$ centers $C$ with minimum $\ell_p$-clustering cost (i.e., $(\sum_{v\in P} d(v,C)^p)^{1/p}$) such that for each group $i\in \ell$, $|C\cap P_i| \in [\alpha_i, \beta_i]$. In particular, the fair range $\ell_p$-clustering captures fair range $k$-center, $k$-median and $k$-means as its special cases. In this work, we provide an $O(1)$-approximation algorithm for the fair range $\ell_p$-clustering that picks at most $k+2\ell$ centers and may only violate the upper bound of each demographic group by at most an additive term of $2$.
• Abstract（参考訳）: 本論文は,データポイントが異なる人口集団から得られるフェアレンジクラスタリング問題について検討し,各グループを最低限のクラスタリングコストで選択することを目的としている。 More precisely, given a set of $n$ points in a metric space $(P,d)$ where each point belongs to one of the $\ell$ different demographics (i.e., $P = P_1 \uplus P_2 \uplus \cdots \uplus P_\ell$) and a set of $\ell$ intervals $[\alpha_1, \beta_1], \cdots, [\alpha_\ell, \beta_\ell]$ on desired number of centers from each group, the goal is to pick a set of $k$ centers $C$ with minimum $\ell_p$-clustering cost (i.e., $(\sum_{v\in P} d(v,C)^p)^{1/p}$) such that for each group $i\in \ell$, $|C\cap P_i| \in [\alpha_i, \beta_i]$. 特に、fair range $\ell_p$-clusteringは、特別なケースとして、fair range $k$-center、$k$-median、$k$-meansをキャプチャする。 本研究では,最大$k+2\ell$センターで選択し,少なくとも$$$という付加項で各人口集団の上限にのみ違反する,フェアレンジの$\ell_p$-clusteringのための$o(1)$近似アルゴリズムを提供する。

関連論文リスト

• LevAttention: Time, Space, and Streaming Efficient Algorithm for Heavy Attentions [54.54897832889028]
  任意の$K$に対して、$n$とは独立に「普遍集合」$Uサブセット[n]$が存在し、任意の$Q$と任意の行$i$に対して、大きな注目スコアが$A_i,j$ in row $i$ of $A$は全て$jin U$を持つことを示す。 我々は、視覚変換器のスキームの利点を実証的に示し、トレーニング中に我々の普遍的なセットを使用する新しいモデルのトレーニング方法を示した。
  論文  参考訳（メタデータ） (2024-10-07T19:47:13Z)
• A Polynomial-Time Approximation for Pairwise Fair $k$-Median Clustering [10.697784653113095]
  すべてのクラスタ$C$とすべてのグループ$i in [ell]$に対して、$C$ from group $i$のポイント数は、他のグループ$j in [ell]$のポイントの数のt倍でなければならない。 私たちは、$ell=2$が一般的な均一容量$k$-medianに匹敵する難易度である場合にも、その問題を示します。
  論文  参考訳（メタデータ） (2024-05-16T18:17:44Z)
• A Scalable Algorithm for Individually Fair K-means Clustering [77.93955971520549]
  Jung et al. と Mahabadi et al が導入した個別フェア (p$, $k$) クラスタリング問題に対するスケーラブルなアルゴリズムを提案する。 クラスタリングは、各$xin P$に対して$delta(x)$ of $x$の範囲内で中心となる場合、個別にフェアと呼ばれる。 我々は,従来よりもアルゴリズムがはるかに高速であるだけでなく,低コストのソリューションを生み出すことを実証的に示す。
  論文  参考訳（メタデータ） (2024-02-09T19:01:48Z)
• Improved Search of Relevant Points for Nearest-Neighbor Classification [91.3755431537592]
  トレーニングセットから除外された場合、トレーニングポイントが$mathbbRd$のクエリポイントの誤分類を引き起こす可能性がある場合、トレーニングポイントは関連していると言います。 出力に敏感なアルゴリズムが提案され、境界点の集合が$P$ in $O(n2 + nk2 )$ time, ここで$k$はそのような集合のサイズである。 本稿では,このアルゴリズムを,O(nk2 )$と同等の時間複雑性を持つように改良し,そのアルゴリズムの最初のステップが$O(n2)であることを示す。
  論文  参考訳（メタデータ） (2022-03-07T18:10:27Z)
• Fair Representation Clustering with Several Protected Classes [13.53362222844008]
  我々は、各クラスタが異なるグループから個人を公平に表現する必要があるフェア$k$-medianの問題を研究する。 我々は、$O(log k)$-approximationアルゴリズムを示し、$nO(ell)$で実行します。
  論文  参考訳（メタデータ） (2022-02-03T03:45:45Z)
• Approximating Fair Clustering with Cascaded Norm Objectives [10.69111036810888]
  ベクトルの $ell_q$-norm を $ell_p$-norms の $ell_p$-norm よりも小さくするクラスタリングが、中心から$P$ の点の重み付き距離の $ell_p$-norms より小さい。 これはSocially Fair $k$-Medianや$k$-Meansなど、さまざまなクラスタリング問題を一般化する。
  論文  参考訳（メタデータ） (2021-11-08T20:18:10Z)
• FriendlyCore: Practical Differentially Private Aggregation [67.04951703461657]
  我々は、制約のない(擬似)計量空間から点の集合を$cal D$として取り出す、単純で実用的なツールである$mathsfFriendlyCore$を提案する。 $cal D$ が有効直径 $r$ を持つとき、$mathsfFriendlyCore$ はすべての点を含む "stable" サブセット $cal D_Gsubseteq cal D$ を返す。 $mathsfFriendlyCore$は、プライベートに集約する前に入力を前処理するために使用することができる。
  論文  参考訳（メタデータ） (2021-10-19T17:43:50Z)
• Improved Approximation Algorithms for Individually Fair Clustering [9.914246432182873]
  16p +varepsilon,3)$-bicriteria approximation for the fair $k$-clustering with $ell_p$-norm cost。 我々のアプローチは、Kleindessnerらによって提案されたグループフェアネス要件により、個別に公平なクラスタリングからクラスタリングに還元されることを示唆している。
  論文  参考訳（メタデータ） (2021-06-26T15:22:52Z)
• Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean Estimation [58.24280149662003]
  本稿では,データセットの大部分を敵が破壊できるリストデコタブル平均推定の問題について検討する。 我々は、ほぼ最適な統計的保証を達成するために、リストデコダブル平均推定のための新しいアルゴリズムを開発した。
  論文  参考訳（メタデータ） (2021-06-16T03:34:14Z)
• Learning a Latent Simplex in Input-Sparsity Time [58.30321592603066]
  我々は、$AinmathbbRdtimes n$へのアクセスを考えると、潜入$k$-vertex simplex $KsubsetmathbbRdtimes n$を学習する問題を考える。 実行時間における$k$への依存は、トップ$k$特異値の質量が$a$であるという自然な仮定から不要であることを示す。
  論文  参考訳（メタデータ） (2021-05-17T16:40:48Z)
• Individual Fairness for $k$-Clustering [16.988236398003068]
  ローカル検索に基づく$k$-medianと$k$-meansのアルゴリズム。 公平な$k$-clusteringのために、bicriteria近似の取得方法を示す。
  論文  参考訳（メタデータ） (2020-02-17T02:31:13Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。