論文の概要: Parameterized Approximation Schemes for Clustering with General Norm Objectives

• arxiv url: http://arxiv.org/abs/2304.03146v1
• Date: Thu, 6 Apr 2023 15:31:37 GMT
• ステータス: 処理完了
• システム内更新日: 2023-04-07 13:53:57.188528
• Title: Parameterized Approximation Schemes for Clustering with General Norm Objectives
• Title（参考訳）: 一般目的のクラスタリングのためのパラメータ化近似スキーム
• Authors: Fateme Abbasi and Sandip Banerjee and Jaros{\l}aw Byrka and Parinya Chalermsook and Ameet Gadekar and Kamyar Khodamoradi and D\'aniel Marx and Roohani Sharma and Joachim Spoerhase
• Abstract要約: 本稿では、$(k,epsilon)$-approximationアルゴリズムを$k$-clustering問題に対して設計する、よく研究されている方式について考察する。 私たちの主な貢献は、クリーンでシンプルなEPASで、10以上のクラスタリング問題を解決しています。
• 参考スコア（独自算出の注目度）: 0.6956677722498498
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: This paper considers the well-studied algorithmic regime of designing a $(1+\epsilon)$-approximation algorithm for a $k$-clustering problem that runs in time $f(k,\epsilon)poly(n)$ (sometimes called an efficient parameterized approximation scheme or EPAS for short). Notable results of this kind include EPASes in the high-dimensional Euclidean setting for $k$-center [Bad\u{o}iu, Har-Peled, Indyk; STOC'02] as well as $k$-median, and $k$-means [Kumar, Sabharwal, Sen; J. ACM 2010]. However, existing EPASes handle only basic objectives (such as $k$-center, $k$-median, and $k$-means) and are tailored to the specific objective and metric space. Our main contribution is a clean and simple EPAS that settles more than ten clustering problems (across multiple well-studied objectives as well as metric spaces) and unifies well-known EPASes. Our algorithm gives EPASes for a large variety of clustering objectives (for example, $k$-means, $k$-center, $k$-median, priority $k$-center, $\ell$-centrum, ordered $k$-median, socially fair $k$-median aka robust $k$-median, or more generally monotone norm $k$-clustering) and metric spaces (for example, continuous high-dimensional Euclidean spaces, metrics of bounded doubling dimension, bounded treewidth metrics, and planar metrics). Key to our approach is a new concept that we call bounded $\epsilon$-scatter dimension--an intrinsic complexity measure of a metric space that is a relaxation of the standard notion of bounded doubling dimension. Our main technical result shows that two conditions are essentially sufficient for our algorithm to yield an EPAS on the input metric $M$ for any clustering objective: (i) The objective is described by a monotone (not necessarily symmetric!) norm, and (ii) the $\epsilon$-scatter dimension of $M$ is upper bounded by a function of $\epsilon$.
• Abstract（参考訳）: 本稿では,計算時間$f(k,\epsilon)poly(n)$(短時間で効率的なパラメータ化近似スキームあるいはepasと呼ばれることもある)で動作する,k$クラスタ問題に対する$(1+\epsilon)$近似アルゴリズムの設計手法について考察する。 この種の注目すべき結果には、$k$-center [Bad\u{o}iu, Har-Peled, Indyk; STOC'02] の高次元ユークリッド設定におけるEPASeと$k$-median, $k$-means [Kumar, Sabharwal, Sen; J. ACM 2010] がある。 しかしながら、既存のepaseは基本的な目的($k$-center、$k$-median、$k$-meansなど)のみを扱い、特定の目的と計量空間に合わせたものである。 我々の主な貢献は、クリーンでシンプルなEPASであり、10以上のクラスタリング問題(複数のよく研究された目的と計量空間)を解決し、よく知られたEPASeを統合する。 このアルゴリズムは,多種多様なクラスタリング対象(例えば,$k$-means, $k$-center, $k$-median, priority $k$-centrum, $\ell$-median, order $k$-median, socially fair $k$-median aka robust $k$-median, or more generally monotone norm $k$-clustering)と距離空間(例えば,連続高次元ユークリッド空間,有界二重次元のメトリクス,有界木幅メトリクス,平面メトリクス)に対してepaseを与える。 我々のアプローチの鍵となるのは、有界な$\epsilon$-scatter次元と呼ばれる新しい概念です。 我々の主な技術的結果は、2つの条件が本質的に我々のアルゴリズムが任意のクラスタリングの目的に対して入力メトリック$m$のepaを得るのに十分であることを示している。 (i)目的はモノトーン(必ずしも対称ではない!)ノルムによって記述され、 (ii)$\epsilon$-scatter dimension of $M$は、$\epsilon$の関数によって上界となる。

関連論文リスト

• 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)
• Diversity-aware clustering: Computational Complexity and Approximation Algorithms [19.67390261007849]
  本稿では,データポイントが複数の属性に関連付けられ,グループ間の交差が生じている,多様性を考慮したクラスタリング問題について検討する。 クラスタリングソリューションは、各グループから最小数のクラスタセンターが選択されることを保証する必要がある。 近似比が1+ frac2e$, $1+frac8e$, 3,$のパラメータ化近似アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-01-10T19:01:05Z)
