論文の概要: Sublinear Time and Space Algorithms for Correlation Clustering via
Sparse-Dense Decompositions
- arxiv url: http://arxiv.org/abs/2109.14528v1
- Date: Wed, 29 Sep 2021 16:25:02 GMT
- ステータス: 処理完了
- システム内更新日: 2021-09-30 14:37:19.021434
- Title: Sublinear Time and Space Algorithms for Correlation Clustering via
Sparse-Dense Decompositions
- Title（参考訳）: スパース密度分解による相関クラスタリングのための線形時間と空間アルゴリズム
- Authors: Sepehr Assadi, Chen Wang
- Abstract要約: 本稿では,相関クラスタリングの解法を提案する。
我々は高効率な時間と空間の複雑さを持つサブ線形アルゴリズムを得る。
提案手法の主な要素はスパース線グラフ分解への新規な接続である。
- 参考スコア（独自算出の注目度）: 9.29659220237395
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We present a new approach for solving (minimum disagreement) correlation
clustering that results in sublinear algorithms with highly efficient time and
space complexity for this problem. In particular, we obtain the following
algorithms for $n$-vertex $(+/-)$-labeled graphs $G$:
-- A sublinear-time algorithm that with high probability returns a constant
approximation clustering of $G$ in $O(n\log^2{n})$ time assuming access to the
adjacency list of the $(+)$-labeled edges of $G$ (this is almost quadratically
faster than even reading the input once). Previously, no sublinear-time
algorithm was known for this problem with any multiplicative approximation
guarantee.
-- A semi-streaming algorithm that with high probability returns a constant
approximation clustering of $G$ in $O(n\log{n})$ space and a single pass over
the edges of the graph $G$ (this memory is almost quadratically smaller than
input size). Previously, no single-pass algorithm with $o(n^2)$ space was known
for this problem with any approximation guarantee.
The main ingredient of our approach is a novel connection to sparse-dense
graph decompositions that are used extensively in the graph coloring
literature. To our knowledge, this connection is the first application of these
decompositions beyond graph coloring, and in particular for the correlation
clustering problem, and can be of independent interest.
- Abstract（参考訳）: 本稿では,この問題に対して,高効率な時間と空間の複雑さを持つ部分線形アルゴリズムを導出する(最小不一致)相関クラスタリングの解法を提案する。
特に、$n$-vertex $(+/-)$-labeled graphs $g$: -- 確率の高い部分線形時間アルゴリズムは、$(+)$-labeled edges $g$の隣接リストへのアクセスを仮定して、$g$ in $o(n\log^2{n})$ の定数近似クラスタリングを返す。
以前は、この問題を乗算近似を保証するサブ線形時間アルゴリズムは知られていない。
-- 確率の高い半ストリーミングアルゴリズムは、定数近似クラスタリングとして$o(n\log{n})$スペースに$g$を返し、グラフのエッジに1つのパスで$g$を渡す(このメモリは入力サイズよりほぼ2倍小さい)。
従来、o(n^2)$空間を持つ単一パスアルゴリズムは、近似保証なしでは知られていた。
提案手法の主な要素は,グラフカラー化の文献で広く用いられているスパース線グラフ分解への新規な接続である。
我々の知る限り、この接続はグラフカラー化以外の分解の最初の応用であり、特に相関クラスタリング問題に対して、独立した関心を持つことができる。
関連論文リスト
- Almost-linear Time Approximation Algorithm to Euclidean $k$-median and $k$-means [4.271492285528115]
Euclidean $k$-medianと$k$-meansの問題、クラスタリングのタスクをモデル化する標準的な2つの方法に注目します。
本稿では,定数係数近似を計算するためのほぼ線形時間アルゴリズムを提案することにより,この問題にほぼ答える。
論文 参考訳（メタデータ） (2024-07-15T20:04:06Z) - 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) - Do you know what q-means? [50.045011844765185]
クラスタリングは、大規模なデータセットを分析する上で最も重要なツールの1つである。
クラスタリングのための"$q$-means"アルゴリズムの改良版を提案する。
また、$Obig(frack2varepsilon2(sqrtkd + log(Nd))big で実行される $varepsilon に対する "dequantized" アルゴリズムも提示する。
論文 参考訳（メタデータ） (2023-08-18T17:52:12Z) - Efficiently Learning One-Hidden-Layer ReLU Networks via Schur
Polynomials [50.90125395570797]
正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。
本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
論文 参考訳（メタデータ） (2023-07-24T14:37:22Z) - Differentially Private Clustering in Data Streams [65.78882209673885]
オフラインのDPコアセットやクラスタリングアルゴリズムをブラックボックスとしてのみ必要とする,差分プライベートなストリーミングクラスタリングフレームワークを提案する。
我々のフレームワークはまた、連続的なリリース設定の下で微分プライベートであり、すなわち、全てのタイムスタンプにおけるアルゴリズムの出力の和は常に微分プライベートである。
論文 参考訳（メタデータ） (2023-07-14T16:11:22Z) - Near-Optimal Quantum Coreset Construction Algorithms for Clustering [15.513270929560088]
我々は、$tildeO(sqrtnkd3/2)$クエリ複雑性を持つ$mathbbRd$で$k$-clusteringのコアセットを見つける量子アルゴリズムを与える。
私たちのコアセットは入力サイズを$n$から$mathrmpoly(kepsilon-1d)$に減らします。
論文 参考訳（メタデータ） (2023-06-05T12:22:46Z) - A polynomial-time iterative algorithm for random graph matching with
non-vanishing correlation [12.869436542291144]
本稿では,2つの相関した ErdHos--R'enyi グラフと,エッジが潜時対応によって相関している$n$ とをマッチングする効率的なアルゴリズムを提案する。
我々のアルゴリズムは実行時間を持ち、エッジの相関が無くなる限り、潜時マッチングを回復することに成功した。
論文 参考訳（メタデータ） (2023-06-01T00:58:50Z) - Correlation Clustering Algorithm for Dynamic Complete Signed Graphs: An
Index-based Approach [9.13755431537592]
本稿では,相関クラスタリング問題を$O(mtimesleft(2+ alpha (G) right)+n)$から$O(m+n)$に近似する複雑性を,完全符号グラフに対して$varepsilon$とする。
提案手法は,元のアルゴリズムと同じ出力を与え,そのアルゴリズムをフルダイナミックな設定で実装できるようにする。
論文 参考訳（メタデータ） (2023-01-01T10:57:36Z) - 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) - Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。
両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文 参考訳（メタデータ） (2020-07-07T17:10:00Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。