論文の概要: Approximating Fair $k$-Min-Sum-Radii in $\mathbb{R}^d$
- arxiv url: http://arxiv.org/abs/2309.00834v1
- Date: Sat, 2 Sep 2023 06:01:59 GMT
- ステータス: 処理完了
- システム内更新日: 2023-09-07 00:57:19.142441
- Title: Approximating Fair $k$-Min-Sum-Radii in $\mathbb{R}^d$
- Title（参考訳）: フェア$k$-Min-Sum-Radii in $\mathbb{R}^d$
- Authors: Lukas Drexler, Annika Hennes, Abhiruk Lahiri, Melanie Schmidt, Julian
Wargalla
- Abstract要約: 定数$k$の場合の任意の次元のユークリッド空間における$k$-min-sum-radii問題を研究する。
定数$k$の場合の任意の次元のユークリッド空間における公平な$k$-min-sum-radii問題に対するPTASを提案する。
- 参考スコア（独自算出の注目度）: 1.7561849652813544
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The $k$-center problem is a classical clustering problem in which one is
asked to find a partitioning of a point set $P$ into $k$ clusters such that the
maximum radius of any cluster is minimized. It is well-studied. But what if we
add up the radii of the clusters instead of only considering the cluster with
maximum radius? This natural variant is called the $k$-min-sum-radii problem.
It has become the subject of more and more interest in recent years, inspiring
the development of approximation algorithms for the $k$-min-sum-radii problem
in its plain version as well as in constrained settings.
We study the problem for Euclidean spaces $\mathbb{R}^d$ of arbitrary
dimension but assume the number $k$ of clusters to be constant. In this case, a
PTAS for the problem is known (see Bandyapadhyay, Lochet and Saurabh, SoCG,
2023). Our aim is to extend the knowledge base for $k$-min-sum-radii to the
domain of fair clustering. We study several group fairness constraints, such as
the one introduced by Chierichetti et al. (NeurIPS, 2017). In this model, input
points have an additional attribute (e.g., colors such as red and blue), and
clusters have to preserve the ratio between different attribute values (e.g.,
have the same fraction of red and blue points as the ground set). Different
variants of this general idea have been studied in the literature. To the best
of our knowledge, no approximative results for the fair $k$-min-sum-radii
problem are known, despite the immense amount of work on the related fair
$k$-center problem.
We propose a PTAS for the fair $k$-min-sum-radii problem in Euclidean spaces
of arbitrary dimension for the case of constant $k$. To the best of our
knowledge, this is the first PTAS for the problem. It works for different
notions of group fairness.
- Abstract（参考訳）: k$-center問題(英語版)は古典的なクラスタリング問題であり、任意のクラスタの最大半径が最小になるように、$p$を$k$クラスタに設定したポイントの分割を求める。
よく研究されている。
しかし、最大半径のクラスタのみを考えるのではなく、クラスタの半径を加算すればどうだろうか?
この自然変種は$k$-min-sum-radii 問題と呼ばれる。
近年ではますます関心が高まり、通常のバージョンや制約された設定でk$-min-sum-radii問題の近似アルゴリズムの開発に刺激されている。
任意の次元のユークリッド空間 $\mathbb{R}^d$ の問題を研究するが、クラスターの数 $k$ は定数であると仮定する。
この場合、問題のPTASが知られている(Bandyapadhyay, Lochet and Saurabh, SoCG, 2023)。
我々の目標は、$k$-min-sum-radiiの知識ベースをフェアクラスタリングの領域に拡張することです。
本研究では,Chierichettiらによって導入されたもの(NeurIPS, 2017)など,グループフェアネスの制約について検討する。
このモデルでは、入力ポイントは追加の属性(例えば赤や青のような色)を持ち、クラスタは異なる属性値の比率を保存しなければならない(例えば、基底集合と同じ赤と青の点を持つ)。
この一般的な考え方の異なる変種が文献で研究されている。
私たちの知る限りでは、適切な$k$-sum-radii問題に対して、関連する$k$-center問題に関する膨大な作業にもかかわらず、近似的な結果が知られていない。
定数$k$の場合の任意の次元のユークリッド空間における$k$-min-sum-radii問題に対するPTASを提案する。
私たちの知る限りでは、この問題に対する最初のPTASです。
群フェアネスの異なる概念に対して作用する。
関連論文リスト
- 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) - Clustering to Minimize Cluster-Aware Norm Objectives [0.3481985817302898]
与えられたデータセットの$P$を$k$クラスタに分割し、$X$の$k$センターを見つける。
中心の$xin X$で表されるクラスタのコストは、x$に割り当てられた点の距離のベクトルの単調で対称なノルム$f$(インナーノルム)である。
目標は、クラスタコストのベクトルのノルム$g$(外部ノルム)を最小化することである。
論文 参考訳（メタデータ） (2024-10-31T16:33:40Z) - 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) - Sketching Algorithms for Sparse Dictionary Learning: PTAS and Turnstile
Streaming [48.18845814885398]
本研究は,スプリス辞書学習とユークリッド語$k$-meansクラスタリング問題に対するスケッチベースアプローチの適用性を高めるための新しい手法を開発した。
高速アルゴリズムでは、$k$-meansクラスタリング問題に対してPTASを設計するための新しいアプローチを得る。
ストリーミングアルゴリズムの分野では、辞書学習と$k$-meansクラスタリングのための新しい上限と下位境界を得る。
論文 参考訳（メタデータ） (2023-10-29T16:46:26Z) - Optimal Algorithms for Latent Bandits with Cluster Structure [50.44722775727619]
本稿では,複数のユーザが存在するクラスタ構造を持つ潜伏包帯問題と関連するマルチアーム包帯問題とを考察する。
本稿では,潜伏クラスタ構造を利用して$widetildeO(sqrt(mathsfM+mathsfN)mathsfTの最小限の後悔を提供するLATTICEを提案する。
論文 参考訳（メタデータ） (2023-01-17T17:49:04Z) - 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) - Fuzzy Clustering with Similarity Queries [56.96625809888241]
ファジィ(fuzzy, soft objective)は、よく知られた$k$-means問題の一般化である。
クエリを少なくすることで、問題の解決が容易になる。
論文 参考訳（メタデータ） (2021-06-04T02:32:26Z) - Revisiting Priority $k$-Center: Fairness and Outliers [5.3898004059026325]
我々は,プライオリティ $k$-center に対して定数係数近似アルゴリズムを導出するフレームワークを開発した。
私たちのフレームワークは,matroid と knapsack の制約に対する優先度 $k$-center の一般化にも拡張しています。
論文 参考訳（メタデータ） (2021-03-04T21:15:37Z) - Near-Optimal Regret Bounds for Contextual Combinatorial Semi-Bandits
with Linear Payoff Functions [53.77572276969548]
我々は、C$2$UCBアルゴリズムが分割マトロイド制約に対して最適な後悔結合$tildeO(dsqrtkT + dk)$を有することを示した。
一般的な制約に対して,C$2$UCBアルゴリズムで腕の報酬推定値を変更するアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-01-20T04:29:18Z) - Computationally efficient sparse clustering [67.95910835079825]
我々はPCAに基づく新しいクラスタリングアルゴリズムの有限サンプル解析を行う。
ここでは,ミニマックス最適誤クラスタ化率を,体制$|theta infty$で達成することを示す。
論文 参考訳（メタデータ） (2020-05-21T17:51:30Z) - Structures of Spurious Local Minima in $k$-means [20.155509538529568]
我々は、$k$-means問題に対する急激な局所解の構造について検討する。
分離条件下では,この現象が唯一の局所的局所最小値であることを示す。
論文 参考訳（メタデータ） (2020-02-16T22:15:03Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。