論文の概要: Revisiting Priority $k$-Center: Fairness and Outliers
- arxiv url: http://arxiv.org/abs/2103.03337v1
- Date: Thu, 4 Mar 2021 21:15:37 GMT
- ステータス: 処理完了
- システム内更新日: 2021-03-08 14:40:34.006283
- Title: Revisiting Priority $k$-Center: Fairness and Outliers
- Title（参考訳）: プライオリティの見直し$k$-Center:フェアネスとアウトリーチ
- Authors: Tanvi Bajpai, Deeparnab Chakrabarty, Chandra Chekuri, Maryam Negahbani
- Abstract要約: 我々は,プライオリティ $k$-center に対して定数係数近似アルゴリズムを導出するフレームワークを開発した。
私たちのフレームワークは,matroid と knapsack の制約に対する優先度 $k$-center の一般化にも拡張しています。
- 参考スコア（独自算出の注目度）: 5.3898004059026325
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In the Priority $k$-Center problem, the input consists of a metric space
$(X,d)$, an integer $k$ and for each point $v \in X$ a priority radius $r(v)$.
The goal is to choose $k$-centers $S \subseteq X$ to minimize $\max_{v \in X}
\frac{1}{r(v)} d(v,S)$. If all $r(v)$'s were uniform, one obtains the classical
$k$-center problem. Plesn\'ik [Plesn\'ik, Disc. Appl. Math. 1987] introduced
this problem and gave a $2$-approximation algorithm matching the best possible
algorithm for vanilla $k$-center. We show how the problem is related to two
different notions of fair clustering [Harris et al., NeurIPS 2018; Jung et al.,
FORC 2020]. Motivated by these developments we revisit the problem and, in our
main technical contribution, develop a framework that yields constant factor
approximation algorithms for Priority $k$-Center with outliers. Our framework
extends to generalizations of Priority $k$-Center to matroid and knapsack
constraints, and as a corollary, also yields algorithms with fairness
guarantees in the lottery model of Harris et al.
- Abstract（参考訳）: 優先度 $k$-Center 問題では、入力は計量空間 $(X,d)$ と整数 $k$ と、各点 $v \in X$ の優先度半径 $r(v)$ からなる。
目標は $k$-centers $S \subseteq X$ を選び、$\max_{v \in X} \frac{1}{r(v)} d(v,S)$ を最小化することである。
すべての$r(v)$ が一様であれば、古典的な $k$-center 問題が得られる。
Plesn\'ik [Plesn\'ik, Disc。
アプリ。
数学。
1987年]この問題を導入し、バニラ$k$-centerの最良のアルゴリズムと一致する2ドルの近似アルゴリズムを与えた。
この問題は、フェアクラスタリングの2つの異なる概念 [Harris et al., NeurIPS 2018; Jung et al., FORC 2020] とどのように関連しているかを示します。
これらの開発に動機づけられて、我々は問題を再検討し、私たちの主な技術的貢献では、優先度$ k$-Centerの定数因子近似アルゴリズムを生成するフレームワークを開発します。
我々のフレームワークは、行列やknapsackの制約に$k$-Centerのプライオリティの一般化にまで拡張され、また、論理的にハリスらの宝くじモデルにおいて公平性を保証するアルゴリズムも得られる。
関連論文リスト
- Nearly Linear Sparsification of $\ell_p$ Subspace Approximation [47.790126028106734]
$ell_p$ 部分空間近似問題のNP硬度に対処する一般的なアプローチは、強いコアセットを計算することである。
我々は、$ell_p$部分空間近似に対して、ランクパラメータ$k$にほぼ最適に依存する強いコアセットを構築するための最初のアルゴリズムを得る。
我々の手法は、オフライン設定と同様のバウンダリを持つ$ell_p$サブスペース近似のための、ほぼ最適に近いオンライン強力なコアセットにも繋がる。
論文 参考訳（メタデータ） (2024-07-03T16:49:28Z) - 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) - Approximating Fair $k$-Min-Sum-Radii in Euclidean Space [1.6369404745833038]
定数$k$の場合の任意の次元のユークリッド空間における$k$-min-sum-radii問題を研究する。
定数$k$の場合の任意の次元のユークリッド空間における公平な$k$-min-sum-radii問題に対するPTASを提案する。
論文 参考訳（メタデータ） (2023-09-02T06:01:59Z) - Do you know what q-means? [50.045011844765185]
クラスタリングは、大規模なデータセットを分析する上で最も重要なツールの1つである。
クラスタリングのための"$q$-means"アルゴリズムの改良版を提案する。
また、$Obig(frack2varepsilon2(sqrtkd + log(Nd))big で実行される $varepsilon に対する "dequantized" アルゴリズムも提示する。
論文 参考訳（メタデータ） (2023-08-18T17:52:12Z) - Improved Learning-augmented Algorithms for k-means and k-medians
Clustering [8.04779839951237]
学習強化設定におけるクラスタリングの問題について考察し、そこでは、$d$次元ユークリッド空間のデータセットが与えられる。
本稿では,クラスタリングコストを改良したセンターを生成する決定論的$k$-meansアルゴリズムを提案する。
我々のアルゴリズムは、予測があまり正確でないときでも機能する。つまり、我々の限界は$alpha$を$/2$に保ち、以前の研究で$alpha$よりも1/7$に改善する。
論文 参考訳（メタデータ） (2022-10-31T03:00:11Z) - Corralling a Larger Band of Bandits: A Case Study on Switching Regret
for Linear Bandits [99.86860277006318]
本稿では,一組の逆アルゴリズムを組み合わせ,学習することの問題点について考察する。
Agarwal et al. の CORRAL はこの目標を、$widetildeO(sqrtd S T)$ の残酷なオーバーヘッドで達成している。
この問題に触発されて、後悔のオーバーヘッドが百万ドルにしか依存しない大規模バンディットアルゴリズムのバンドを囲む新しいレシピを提案する。
論文 参考訳（メタデータ） (2022-02-12T21:55:44Z) - 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) - Maximizing Determinants under Matroid Constraints [69.25768526213689]
我々は、$det(sum_i in Sv_i v_i v_itop)$が最大になるような基底を$S$$$$M$とする問題を研究する。
この問題は、実験的なデザイン、商品の公平な割り当て、ネットワーク設計、機械学習など、さまざまな分野に現れている。
論文 参考訳（メタデータ） (2020-04-16T19:16:38Z) - Coreset-based Strategies for Robust Center-type Problems [0.6875312133832077]
我々は、効率的なシーケンシャル、MapReduce、ストリーミングアルゴリズムをもたらす2つの問題に対するコアセットベースの戦略を考案する。
パラメータ$k,zepsilon,D$の広い範囲で、$|V|$で実行時間線形のシーケンシャルアルゴリズムと、ラウンド/パスが少なく、実質的にサブ線形な局所/ワーキングメモリを持つMapReduce/ストリーミングアルゴリズムを得る。
論文 参考訳（メタデータ） (2020-02-18T10:04:08Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。