論文の概要: More on greedy construction heuristics for the MAX-CUT problem

• arxiv url: http://arxiv.org/abs/2312.10895v1
• Date: Mon, 18 Dec 2023 02:52:04 GMT
• ステータス: 処理完了
• システム内更新日: 2023-12-20 21:40:40.198405
• Title: More on greedy construction heuristics for the MAX-CUT problem
• Title（参考訳）: MAX-CUT問題に対する欲求的建設ヒューリスティックスの詳細
• Authors: Jianan Wang, Chuixiong Wu, Fen Zuo
• Abstract要約: この図は, 最大カット問題に対して, 主なグリーディを分類するのに有効であることを示す。 SG(Sahni-Gonzalez)アルゴリズムの全てのバージョンはプリム類に分類される。 様々なエッジ・コントラクション(EC)アルゴリズムはKruskalクラスに属する。
• 参考スコア（独自算出の注目度）: 8.148355685823521
• License: http://creativecommons.org/licenses/by-sa/4.0/
• Abstract: A cut of a graph can be represented in many different ways. Here we propose to represent a cut through a ``relation tree'', which is a spanning tree with signed edges. We show that this picture helps to classify the main greedy heuristics for the maximum cut problem, in analogy with the minimum spanning tree problem. Namely, all versions of the Sahni-Gonzalez~(SG) algorithms could be classified as the Prim class, while various Edge-Contraction~(EC) algorithms are of the Kruskal class. We further elucidate the relation of this framework to the stabilizer formalism in quantum computing, and point out that the recently proposed \textit{ADAPT-Clifford} algorithm is a reformulation of a refined version of the SG algorithm, SG3. Numerical performance of the typical algorithms from the two classes are studied with various kinds of graphs. It turns out that, the Prim-class algorithms perform better for general dense graphs, and the Kruskal-class algorithms performs better when the graphs are sparse enough.
• Abstract（参考訳）: グラフの切断は多くの異なる方法で表現できる。 ここでは、符号付きエッジを持つスパンディングツリーである ``relation tree'' を通して切断を表現することを提案する。 この図は, 最大カット問題に対して, 最小スパンディングツリー問題に類似して, 主欲のヒューリスティックを分類するのに役立つことを示す。 すなわち、Sahni-Gonzalez~(SG)アルゴリズムのすべてのバージョンはPrimクラスに分類されるが、Edge-Contraction~(EC)アルゴリズムはKruskalクラスである。 我々は、このフレームワークと量子コンピューティングにおける安定化形式との関係をさらに解明し、最近提案された \textit{ADAPT-Clifford} アルゴリズムは SG アルゴリズムの洗練されたバージョンである SG3 の再構成であると指摘した。 2つのクラスからの典型的なアルゴリズムの数値的性能を各種グラフを用いて検討した。 その結果、Primクラスアルゴリズムは一般の高密度グラフに対してより良い性能を示し、Kruskalクラスアルゴリズムはグラフが十分にスパースである場合により良い性能を示すことがわかった。

関連論文リスト

• Optimal spanning tree reconstruction in symbolic regression [2.553456266022125]
  モデルは原始関数の重ね合わせである。 提案アルゴリズムは, 加重色グラフからスパンニング木を再構成する。 本稿では,Steiner 木木アルゴリズムを応用した新しい手法を提案する。
  論文  参考訳（メタデータ） (2024-06-25T13:22:13Z)
• Combinatorial Approximations for Cluster Deletion: Simpler, Faster, and Better [18.121514220195607]
  クラスタ削除は、計算およびソーシャルネットワーク分析におけるNPハードグラフクラスタリングの目的である。 まず,2つの近似アルゴリズムの厳密な解析を行い,その近似保証を4から3に改善する。 補助グラフにおいて最大等級を優しく取り、その周囲にクラスタを形成することにより、両アルゴリズムを驚くほど単純な方法でデランドマイズすることができることを示す。
  論文  参考訳（メタデータ） (2024-04-24T18:39:18Z)
