論文の概要: Constant-Factor Approximation Algorithms for Socially Fair
$k$-Clustering
- arxiv url: http://arxiv.org/abs/2206.11210v1
- Date: Wed, 22 Jun 2022 16:57:17 GMT
- ステータス: 処理完了
- システム内更新日: 2022-06-23 14:47:06.220544
- Title: Constant-Factor Approximation Algorithms for Socially Fair
$k$-Clustering
- Title（参考訳）: 社会的に公平な$k$-Clusteringのための定数要素近似アルゴリズム
- Authors: Mehrdad Ghadiri, Mohit Singh, Santosh S. Vempala
- Abstract要約: 社会的に公正な$(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。
- 参考スコア（独自算出の注目度）: 12.545909976356528
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study approximation algorithms for the socially fair $(\ell_p,
k)$-clustering problem with $m$ groups, whose special cases include the
socially fair $k$-median ($p=1$) and socially fair $k$-means ($p=2$) problems.
We present (1) a polynomial-time $(5+2\sqrt{6})^p$-approximation with at most
$k+m$ centers (2) a $(5+2\sqrt{6}+\epsilon)^p$-approximation with $k$ centers
in time $n^{2^{O(p)}\cdot m^2}$, and (3) a $(15+6\sqrt{6})^p$ approximation
with $k$ centers in time $k^{m}\cdot\text{poly}(n)$. The first result is
obtained via a refinement of the iterative rounding method using a sequence of
linear programs. The latter two results are obtained by converting a solution
with up to $k+m$ centers to one with $k$ centers using sparsification methods
for (2) and via an exhaustive search for (3). We also compare the performance
of our algorithms with existing bicriteria algorithms as well as exactly $k$
center approximation algorithms on benchmark datasets, and find that our
algorithms also outperform existing methods in practice.
- Abstract（参考訳）: 我々は、社会的に公正な$(\ell_p, k)$-clusteringを$m$グループで行う際の近似アルゴリズムについて研究し、社会的にフェアな$k$-median(p=1$)と社会的にフェアな$k$-means(p=2$)の問題を含む。
多項式時間 $(5+2\sqrt{6})^p$-approximation with at least $k+m$ center (2) a $(5+2\sqrt{6}+\epsilon)^p$-approximation with $k$ center in time $n^{2^{O(p)}\cdot m^2}$, (3) a $(15+6\sqrt{6})^p$ at time $k^{m}\cdot\text{poly}(n)$.} を示す。
第1の結果は,線形プログラム列を用いた反復丸め法の改良により得られた。
後者の2つの結果は、(2)のスパーシフィケーション法を用いて最大$k+m$センターの解を$k$センターの解に変換し、(3)の徹底的な探索によって得られる。
また、アルゴリズムの性能を既存のbicriteriaアルゴリズムと比較し、ベンチマークデータセット上のセンター近似アルゴリズムを正確に$k$で評価し、我々のアルゴリズムが既存のメソッドを実際に上回っていることも確認した。
関連論文リスト
- 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) - Diversity-aware clustering: Computational Complexity and Approximation
Algorithms [19.67390261007849]
本稿では,データポイントが複数の属性に関連付けられ,グループ間の交差が生じている,多様性を考慮したクラスタリング問題について検討する。
クラスタリングソリューションは、各グループから最小数のクラスタセンターが選択されることを保証する必要がある。
近似比が1+ frac2e$, $1+frac8e$, 3,$のパラメータ化近似アルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-01-10T19:01:05Z) - Do you know what q-means? [50.045011844765185]
クラスタリングは、大規模なデータセットを分析する上で最も重要なツールの1つである。
クラスタリングのための"$q$-means"アルゴリズムの改良版を提案する。
また、$Obig(frack2varepsilon2(sqrtkd + log(Nd))big で実行される $varepsilon に対する "dequantized" アルゴリズムも提示する。
論文 参考訳（メタデータ） (2023-08-18T17:52:12Z) - Near-Optimal Quantum Coreset Construction Algorithms for Clustering [15.513270929560088]
我々は、$tildeO(sqrtnkd3/2)$クエリ複雑性を持つ$mathbbRd$で$k$-clusteringのコアセットを見つける量子アルゴリズムを与える。
私たちのコアセットは入力サイズを$n$から$mathrmpoly(kepsilon-1d)$に減らします。
論文 参考訳（メタデータ） (2023-06-05T12:22:46Z) - Replicable Clustering [57.19013971737493]
我々は,統計学的な$k$-medians,統計学的な$k$-means,統計学的な$k$-centers問題のアルゴリズムをブラックボックス方式で近似ルーチンを用いて提案する。
理論的結果を検証するブラックボックスとしてsklearnの$k$-means++実装を用いた2次元合成分布の実験も行っている。
論文 参考訳（メタデータ） (2023-02-20T23:29:43Z) - TURF: A Two-factor, Universal, Robust, Fast Distribution Learning
Algorithm [64.13217062232874]
最も強力で成功したモダリティの1つは、全ての分布を$ell$距離に近似し、基本的に最も近い$t$-piece次数-$d_$の少なくとも1倍大きい。
本稿では,この数値をほぼ最適に推定する手法を提案する。
論文 参考訳（メタデータ） (2022-02-15T03:49:28Z) - Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean
Estimation [58.24280149662003]
本稿では,データセットの大部分を敵が破壊できるリストデコタブル平均推定の問題について検討する。
我々は、ほぼ最適な統計的保証を達成するために、リストデコダブル平均推定のための新しいアルゴリズムを開発した。
論文 参考訳（メタデータ） (2021-06-16T03:34:14Z) - Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample
Complexity [59.34067736545355]
S$状態、$A$アクション、割引係数$gamma in (0,1)$、近似しきい値$epsilon > 0$の MDP が与えられた場合、$epsilon$-Optimal Policy を学ぶためのモデルなしアルゴリズムを提供する。
十分小さな$epsilon$の場合、サンプルの複雑さで改良されたアルゴリズムを示す。
論文 参考訳（メタデータ） (2020-06-06T13:34:41Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。