論文の概要: Approximation Algorithms for Socially Fair Clustering
- arxiv url: http://arxiv.org/abs/2103.02512v1
- Date: Wed, 3 Mar 2021 16:36:21 GMT
- ステータス: 処理完了
- システム内更新日: 2021-03-04 15:05:53.716423
- Title: Approximation Algorithms for Socially Fair Clustering
- Title（参考訳）: 社会的公正クラスタリングのための近似アルゴリズム
- Authors: Yury Makarychev and Ali Vakilian
- Abstract要約: 本稿では, $(eO(p) fraclog elllogell)$-approximation algorithm for socially Fair Clustering with the $ell_p$-objectiveを提案する。
- 参考スコア（独自算出の注目度）: 12.63013063147516
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We present an $(e^{O(p)} \frac{\log \ell}{\log\log\ell})$-approximation
algorithm for socially fair clustering with the $\ell_p$-objective. In this
problem, we are given a set of points in a metric space. Each point belongs to
one (or several) of $\ell$ groups. The goal is to find a $k$-medians,
$k$-means, or, more generally, $\ell_p$-clustering that is simultaneously good
for all of the groups. More precisely, we need to find a set of $k$ centers $C$
so as to minimize the maximum over all groups $j$ of $\sum_{u \text{ in group
}j} d(u,C)^p$. The socially fair clustering problem was independently proposed
by Abbasi, Bhaskara, and Venkatasubramanian [2021] and Ghadiri, Samadi, and
Vempala [2021]. Our algorithm improves and generalizes their
$O(\ell)$-approximation algorithms for the problem. The natural LP relaxation
for the problem has an integrality gap of $\Omega(\ell)$. In order to obtain
our result, we introduce a strengthened LP relaxation and show that it has an
integrality gap of $\Theta(\frac{\log \ell}{\log\log\ell})$ for a fixed $p$.
Additionally, we present a bicriteria approximation algorithm, which
generalizes the bicriteria approximation of Abbasi et al. [2021].
- Abstract（参考訳）: 本稿では, $(e^{O(p)} \frac{\log \ell}{\log\log\ell})$-approximation algorithm for socially Fair Clustering with the $\ell_p$-objectiveを提案する。
この問題では、計量空間における点の集合が与えられる。
各点は$\ell$群の1つ(または複数の)に属する。
目標は、$k$-medians、$k$-means、またはより一般的には、すべてのグループに同時に良い$\ell_p$-clusteringを見つけることである。
より正確には、$k$ の中心 $C$ の集合を見つける必要があるので、すべての群 $j$ of $\sum_{u \text{ in group }j} d(u,C)^p$ 上の最大値を最小限に抑える。
社会的に公平なクラスタリング問題は、abbasi, bhaskara, venkatasubramanian [2021] と ghadiri, samadi, vempala [2021] によって独立に提案された。
本アルゴリズムは,この問題に対する$O(\ell)$-approximationアルゴリズムの改良と一般化を行う。
この問題に対する自然なLP緩和は、積分性ギャップが$\Omega(\ell)$である。
この結果を得るために,強化されたLPリラクゼーションを導入し,固定$p$に対して$\Theta(\frac{\log \ell}{\log\log\ell})$の積分ギャップがあることを示した。
さらに,abbasi et alのbicriteria近似を一般化したbicriteria近似アルゴリズムを提案する。
[2021].
関連論文リスト
- 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) - Do you know what q-means? [50.045011844765185]
クラスタリングは、大規模なデータセットを分析する上で最も重要なツールの1つである。
クラスタリングのための"$q$-means"アルゴリズムの改良版を提案する。
また、$Obig(frack2varepsilon2(sqrtkd + log(Nd))big で実行される $varepsilon に対する "dequantized" アルゴリズムも提示する。
論文 参考訳（メタデータ） (2023-08-18T17:52:12Z) - 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) - 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) - Near-optimal Algorithms for Explainable k-Medians and k-Means [12.68470213641421]
Dasgupta, Frost, Moshkovitz, Rashtchian (ICML 2020) が導入した$k$-medians と $k$-means の問題を考える。
私たちのゴールは、データを$kクラスタに分割し、$k-mediansや$k-meansの目的を最小化する、最適な決定ツリーを見つけることです。
論文 参考訳（メタデータ） (2021-07-02T02:07:12Z) - 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) - 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) - Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。
両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文 参考訳（メタデータ） (2020-07-07T17:10:00Z) - 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) - Tight Quantum Lower Bound for Approximate Counting with Quantum States [49.6558487240078]
Aaronson, Kothari, Kretschmer, Thaler (2020) が考える数え上げ問題の次の変種に対する厳密な下界を証明する。
このタスクは、入力セット$xsubseteq [n]$が$k$か$k'=(1+varepsilon)k$であるかどうかを識別する。
論文 参考訳（メタデータ） (2020-02-17T10:53:50Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。