• Sketching Algorithms for Sparse Dictionary Learning: PTAS and Turnstile Streaming [48.18845814885398]
  本研究は,スプリス辞書学習とユークリッド語$k$-meansクラスタリング問題に対するスケッチベースアプローチの適用性を高めるための新しい手法を開発した。 高速アルゴリズムでは、$k$-meansクラスタリング問題に対してPTASを設計するための新しいアプローチを得る。 ストリーミングアルゴリズムの分野では、辞書学習と$k$-meansクラスタリングのための新しい上限と下位境界を得る。
  論文  参考訳（メタデータ） (2023-10-29T16:46:26Z)
• Parameterized Approximation for Robust Clustering in Discrete Geometric Spaces [2.687607197645453]
  次元$Theta(log n)$ が $(sqrt3/2-o(1))$hard である場合でさえ、FPTアルゴリズムを近似する。 また、次元 $Theta(log n)$ が $(sqrt3/2-o(1))$hard であるような特別な場合でさえ、FPTアルゴリズムを近似することを示す。
  論文  参考訳（メタデータ） (2023-05-12T08:43:28Z)
• Replicable Clustering [57.19013971737493]
  我々は,統計学的な$k$-medians,統計学的な$k$-means,統計学的な$k$-centers問題のアルゴリズムをブラックボックス方式で近似ルーチンを用いて提案する。 理論的結果を検証するブラックボックスとしてsklearnの$k$-means++実装を用いた2次元合成分布の実験も行っている。
  論文  参考訳（メタデータ） (2023-02-20T23:29:43Z)
• Pseudonorm Approachability and Applications to Regret Minimization [73.54127663296906]
  我々は、高次元 $ell_infty$-approachability 問題を、低次元の擬ノルムアプローチ可能性問題に変換する。 我々は、$ell$や他のノルムに対するアプローチ可能性に関する以前の研究に類似した疑似ノルムアプローチ可能性のアルゴリズム理論を開発する。
  論文  参考訳（メタデータ） (2023-02-03T03:19:14Z)
• 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)
• Distributed k-Means with Outliers in General Metrics [0.6117371161379208]
  一般距離空間に対する$z$アウトレイアを持つk平均に対する分散コアセットに基づく3ラウンド近似アルゴリズムを提案する。 我々のアルゴリズムの重要な特徴は、距離空間の2倍の次元で捉えられたデータセットの本質的な複雑さに鮮明に適応することである。
  論文  参考訳（メタデータ） (2022-02-16T16:24:31Z)
• Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean Estimation [58.24280149662003]
  本稿では,データセットの大部分を敵が破壊できるリストデコタブル平均推定の問題について検討する。 我々は、ほぼ最適な統計的保証を達成するために、リストデコダブル平均推定のための新しいアルゴリズムを開発した。
  論文  参考訳（メタデータ） (2021-06-16T03:34:14Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。