論文の概要: 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クラスアルゴリズムはグラフが十分にスパースである場合により良い性能を示すことがわかった。
関連論文リスト
- 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) - Nearly-Optimal Hierarchical Clustering for Well-Clustered Graphs [7.616556723260849]
本稿では,Dasguptaのコスト関数に対する2つの効率的な階層クラスタリング(HC)アルゴリズムを提案する。
明確なクラスタ構造を持つ任意の入力グラフ$G$に対して、我々の設計したアルゴリズムは、入力サイズが$G$でほぼ直線的に実行される。
設計したアルゴリズムは、より少ない実行時間で、より優れたHCツリーを生成する。
論文 参考訳(メタデータ) (2023-06-16T16:31:46Z) - 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) - Causal Bandits on General Graphs [1.4502611532302039]
本稿では、因果グラフのみによって指定された因果ベイズネットワーク(CBN)における最良の介入を決定する問題について検討する。
本稿では,原子間干渉や観測不可能な変数を含む半マルコフ因果グラフを入力として用いた,簡単な後悔最小化アルゴリズムを提案する。
この結果から,提案アルゴリズムの単純後悔保証は,因果グラフのより微妙な構造的制約を考慮すれば改善できることがわかった。
論文 参考訳(メタデータ) (2021-07-06T17:29:45Z) - Hybrid quantum-classical algorithms for approximate graph coloring [65.62256987706128]
量子近似最適化アルゴリズム(RQAOA)をMAX-$k$-CUTに適用する方法を示す。
任意のグラフに対するレベル-$1$QAOAとレベル-$1$RQAOAをシミュレートした,効率的な古典的シミュレーションアルゴリズムを構築する。
論文 参考訳(メタデータ) (2020-11-26T18:22:21Z) - Efficient Permutation Discovery in Causal DAGs [9.22466799504763]
有向非巡回グラフのスパース置換を求めるアルゴリズムを提案する。
We show that our method with depth $w$ run in $O(pw+3) $ time。
また,PC アルゴリズムや GES, GSP などの因果構造学習アルゴリズムと比較し,より短い実行時間で同等の性能が得られることを示す。
論文 参考訳(メタデータ) (2020-11-06T21:56:41Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。