Fugu-MT 論文翻訳(概要): A 4-approximation algorithm for min max correlation clustering

論文の概要: A 4-approximation algorithm for min max correlation clustering

arxiv url: http://arxiv.org/abs/2310.09196v3
Date: Wed, 14 Feb 2024 09:23:48 GMT
ステータス: 処理完了
システム内更新日: 2024-02-15 19:19:55.181189
Title: A 4-approximation algorithm for min max correlation clustering
Title（参考訳）: min max相関クラスタリングのための4近似アルゴリズム
Authors: Holger Heidrich, Jannik Irmai, Bjoern Andres
Abstract要約: minmax相関クラスタリング問題に対する下界法を導入し、この手法に基づいて、完全グラフに対する 4-近似アルゴリズムを提案する。これにより、線形プログラムの定式化を用いて、5の最もよく知られた近似を保証することができる。いくつかのベンチマークデータセットにおいて、ソリューションの品質と実行時の技術状況を改善することを示します。
参考スコア（独自算出の注目度）: 4.028503203417233
License: http://creativecommons.org/licenses/by/4.0/
Abstract: We introduce a lower bounding technique for the min max correlation clustering problem and, based on this technique, a combinatorial 4-approximation algorithm for complete graphs. This improves upon the previous best known approximation guarantees of 5, using a linear program formulation (Kalhan et al., 2019), and 40, for a combinatorial algorithm (Davies et al., 2023a). We extend this algorithm by a greedy joining heuristic and show empirically that it improves the state of the art in solution quality and runtime on several benchmark datasets.
Abstract（参考訳）: 本稿では,min max相関クラスタリング問題に対する下限法を提案し,この手法に基づき,完全グラフのための組合せ4近似アルゴリズムを提案する。これは、組合せアルゴリズム(davies et al., 2023a)のための線形プログラム定式化(kalhan et al., 2019)と40を用いて、以前の最もよく知られた5の近似保証を改善する。我々はこのアルゴリズムをヒューリスティックな結合によって拡張し、いくつかのベンチマークデータセット上でのソリューション品質と実行時の技術状況を改善することを実証的に示す。

関連論文リスト

Accelerating k-Means Clustering with Cover Trees [0.30693357740321775]
表木指数に基づく新しいk-meansアルゴリズムを提案し, オーバーヘッドが比較的低く, 性能も良好である。木集約と境界に基づくフィルタリングの利点を組み合わせたハイブリッドアルゴリズムを得る。
論文参考訳（メタデータ） (2024-10-19T14:02:42Z)
Individualized Privacy Accounting via Subsampling with Applications in Combinatorial Optimization [55.81991984375959]
本研究では、以下の簡単な観察を通して、個別化されたプライバシ会計を解析する新しい手法を提案する。我々は、分解可能な部分モジュラーおよびセットアルゴリズム被覆を含む、プライベート最適化問題に対するいくつかの改良されたアルゴリズムを得る。
論文参考訳（メタデータ） (2024-05-28T19:02:30Z)
Accelerating Cutting-Plane Algorithms via Reinforcement Learning Surrogates [49.84541884653309]
凸離散最適化問題に対する現在の標準的なアプローチは、カットプレーンアルゴリズムを使うことである。多くの汎用カット生成アルゴリズムが存在するにもかかわらず、大規模な離散最適化問題は、難易度に悩まされ続けている。そこで本研究では,強化学習による切削平面アルゴリズムの高速化手法を提案する。
論文参考訳（メタデータ） (2023-07-17T20:11:56Z)
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)
An Exact Algorithm for Semi-supervised Minimum Sum-of-Squares Clustering [0.5801044612920815]
半教師付きMSSCのための分岐結合アルゴリズムを提案する。背景知識はペアワイズ・マスタリンクと結びつかない制約として組み込まれている。提案したグローバル最適化アルゴリズムは,実世界のインスタンスを最大800個のデータポイントまで効率的に解決する。
論文参考訳（メタデータ） (2021-11-30T17:08:53Z)
ParChain: A Framework for Parallel Hierarchical Agglomerative Clustering using Nearest-Neighbor Chain [6.824747267214373]
本稿では並列階層クラスタリング(HAC)アルゴリズムを設計するためのParChainフレームワークを提案する。従来の並列HACアルゴリズムと比較して、我々の新しいアルゴリズムは線形メモリしか必要とせず、大規模データセットにスケーラブルである。我々のアルゴリズムは、既存のアルゴリズムでは処理できない数千万のポイントでデータセットのサイズにスケールすることができる。
論文参考訳（メタデータ） (2021-06-08T23:13:27Z)
Locally Private k-Means in One Round [44.00192304748844]
差分プライバシー(DP)の1ラウンド(別名非相互作用)局所モデルにおけるk平均クラスタリングの近似アルゴリズムを提供する。このアルゴリズムは、最適な非プライベート近似アルゴリズムに近い近似比を任意に達成する。
論文参考訳（メタデータ） (2021-04-20T03:07:31Z)
Approximation Algorithms for Sparse Best Rank-1 Approximation to Higher-Order Tensors [1.827510863075184]
スパーステンソル最高ランク1近似(英: Sparse tensor best rank-1 approximation, BR1Approx)は、密度テンソルBR1Approxの空間一般化である。低計算量で容易に実装できる4つの近似アルゴリズムが提案されている。提案手法の有効性を示すために,合成および実データに関する数値実験を行った。
論文参考訳（メタデータ） (2020-12-05T18:13:14Z)
An Asymptotically Optimal Primal-Dual Incremental Algorithm for Contextual Linear Bandits [129.1029690825929]
複数の次元に沿った最先端技術を改善する新しいアルゴリズムを提案する。非文脈線形帯域の特別な場合において、学習地平線に対して最小限の最適性を確立する。
論文参考訳（メタデータ） (2020-10-23T09:12:47Z)
Differentially Private Clustering: Tight Approximation Ratios [57.89473217052714]
基本的なクラスタリング問題に対して,効率的な微分プライベートアルゴリズムを提案する。この結果から,SampleとAggregateのプライバシーフレームワークのアルゴリズムの改善が示唆された。 1-Clusterアルゴリズムで使用されるツールの1つは、ClosestPairのより高速な量子アルゴリズムを適度な次元で得るために利用できる。
論文参考訳（メタデータ） (2020-08-18T16:22:06Z)
Fair Correlation Clustering [92.15492066925977]
相関クラスタリングの近似アルゴリズムは,いくつかの重要なフェアネス制約の下で得られる。相関クラスタリングに対する公平な解は、最先端の(不公平な)アルゴリズムと比較して、コストを抑えながら得られることを示す。
論文参考訳（メタデータ） (2020-02-06T14:28:21Z)

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