論文の概要: A Polynomial-Time Approximation for Pairwise Fair $k$-Median Clustering

• arxiv url: http://arxiv.org/abs/2405.10378v1
• Date: Thu, 16 May 2024 18:17:44 GMT
• ステータス: 処理完了
• システム内更新日: 2024-05-20 17:42:52.317134
• Title: A Polynomial-Time Approximation for Pairwise Fair $k$-Median Clustering
• Title（参考訳）: Pairwise Fair $k$-Median Clusteringのための多項式時間近似
• Authors: Sayan Bandyapadhyay, Eden Chlamtáč, Yury Makarychev, Ali Vakilian,
• Abstract要約: すべてのクラスタ$C$とすべてのグループ$i in [ell]$に対して、$C$ from group $i$のポイント数は、他のグループ$j in [ell]$のポイントの数のt倍でなければならない。 私たちは、$ell=2$が一般的な均一容量$k$-medianに匹敵する難易度である場合にも、その問題を示します。
• 参考スコア（独自算出の注目度）: 10.697784653113095
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this work, we study pairwise fair clustering with $\ell \ge 2$ groups, where for every cluster $C$ and every group $i \in [\ell]$, the number of points in $C$ from group $i$ must be at most $t$ times the number of points in $C$ from any other group $j \in [\ell]$, for a given integer $t$. To the best of our knowledge, only bi-criteria approximation and exponential-time algorithms follow for this problem from the prior work on fair clustering problems when $\ell > 2$. In our work, focusing on the $\ell > 2$ case, we design the first polynomial-time $(t^{\ell}\cdot \ell\cdot k)^{O(\ell)}$-approximation for this problem with $k$-median cost that does not violate the fairness constraints. We complement our algorithmic result by providing hardness of approximation results, which show that our problem even when $\ell=2$ is almost as hard as the popular uniform capacitated $k$-median, for which no polynomial-time algorithm with an approximation factor of $o(\log k)$ is known.
• Abstract（参考訳）: この研究では、$\ell \ge 2$ group を用いてペアワイズフェアクラスタリングを研究し、すべてのクラスタに対して $C$ とすべてのグループ $i \in [\ell]$ に対して、$C$ from group $i$ の点数は、任意の整数 $t$ に対して $C$ の点数の最大$t$ 倍でなければならない。 我々の知る限り、双基準近似と指数時間アルゴリズムだけが、$\ell > 2$のときの公正クラスタリング問題に関する以前の研究からこの問題に追従する。 我々の研究では、$\ell > 2$ の場合に焦点を当て、最初の多項式時間 $(t^{\ell}\cdot \ell\cdot k)^{O(\ell)}$-approximation for this problem with $k$-median cost that not violation the fairness constraints。 近似係数が$o(\log k)$の多項式時間アルゴリズムが知られていないような、一般的な均一容量の$k$-medianに匹敵する難易度が$\ell=2$であっても、アルゴリズムの結果を補う。

関連論文リスト

• On Approximability of $\ell_2^2$ Min-Sum Clustering [17.403803548692498]
  本稿では、$ell2$ minsum $k$-clustering問題に対して、最初の強度近似結果を与える。 さらに、ジョンソン被覆仮説の均衡を仮定すると、その目的を1.327よりも良い因子に近似することはNPハードであることが示される。
  論文  参考訳（メタデータ） (2024-12-04T14:03:27Z)
• The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
  この問題は通信複雑性のランダム化を$Omega(frac1kcdot n2log|mathbbF|)$とする。 アプリケーションとして、$k$パスを持つ任意のストリーミングアルゴリズムに対して、$Omega(frac1kcdot n2log|mathbbF|)$スペースローバウンドを得る。
  論文  参考訳（メタデータ） (2024-10-26T06:21:42Z)
• 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 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)
• Do you know what q-means? [50.045011844765185]
  クラスタリングは、大規模なデータセットを分析する上で最も重要なツールの1つである。 クラスタリングのための"$q$-means"アルゴリズムの改良版を提案する。 また、$Obig(frack2varepsilon2(sqrtkd + log(Nd))big で実行される $varepsilon に対する "dequantized" アルゴリズムも提示する。
  論文  参考訳（メタデータ） (2023-08-18T17:52:12Z)
• Approximation Algorithms for Fair Range Clustering [14.380145034918158]
  本稿では、データポイントが異なる人口集団のものであるフェアレンジクラスタリング問題について検討する。 目標は、各グループが少なくともセンターセットで最小限に表現されるように、最小クラスタリングコストで$k$センターを選択することである。 特に、fair range $ell_p$-clusteringは、特別なケースとして$k$-center、$k$-median、$k$-meansをキャプチャする。
  論文  参考訳（メタデータ） (2023-06-11T21:18:40Z)
• Constant-Factor Approximation Algorithms for Socially Fair $k$-Clustering [12.545909976356528]
  社会的に公正な$(ell_p, k)$-clustering問題$m$groupに対する近似アルゴリズムについて検討する。 a-time $(5+2sqrt6)pimation at most $k+m$center (2) a $(5+2sqrt6)pimation with $k$center in time $n2O(p)cdot m2$, (3) a $ 15+6sqrt6)p$ approximation with $k$center in。
  論文  参考訳（メタデータ） (2022-06-22T16:57:17Z)
• TURF: A Two-factor, Universal, Robust, Fast Distribution Learning Algorithm [64.13217062232874]
  最も強力で成功したモダリティの1つは、全ての分布を$ell$距離に近似し、基本的に最も近い$t$-piece次数-$d_$の少なくとも1倍大きい。 本稿では,この数値をほぼ最適に推定する手法を提案する。
  論文  参考訳（メタデータ） (2022-02-15T03:49:28Z)
• 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)
• 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)

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

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