論文の概要: Improved Approximations for Euclidean $k$-means and $k$-median, via Nested Quasi-Independent Sets

• arxiv url: http://arxiv.org/abs/2204.04828v1
• Date: Mon, 11 Apr 2022 02:19:40 GMT
• ステータス: 処理完了
• システム内更新日: 2022-04-12 19:01:17.966189
• Title: Improved Approximations for Euclidean $k$-means and $k$-median, via Nested Quasi-Independent Sets
• Title（参考訳）: Nested Quasi-Independent Setsによるユークリッド$k$-meansおよび$k$-medianの近似の改善
• Authors: Vincent Cohen-Addad, Hossein Esfandiari, Vahab Mirrokni, Shyam Narayanan
• Abstract要約: 我々は高次元ユークリッド$k$-medianおよび$k$-means問題に対する原始双対アルゴリズムを提案する。 このアルゴリズムはユークリッドの$k$-median と $k$-means に対してそれぞれ2.406$ と 5.912$ の近似比を達成する。 逆に、この手法はユークリッド空間や $ell_p$ 計量空間の他の最適化問題にも興味があるかもしれない。
• 参考スコア（独自算出の注目度）: 34.92651216338062
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Motivated by data analysis and machine learning applications, we consider the popular high-dimensional Euclidean $k$-median and $k$-means problems. We propose a new primal-dual algorithm, inspired by the classic algorithm of Jain and Vazirani and the recent algorithm of Ahmadian, Norouzi-Fard, Svensson, and Ward. Our algorithm achieves an approximation ratio of $2.406$ and $5.912$ for Euclidean $k$-median and $k$-means, respectively, improving upon the 2.633 approximation ratio of Ahmadian et al. and the 6.1291 approximation ratio of Grandoni, Ostrovsky, Rabani, Schulman, and Venkat. Our techniques involve a much stronger exploitation of the Euclidean metric than previous work on Euclidean clustering. In addition, we introduce a new method of removing excess centers using a variant of independent sets over graphs that we dub a "nested quasi-independent set". In turn, this technique may be of interest for other optimization problems in Euclidean and $\ell_p$ metric spaces.
• Abstract（参考訳）: データ分析や機械学習の応用によって動機付けられた、一般的な高次元ユークリッドの$k$-medianと$k$-meansの問題を考える。 本稿では,ジャイナとヴァジラニの古典的アルゴリズムと,Ahmadian,Noouzi-Fard,Svensson,Wardの最近のアルゴリズムに着想を得た新しい原始双対アルゴリズムを提案する。 このアルゴリズムは、euclidean $k$medianと$k$-meansに対してそれぞれ2.406$と5.912$の近似比を達成し、ahmadian et al.の2.633近似比とgrandoni、ostrovsky、rabani、schulman、venkatの6.1291近似比を改善した。 我々の手法は、以前のユークリッドクラスタリングの研究よりもはるかに強いユークリッド計量の活用を含む。 さらに,我々は「ネスト準独立集合」をダビングするグラフ上の独立集合の変種を用いて,余剰中心を除去する新しい方法を提案する。 逆に、この手法はユークリッド空間や$\ell_p$計量空間における他の最適化問題にも興味を持つ。

関連論文リスト

• 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)
• 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)
• Parameterized Approximation Schemes for Clustering with General Norm Objectives [0.6956677722498498]
  本稿では、$(k,epsilon)$-approximationアルゴリズムを$k$-clustering問題に対して設計する、よく研究されている方式について考察する。 私たちの主な貢献は、クリーンでシンプルなEPASで、10以上のクラスタリング問題を解決しています。
  論文  参考訳（メタデータ） (2023-04-06T15:31:37Z)
• Differentially-Private Hierarchical Clustering with Provable Approximation Guarantees [79.59010418610625]
  階層クラスタリングのための微分プライベート近似アルゴリズムについて検討する。 例えば、$epsilon$-DPアルゴリズムは入力データセットに対して$O(|V|2/epsilon)$-additiveエラーを示さなければならない。 本稿では,ブロックを正確に復元する1+o(1)$近似アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-01-31T19:14:30Z)
• Private estimation algorithms for stochastic block models and mixture models [63.07482515700984]
  効率的なプライベート推定アルゴリズムを設計するための一般的なツール。 最初の効率的な$(epsilon, delta)$-differentially private algorithm for both weak recovery and exact recovery。
  論文  参考訳（メタデータ） (2023-01-11T09:12:28Z)
• 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)
• Byzantine-Robust Federated Linear Bandits [27.77095339417368]
  分散エージェントの集合が共通の線形帯域モデルを協調的に学習するフェデレート環境で線形帯域最適化問題を研究する。 標準的な連邦学習アルゴリズムは、少数のエージェントに対するビザンチン攻撃に対して脆弱である。 提案アルゴリズムは, エージェントの半数未満に対するビザンチン攻撃に対して堅牢であり, サブ線形$tildemathcalO(T3/4)$ regret with $mathcalO(sqrtT)$ steps of communicationを実現している。
  論文  参考訳（メタデータ） (2022-04-03T20:22:26Z)
• Byzantine-Resilient Non-Convex Stochastic Gradient Descent [61.6382287971982]
  敵対的レジリエントな分散最適化。 機械は独立して勾配を計算し 協力することができます 私達のアルゴリズムは新しい集中の技術およびサンプル複雑性に基づいています。 それは非常に実用的です:それはないときすべての前の方法の性能を改善します。 セッティングマシンがあります。
  論文  参考訳（メタデータ） (2020-12-28T17:19:32Z)
• Hardness of Approximation of Euclidean $k$-Median [0.25782420501870296]
  a set $mathcalX$ of $n$ points in $mathbbRd$, find a set $C subset mathbbRd$ of $k$ points(センターと呼ばれる)。 本研究では、ユークリッドの$k$-median問題に対する近似結果の最初の難しさについて述べる。
  論文  参考訳（メタデータ） (2020-11-09T06:50:34Z)

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

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