論文の概要: Breaking 3-Factor Approximation for Correlation Clustering in
Polylogarithmic Rounds
- arxiv url: http://arxiv.org/abs/2307.06723v1
- Date: Thu, 13 Jul 2023 12:32:49 GMT
- ステータス: 処理完了
- システム内更新日: 2023-07-14 14:38:12.914428
- Title: Breaking 3-Factor Approximation for Correlation Clustering in
Polylogarithmic Rounds
- Title（参考訳）: 多対数ラウンドにおける相関クラスタリングのための分割3因子近似
- Authors: Nairen Cao, Shang-En Huang, Hsin-Hao Su
- Abstract要約: 相関クラスタリング問題に対する並列アルゴリズムについて検討する。
目標は、エンティティをクラスタに分割し、ラベルとの相違を最小限にすることである。
現在、全ての効率的な並列アルゴリズムは、近似比が少なくとも3である。
3 より優れた近似比を実現するための最初の多元対数アルゴリズムを提案する。
- 参考スコア（独自算出の注目度）: 0.23633885460047763
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: In this paper, we study parallel algorithms for the correlation clustering
problem, where every pair of two different entities is labeled with similar or
dissimilar. The goal is to partition the entities into clusters to minimize the
number of disagreements with the labels. Currently, all efficient parallel
algorithms have an approximation ratio of at least 3. In comparison with the
$1.994+\epsilon$ ratio achieved by polynomial-time sequential algorithms
[CLN22], a significant gap exists.
We propose the first poly-logarithmic depth parallel algorithm that achieves
a better approximation ratio than 3. Specifically, our algorithm computes a
$(2.4+\epsilon)$-approximate solution and uses $\tilde{O}(m^{1.5})$ work.
Additionally, it can be translated into a $\tilde{O}(m^{1.5})$-time sequential
algorithm and a poly-logarithmic rounds sublinear-memory MPC algorithm with
$\tilde{O}(m^{1.5})$ total memory.
Our approach is inspired by Awerbuch, Khandekar, and Rao's [AKR12]
length-constrained multi-commodity flow algorithm, where we develop an
efficient parallel algorithm to solve a truncated correlation clustering linear
program of Charikar, Guruswami, and Wirth [CGW05]. Then we show the solution of
the truncated linear program can be rounded with a factor of at most 2.4 loss
by using the framework of [CMSY15]. Such a rounding framework can then be
implemented using parallel pivot-based approaches.
- Abstract（参考訳）: 本稿では,相関クラスタリング問題に対する並列アルゴリズムについて検討する。
目標は、エンティティをクラスタに分割し、ラベルとの相違の数を最小化することです。
現在、全ての効率的な並列アルゴリズムは近似比が少なくとも3である。
多項式時間逐次アルゴリズム[CLN22]によって達成された1.994+\epsilon$比と比較して、大きなギャップが存在する。
3 より優れた近似比を実現するための最初の多対数深度並列アルゴリズムを提案する。
具体的には、このアルゴリズムは$(2.4+\epsilon)$-approximate Solutionを計算し、$\tilde{O}(m^{1.5})$ workを使用する。
さらに、$\tilde{O}(m^{1.5})$タイムシーケンシャルアルゴリズムと$\tilde{O}(m^{1.5})$トータルメモリを持つ多対数ラウンドスサブリニアメモリMPCアルゴリズムに変換することができる。
この手法はawerbuch, khandekar, raoの [akr12] long-constrained multi-commodity flow algorithm に触発され,charikar, guruswami, wirth [cgw05] の断続相関クラスタリング線形プログラムを解く効率的な並列アルゴリズムを開発した。
次に,[CMSY15] の枠組みを用いて, トラッピングされた線形プログラムの解を少なくとも2.4の損失率で丸めることができることを示す。
このようなラウンドフレームワークは、並列ピボットベースのアプローチで実装できる。
関連論文リスト
- 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) - Approximation Algorithms for Preference Aggregation Using CP-Nets [3.337244446073836]
本稿では,条件付き選好ネットワーク(CP-nets)上での選好を集約する近似アルゴリズムの設計と解析について述べる。
その焦点は、一般に最適な解が指数関数的な大きさであることが知られている、いわゆる「エンフスワップ」よりも、優先的な選好を集約することである。
論文 参考訳（メタデータ） (2023-12-14T17:31:38Z) - 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) - 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) - 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) - ParChain: A Framework for Parallel Hierarchical Agglomerative Clustering
using Nearest-Neighbor Chain [6.824747267214373]
本稿では並列階層クラスタリング(HAC)アルゴリズムを設計するためのParChainフレームワークを提案する。
従来の並列HACアルゴリズムと比較して、我々の新しいアルゴリズムは線形メモリしか必要とせず、大規模データセットにスケーラブルである。
我々のアルゴリズムは、既存のアルゴリズムでは処理できない数千万のポイントでデータセットのサイズにスケールすることができる。
論文 参考訳（メタデータ） (2021-06-08T23:13:27Z) - Fast Parallel Algorithms for Euclidean Minimum Spanning Tree and
Hierarchical Spatial Clustering [6.4805900740861]
HDBSCAN$*$のための私達のアルゴリズムの仕事そしてスペースを減らすために十分分離の新しい概念を導入します。
我々のアルゴリズムは理論的に効率的であることを示す: 彼らは逐次対応の作業(操作数)と多対数深さ(並列時間)を持っている。
48コアマシンを用いた大規模実世界および合成データセットの実験により、我々の最速のアルゴリズムは11.13-55.89x、既存の並列アルゴリズムを少なくとも桁違いに上回った。
論文 参考訳（メタデータ） (2021-04-02T16:05:00Z) - Practical and Parallelizable Algorithms for Non-Monotone Submodular
Maximization with Size Constraint [20.104148319012854]
サイズ制約に関して、必ずしも単調ではない部分モジュラ函数に対して存在および並列化可能である。
最適な適応性とほぼ最適な複雑性クエリを持つアルゴリズムによって達成される最適な近似係数を、0.193 - varepsilon$に改善する。
論文 参考訳（メタデータ） (2020-09-03T22:43:55Z) - Revisiting Modified Greedy Algorithm for Monotone Submodular
Maximization with a Knapsack Constraint [75.85952446237599]
修正されたグリードアルゴリズムは、近似係数が0.305$であることを示す。
最適なデータ依存上界を導出する。
また、分岐やバウンドといったアルゴリズムの効率を大幅に改善するためにも使うことができる。
論文 参考訳（メタデータ） (2020-08-12T15:40:21Z) - Second-order Conditional Gradient Sliding [79.66739383117232]
本稿では,emphSecond-Order Conditional Gradient Sliding (SOCGS)アルゴリズムを提案する。
SOCGSアルゴリズムは、有限個の線形収束反復の後、原始ギャップに二次的に収束する。
実現可能な領域が線形最適化オラクルを通してのみ効率的にアクセスできる場合に有用である。
論文 参考訳（メタデータ） (2020-02-20T17:52:18Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。