論文の概要: Improved Approximation Algorithms for Individually Fair Clustering
- arxiv url: http://arxiv.org/abs/2106.14043v1
- Date: Sat, 26 Jun 2021 15:22:52 GMT
- ステータス: 処理完了
- システム内更新日: 2021-06-29 13:53:41.123082
- Title: Improved Approximation Algorithms for Individually Fair Clustering
- Title（参考訳）: 個別クラスタリングのための近似アルゴリズムの改良
- Authors: Ali Vakilian, Mustafa Yal\c{c}{\i}ner
- Abstract要約: 16p +varepsilon,3)$-bicriteria approximation for the fair $k$-clustering with $ell_p$-norm cost。
我々のアプローチは、Kleindessnerらによって提案されたグループフェアネス要件により、個別に公平なクラスタリングからクラスタリングに還元されることを示唆している。
- 参考スコア（独自算出の注目度）: 9.914246432182873
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We consider the $k$-clustering problem with $\ell_p$-norm cost, which
includes $k$-median, $k$-means and $k$-center cost functions, under an
individual notion of fairness proposed by Jung et al. [2020]: given a set of
points $P$ of size $n$, a set of $k$ centers induces a fair clustering if for
every point $v\in P$, $v$ can find a center among its $n/k$ closest neighbors.
Recently, Mahabadi and Vakilian [2020] showed how to get a
$(p^{O(p)},7)$-bicriteria approximation for the problem of fair $k$-clustering
with $\ell_p$-norm cost: every point finds a center within distance at most $7$
times its distance to its $(n/k)$-th closest neighbor and the $\ell_p$-norm
cost of the solution is at most $p^{O(p)}$ times the cost of an optimal fair
solution. In this work, for any $\varepsilon>0$, we present an improved $(16^p
+\varepsilon,3)$-bicriteria approximation for the fair $k$-clustering with
$\ell_p$-norm cost. To achieve our guarantees, we extend the framework of
[Charikar et al., 2002, Swamy, 2016] and devise a $16^p$-approximation
algorithm for the facility location with $\ell_p$-norm cost under matroid
constraint which might be of an independent interest. Besides, our approach
suggests a reduction from our individually fair clustering to a clustering with
a group fairness requirement proposed by Kleindessner et al. [2019], which is
essentially the median matroid problem [Krishnaswamy et al., 2011].
- Abstract（参考訳）: Jungらによって提案された公正性の概念の下で、$k$-median、$k$-means、$k$-centerコスト関数を含む$\ell_p$-normコストの$k$-clustering問題を考える。
[2020]: 点の集合 P$ of size $n$ が与えられたとき、$k$ 中心の集合は、すべての点 $v\in P$ に対して、$v$ が近辺の $n/k$ の中心を見つけることができるならば、公平なクラスタリングを誘導する。
最近、Mahabadi と Vakilian [2020] は、$(p^{O(p)},7)$-bicriteria approximation for the problem of fair $k$-clustering with $\ell_p$-norm cost: すべての点が、その$(n/k)$-th Near neighbor と、$\ell_p$-norm cost of the solution の少なくとも$(p^{O(p)}$倍の距離にある中心を見つける。
この研究では、任意の$\varepsilon>0$に対して、$\ell_p$-normコストのフェア$k$-clusteringに対する改良された$ 16^p +\varepsilon,3)$-bicriteria近似を示す。
保証を達成するため、[Charikar et al., 2002, Swamy, 2016] の枠組みを拡張し、独立した関心を持つマトロイド制約の下で、$\ell_p$-normのコストで施設位置に対する16^p$-approximationアルゴリズムを考案する。
さらに,我々のアプローチは,kleindessnerらによって提案されたグループフェアネス要件により,個々に公平なクラスタリングからクラスタ化への縮小を示唆する。
Crishnaswamy et al., 2011] は, 基本的には中央値のマトロイド問題である。
関連論文リスト
- Relax and Merge: A Simple Yet Effective Framework for Solving Fair $k$-Means and $k$-sparse Wasserstein Barycenter Problems [8.74967598360817]
複数のグループからなるデータセットが与えられた場合、公正性制約は各クラスタに各グループからのポイントの割合を含む必要がある。
我々はRelax と Merge' のフレームワークを提案し、$rho$ は既製のvanilla $k$-means アルゴリズムの近似比である。
PTASが$k$-meansである場合、我々の解は、フェアネス制約にわずかに違反するだけで、$(5+O(epsilon))$の近似比を達成できる。
論文 参考訳（メタデータ） (2024-11-02T02:50:12Z) - 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) - Mind the gap: Achieving a super-Grover quantum speedup by jumping to the
end [114.3957763744719]
本稿では,数種類のバイナリ最適化問題に対して,厳密な実行保証を有する量子アルゴリズムを提案する。
このアルゴリズムは、$n$非依存定数$c$に対して、時間で$O*(2(0.5-c)n)$の最適解を求める。
また、$k$-spinモデルからのランダムなインスタンスの多数と、完全に満足あるいはわずかにフラストレーションされた$k$-CSP式に対して、文 (a) がそうであることを示す。
論文 参考訳（メタデータ） (2022-12-03T02:45:23Z) - Scalable Differentially Private Clustering via Hierarchically Separated
Trees [82.69664595378869]
我々は,最大$O(d3/2log n)cdot OPT + O(k d2 log2 n / epsilon2)$,$epsilon$はプライバシ保証であることを示す。
最悪の場合の保証は、最先端のプライベートクラスタリング手法よりも悪いが、提案するアルゴリズムは実用的である。
論文 参考訳（メタデータ） (2022-06-17T09:24:41Z) - 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) - Better Algorithms for Individually Fair $k$-Clustering [4.936817539835045]
Jung, Kannan, Lutz [FORC 2020]は、$ell_infty$または$k$-Centerの目的に対して、証明可能な(近似的な)フェアネスと客観的保証を備えたクラスタリングアルゴリズムを導入した。Mahabadi氏とVakilian氏(ICML 2020)は、この問題を再考して、すべての$ell_p$-normsに対してローカル検索アルゴリズムを提供する。
我々は、既知のLPラウンドリング技術を変更することで、MV20よりもはるかに優れた目標に対して最悪のケースを保証できることを実証的に証明し、この目標が最適に非常に近いことを実証した。
論文 参考訳（メタデータ） (2021-06-23T04:16:46Z) - Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean
Estimation [58.24280149662003]
本稿では,データセットの大部分を敵が破壊できるリストデコタブル平均推定の問題について検討する。
我々は、ほぼ最適な統計的保証を達成するために、リストデコダブル平均推定のための新しいアルゴリズムを開発した。
論文 参考訳（メタデータ） (2021-06-16T03:34:14Z) - Locally Private Hypothesis Selection [96.06118559817057]
我々は、$mathcalQ$から$p$までの総変動距離が最良の分布に匹敵する分布を出力する。
局所的な差分プライバシーの制約は、コストの急激な増加を引き起こすことを示す。
提案アルゴリズムは,従来手法のラウンド複雑性を指数関数的に改善する。
論文 参考訳（メタデータ） (2020-02-21T18:30:48Z) - Individual Fairness for $k$-Clustering [16.988236398003068]
ローカル検索に基づく$k$-medianと$k$-meansのアルゴリズム。
公平な$k$-clusteringのために、bicriteria近似の取得方法を示す。
論文 参考訳（メタデータ） (2020-02-17T02:31:13Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。