• A Differentially Private Clustering Algorithm for Well-Clustered Graphs [6.523602840064548]
  このようなグラフに特化された効率的な(epsilon,$delta$)-DPアルゴリズムを提供する。 我々のアルゴリズムは、ほぼバランスの取れたクラスタに対して$k$のグラフを扱う。
  論文  参考訳（メタデータ） (2024-03-21T11:57:16Z)
• Efficient Algorithms for Recognizing Weighted Tree-Adjoining Languages [104.90415092306219]
  4つの形式は、ツリー随伴文法(TAG)、線形指数文法(LIG)、プッシュダウン随伴オートマトン(PAA)、組込みプッシュダウンオートマトン(EPDA)に相当する。 我々は,文字列の導出量(文字列のすべてのオートマトン重み)と全導出量(全ての導出量重み)を計算するための新しいアルゴリズムを設計する。 EPDA の場合、我々のアルゴリズムは、$mathcalO(|Gamma|2)$ および $ の因子による Alonso et al. (2001) のアルゴリズムよりも空間効率と時間効率が良い。
  論文  参考訳（メタデータ） (2023-10-23T18:26:00Z)
• 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)
• Causal Bandits without Graph Learning [28.021500949026766]
  我々は,原子間干渉を用いた報酬ノードの親ノード探索のための効率的なアルゴリズムを開発した。 報奨ノードが複数の親を持つ場合にアルゴリズムを拡張します。
  論文  参考訳（メタデータ） (2023-01-26T20:27:14Z)
• Quantitative approach to Grover's quantum walk on graphs [62.997667081978825]
  グラフ上の連続時間量子ウォークに着目したGroverの探索アルゴリズムについて検討する。 関連する量子ウォークに便利なグラフトポロジーを見つける代わりに、グラフトポロジーを修正し、ラプラシアンを基礎とするグラフを変化させる。
  論文  参考訳（メタデータ） (2022-07-04T19:33:06Z)
• Extensions of Karger's Algorithm: Why They Fail in Theory and How They Are Useful in Practice [17.801124377461953]
  カーガーのアルゴリズムが他のカット問題に対してうまく一般化できるかどうかを考察する。 本稿では,シードセグメンテーション/グラフベース半教師付き学習のための簡単なアルゴリズムを提案する。 新しいアルゴリズムは線形実行時を持ち、与えられた種/クラスに属するサンプルの後方確率と解釈できるポテンシャルを与える。
  論文  参考訳（メタデータ） (2021-10-05T07:46:28Z)
• Hybrid quantum-classical algorithms for approximate graph coloring [65.62256987706128]
  量子近似最適化アルゴリズム(RQAOA)をMAX-$k$-CUTに適用する方法を示す。 任意のグラフに対するレベル-$1$QAOAとレベル-$1$RQAOAをシミュレートした,効率的な古典的シミュレーションアルゴリズムを構築する。
  論文  参考訳（メタデータ） (2020-11-26T18:22:21Z)
• Efficient Computation of Expectations under Spanning Tree Distributions [67.71280539312536]
  本稿では,エッジファクター,非プロジェクティブ・スパンニングツリーモデルにおいて,一階期待と二階期待の重要なケースに対する統一アルゴリズムを提案する。 我々のアルゴリズムは勾配と期待の基本的な関係を利用しており、効率的なアルゴリズムを導出することができる。
  論文  参考訳（メタデータ） (2020-08-29T14:58:26Z)
• Online Dense Subgraph Discovery via Blurred-Graph Feedback [87.9850024070244]
  我々は高密度サブグラフ発見のための新しい学習問題を導入する。 まず,確率の高いほぼ最適解を求めるエッジ時間アルゴリズムを提案する。 そして、理論的保証のあるよりスケーラブルなアルゴリズムを設計する。
  論文  参考訳（メタデータ） (2020-06-24T11:37:33Z)

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

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