Fugu-MT 論文翻訳(概要): From Maximum Cut to Maximum Independent Set

論文の概要: From Maximum Cut to Maximum Independent Set

arxiv url: http://arxiv.org/abs/2408.06758v2
Date: Wed, 18 Sep 2024 08:59:57 GMT
ステータス: 処理完了
システム内更新日: 2024-09-19 22:32:32.554012
Title: From Maximum Cut to Maximum Independent Set
Title（参考訳）: 最大カットから最大独立セットへ
Authors: Chuixiong Wu, Jianan Wang, Fen Zuo,
Abstract要約: 最大独立集合(MIS)問題も特定のイジングモデルと関係があることは以前から知られていた。この戦略により、ランダムなエルドホス・ローニイグラフの独立数に対する近似が大幅に改善されることが判明した。また、コーディング理論から生じるベンチマークで完全なパフォーマンスを示す。
参考スコア（独自算出の注目度）: 7.250073177017239
License: http://creativecommons.org/licenses/by-sa/4.0/
Abstract: The Maximum Cut (Max-Cut) problem could be naturally expressed either in a Quadratic Unconstrained Binary Optimization (QUBO) formulation, or as an Ising model. It has long been known that the Maximum Independent Set (MIS) problem could also be related to a specific Ising model. Therefore, it would be natural to attack MIS with various Max-Cut/Ising solvers. It turns out that this strategy greatly improves the approximation for the independence number of random Erd\H{o}s-R\'{e}nyi graphs. It also exhibits perfect performance on a benchmark arising from coding theory. These results pave the way for further development of approximate quantum algorithms on MIS, and specifically on the corresponding coding problems.
Abstract（参考訳）: 最大カット(Max-Cut)問題は、二次非拘束バイナリ最適化(QUBO)の定式化やイジングモデル(Ising model)として自然に表現できる。最大独立集合(MIS)問題も特定のイジングモデルと関係があることは以前から知られていた。したがって、様々なMax-Cut/IsingソルバでMISを攻撃するのは自然なことである。この戦略は、ランダムな Erd\H{o}s-R\'{e}nyi グラフの独立性の近似を大幅に改善する。また、コーディング理論から生じるベンチマークで完全なパフォーマンスを示す。これらの結果は、MIS上の近似量子アルゴリズム、特に対応する符号化問題において、さらなる発展の道を開くものである。

関連論文リスト

On lower bounds of the density of planar periodic sets without unit distances [55.2480439325792]
平面トーラスから構築したグラフ上での最大独立集合(MIS)問題として問題を再構成することにより、$m_1(mathbbR2)$を推定する新しいアプローチを導入する。提案手法の理論的正当性によって支持された実験結果は,十分に広い範囲のパラメータに対して,この手法が既知の下界を改善できないことを示す。
論文参考訳（メタデータ） (2024-11-20T12:07:19Z)
MG-Net: Learn to Customize QAOA with Circuit Depth Awareness [51.78425545377329]
量子近似最適化アルゴリズム(QAOA)とその変種は、最適化問題に対処する大きな可能性を示している。良好な性能を実現するために必要な回路深度は問題固有であり、しばしば現在の量子デバイスの最大容量を超える。ミキサジェネレータネットワーク (MG-Net) は, 最適ミキサハミルトニアンを動的に定式化するための統合ディープラーニングフレームワークである。
論文参考訳（メタデータ） (2024-09-27T12:28:18Z)
Dataless Quadratic Neural Networks for the Maximum Independent Set Problem [23.643727259409744]
pCQO-MISはエッジ数ではなくグラフ内のノード数でスケールすることを示す。提案手法は,分散の排除,サンプリング,データ中心のアプローチを回避する。
論文参考訳（メタデータ） (2024-06-27T21:12:48Z)
Missing Puzzle Pieces in the Performance Landscape of the Quantum Approximate Optimization Algorithm [0.0]
ランダム正則グラフ上での最大カットと最大独立集合問題を考える。高い正則性に対してQAOAが達成したエネルギー密度を$d=100$まで計算する。両問題に対する最適性について,QAOA分析と最先端の上界を結合する。
論文参考訳（メタデータ） (2024-06-20T18:00:02Z)
An Analysis of Quantum Annealing Algorithms for Solving the Maximum Clique Problem [49.1574468325115]
我々は、QUBO問題として表されるグラフ上の最大傾きを見つける量子D波アンナーの能力を解析する。本稿では, 相補的な最大独立集合問題に対する分解アルゴリズムと, ノード数, 傾き数, 密度, 接続率, 解サイズの他のノード数に対する比を制御するグラフ生成アルゴリズムを提案する。
論文参考訳（メタデータ） (2024-06-11T04:40:05Z)
Best Arm Identification with Fixed Budget: A Large Deviation Perspective [54.305323903582845]
我々は、様々な武器の報酬間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。特に、様々な武器の報酬の間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。
論文参考訳（メタデータ） (2023-12-19T13:17:43Z)
Multi-block Min-max Bilevel Optimization with Applications in Multi-task Deep AUC Maximization [36.743632418094]
マルチブロックのmin-max双レベル最適化問題に対処するシングルループアルゴリズムを提案する。我々のアルゴリズムは数百のタスクで問題に取り組むのに利用できることを示す。
論文参考訳（メタデータ） (2022-06-01T06:42:36Z)
QAOA-in-QAOA: solving large-scale MaxCut problems on small quantum machines [81.4597482536073]
量子近似最適化アルゴリズム(QAOAs)は、量子マシンのパワーを利用し、断熱進化の精神を継承する。量子マシンを用いて任意の大規模MaxCut問題を解くためにQAOA-in-QAOA(textQAOA2$)を提案する。提案手法は,大規模最適化問題におけるQAOAsの能力を高めるために,他の高度な戦略にシームレスに組み込むことができる。
論文参考訳（メタデータ） (2022-05-24T03:49:10Z)
Predicting parameters for the Quantum Approximate Optimization Algorithm for MAX-CUT from the infinite-size limit [0.05076419064097732]
推定次数$d$のランダムエルドス・レーニグラフに適用したMAX-CUT上でのQAOAの性能を評価するための明示的なアルゴリズムを提案する。この解析により、エルドス・レーニグラフ上のMAX-CUTのQAOAパラメータとシェリントン・カークパトリックモデルとの明示的なマッピングが得られる。
論文参考訳（メタデータ） (2021-10-20T17:58:53Z)
Clustering a Mixture of Gaussians with Unknown Covariance [4.821312633849745]
最大極大推定に基づくMax-Cut整数プログラムを導出する。最適な速度を得るが、2次サンプルサイズを必要とする効率的なスペクトルアルゴリズムを開発する。我々は Max-Cut プログラムを$k$-means プログラムに一般化する。
論文参考訳（メタデータ） (2021-10-04T17:59:20Z)
Modeling the Second Player in Distributionally Robust Optimization [90.25995710696425]
我々は、最悪のケース分布を特徴付けるために神経生成モデルを使うことを議論する。このアプローチは多くの実装と最適化の課題をもたらします。提案されたアプローチは、同等のベースラインよりも堅牢なモデルを生み出す。
論文参考訳（メタデータ） (2021-03-18T14:26:26Z)

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