Fugu-MT 論文翻訳(概要): Single-Pass Pivot Algorithm for Correlation Clustering. Keep it simple!

論文の概要: Single-Pass Pivot Algorithm for Correlation Clustering. Keep it simple!

arxiv url: http://arxiv.org/abs/2305.13560v1
Date: Tue, 23 May 2023 00:15:56 GMT
ステータス: 処理完了
システム内更新日: 2023-05-24 19:59:29.776749
Title: Single-Pass Pivot Algorithm for Correlation Clustering. Keep it simple!
Title（参考訳）: 相関クラスタリングのためのシングルパスPivotアルゴリズムシンプルにしておけ!
Authors: Sayak Chakrabarty and Konstantin Makarychev
Abstract要約: 相関クラスタリングのためのPivotアルゴリズムの単純なシングルパス半ストリーミング変種は、O(n/epsilon)ワードのメモリを用いた3+epsilon-近似を与える。この論文の主な貢献の1つは、アルゴリズムとその分析が非常に単純であり、また、アルゴリズムの実装も容易であることである。
参考スコア（独自算出の注目度）: 11.536162323162099
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: We show that a simple single-pass semi-streaming variant of the Pivot algorithm for Correlation Clustering gives a (3 + {\epsilon})-approximation using O(n/{\epsilon}) words of memory. This is a slight improvement over the recent results of Cambus, Kuhn, Lindy, Pai, and Uitto, who gave a (3 + {\epsilon})-approximation using O(n log n) words of memory, and Behnezhad, Charikar, Ma, and Tan, who gave a 5-approximation using O(n) words of memory. One of the main contributions of this paper is that both the algorithm and its analysis are very simple, and also the algorithm is easy to implement.
Abstract（参考訳）: 相関クラスタリングのためのピボットアルゴリズムの単純な単一パスセミストリーミング変種は、o(n/{\epsilon})ワードオブメモリを用いて (3 + {\epsilon})近似を与える。これは、Cambus、Kuhn、Lindy、Pai、UittoがO(n log n)ワードのメモリを使った3 + {\epsilon}-近似を、Behnezhad、Charikar、Ma、TanがO(n)ワードのメモリを使った5-近似を施した最近の結果よりもわずかに改善されている。この論文の主な貢献の1つは、アルゴリズムとその分析が非常に単純であり、また、アルゴリズムの実装も容易であることである。

関連論文リスト

Combinatorial Approximations for Cluster Deletion: Simpler, Faster, and Better [18.121514220195607]
クラスタ削除は、計算およびソーシャルネットワーク分析におけるNPハードグラフクラスタリングの目的である。まず,2つの近似アルゴリズムの厳密な解析を行い,その近似保証を4から3に改善する。補助グラフにおいて最大等級を優しく取り、その周囲にクラスタを形成することにより、両アルゴリズムを驚くほど単純な方法でデランドマイズすることができることを示す。
論文参考訳（メタデータ） (2024-04-24T18:39:18Z)
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)
Do you know what q-means? [50.045011844765185]
クラスタリングは、大規模なデータセットを分析する上で最も重要なツールの1つである。クラスタリングのための"$q$-means"アルゴリズムの改良版を提案する。また、$Obig(frack2varepsilon2(sqrtkd + log(Nd))big で実行される $varepsilon に対する "dequantized" アルゴリズムも提示する。
論文参考訳（メタデータ） (2023-08-18T17:52:12Z)
Quick Adaptive Ternary Segmentation: An Efficient Decoding Procedure For Hidden Markov Models [70.26374282390401]
ノイズの多い観測から元の信号(すなわち隠れ鎖)を復号することは、ほぼすべてのHMMに基づくデータ分析の主要な目標の1つである。本稿では,多対数計算複雑性において隠れた列を復号化するための分法であるQuick Adaptive Ternary(QATS)を提案する。
論文参考訳（メタデータ） (2023-05-29T19:37:48Z)
Discrete Morse Sandwich: Fast Computation of Persistence Diagrams for Scalar Data -- An Algorithm and A Benchmark [8.648433479399857]
本稿では,d-次元単純複素数 K 上で定義される入力片方向線形スカラー場 f を与えられた永続図計算の効率的なアルゴリズムを提案する。我々はこのアルゴリズムを離散モース理論の設定内で表現し、考慮すべき入力単純さの数を著しく削減する。また、この問題に対して「サンドウィッチ」と呼ばれる階層化アプローチを導入する。
論文参考訳（メタデータ） (2022-06-27T10:54:24Z)
Sublinear Time and Space Algorithms for Correlation Clustering via Sparse-Dense Decompositions [9.29659220237395]
本稿では,相関クラスタリングの解法を提案する。我々は高効率な時間と空間の複雑さを持つサブ線形アルゴリズムを得る。提案手法の主な要素はスパース線グラフ分解への新規な接続である。
論文参考訳（メタデータ） (2021-09-29T16:25:02Z)
Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean Estimation [58.24280149662003]
本稿では,データセットの大部分を敵が破壊できるリストデコタブル平均推定の問題について検討する。我々は、ほぼ最適な統計的保証を達成するために、リストデコダブル平均推定のための新しいアルゴリズムを開発した。
論文参考訳（メタデータ） (2021-06-16T03:34:14Z)
Hierarchical Agglomerative Graph Clustering in Nearly-Linear Time [1.5644420658691407]
エッジ重み付きグラフ上での階層的凝集クラスタリング(HAC)アルゴリズムについて検討する。階層的な集合グラフクラスタリングのためのアルゴリズムフレームワークを定義する。提案手法は,ポイントデータセットのクラスタリングを20.7～76.5倍の速度で高速化できることを示す。
論文参考訳（メタデータ） (2021-06-10T09:29:05Z)
Relational Algorithms for k-means Clustering [17.552485682328772]
本稿では,関係アルゴリズムモデルにおいて効率的なk平均近似アルゴリズムを提案する。実行時間は潜在的に$N$よりも小さくなり、リレーショナルデータベースが表すデータポイントの数はクラスタ化される。
論文参考訳（メタデータ） (2020-08-01T23:21:40Z)
Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文参考訳（メタデータ） (2020-07-07T17:10:00Z)

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