論文の概要: Optimal Multimarginal Schrödinger Bridge: Minimum Spanning Tree over Measure-valued Vertices

• arxiv url: http://arxiv.org/abs/2509.10626v1
• Date: Fri, 12 Sep 2025 18:15:42 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-09-16 17:26:22.697741
• Title: Optimal Multimarginal Schrödinger Bridge: Minimum Spanning Tree over Measure-valued Vertices
• Title（参考訳）: 最適マルチマルジナルシュレーディンガー橋:測定値の頂点上の最小スパンニング木
• Authors: Georgiy A. Bondar, Abhishek Halder,
• Abstract要約: Multimarginal Schr"odinger Bridge (MSB) は、既知の統計と既知の相関構造を持つランダムベクトルの集合の最適結合を見つける。 最適MSBの計算は、測定値の頂点上での最小分散木問題の解に相当することがわかった。
• 参考スコア（独自算出の注目度）: 0.15469452301122175
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The Multimarginal Schr\"odinger Bridge (MSB) finds the optimal coupling among a collection of random vectors with known statistics and a known correlation structure. In the MSB formulation, this correlation structure is specified \emph{a priori} as an undirected connected graph with measure-valued vertices. In this work, we formulate and solve the problem of finding the optimal MSB in the sense we seek the optimal coupling over all possible graph structures. We find that computing the optimal MSB amounts to solving the minimum spanning tree problem over measure-valued vertices. We show that the resulting problem can be solved in two steps. The first step constructs a complete graph with edge weight equal to a sum of the optimal value of the corresponding bimarginal SB and the entropies of the endpoints. The second step solves a standard minimum spanning tree problem over that complete weighted graph. Numerical experiments illustrate the proposed solution.
• Abstract（参考訳）: Multimarginal Schr\"odinger Bridge (MSB) は、既知の統計と既知の相関構造を持つランダムベクトルの集合の最適結合を見つける。 MSB の定式化では、この相関構造は測度値の頂点を持つ無向連結グラフとして指定される。 本研究では,全ての可能なグラフ構造に対する最適結合を求めるという意味で,最適MSBを求める問題を定式化し,解決する。 最適MSBの計算は、測定値の頂点上での最小分散木問題の解に相当することがわかった。 得られた問題を2つのステップで解決できることが示される。 最初のステップは、エッジウェイトが対応する二辺 SB の最適値とエンドポイントのエントロピーの和に等しい完全グラフを構成する。 2番目のステップは、その全重み付きグラフ上での標準最小木幅問題の解決である。 数値実験は提案された解を例証する。

関連論文リスト

• Optimizing Cost Hamiltonian Compilation for Max-Cut QAOA on Unweighted Graphs Using Global Controls and Qubit Bit Flips [0.0]
  量子近似最適化アルゴリズム(QAOA)のコストハミルトンコンパイル問題をMax-Cut問題に適用する。 CNOTとRzゲートの標準コンパイルの代わりに、グローバル結合演算と単一ビットビットフリップを採用する。
  論文  参考訳（メタデータ） (2025-08-29T18:12:20Z)
• Bounds on Perfect Node Classification: A Convex Graph Clustering Perspective [50.3088702686312]
  本稿では,ノードラベルやノードの特徴に合致するコミュニティを基盤とした,トランスダクティブノード分類問題の解析を行う。 ノード分類において,スペクトルグラフクラスタリングフレームワークにノード固有情報を組み込んだ新しい最適化問題を提案する。
  論文  参考訳（メタデータ） (2025-08-27T19:22:35Z)
• Improved Approximations for Hard Graph Problems using Predictions [13.827632579682795]
  我々は予測を組み込んだNPハードグラフ問題に対する近似アルゴリズムを改良した。 我々の予測モデルは、Cohen-Addad, d'Orsi, Gupta, Lee, Panigrahiによる$varepsilon$-predictionフレームワークの上に構築され、拡張されます。
  論文  参考訳（メタデータ） (2025-05-29T19:47:09Z)
• On lower bounds of the density of planar periodic sets without unit distances [55.2480439325792]
  平面トーラスから構築したグラフ上での最大独立集合(MIS)問題として問題を再構成することにより、$m_1(mathbbR2)$を推定する新しいアプローチを導入する。 提案手法の理論的正当性によって支持された実験結果から, 十分に広い範囲のパラメータに対して, この手法が既知の下界を改善できないことを示す。
  論文  参考訳（メタデータ） (2024-11-20T12:07:19Z)
• An Analysis of Quantum Annealing Algorithms for Solving the Maximum Clique Problem [49.1574468325115]
  我々は、QUBO問題として表されるグラフ上の最大傾きを見つける量子D波アンナーの能力を解析する。 本稿では, 相補的な最大独立集合問題に対する分解アルゴリズムと, ノード数, 傾き数, 密度, 接続率, 解サイズの他のノード数に対する比を制御するグラフ生成アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-06-11T04:40:05Z)
• A Thorough View of Exact Inference in Graphs from the Degree-4 Sum-of-Squares Hierarchy [37.34153902687548]
  各エッジの1つの破損した観測からノードの未知の接地型バイナリラベリングを正確に回収する問題に取り組む。 この問題に対して、和の平方階層と呼ばれるリラクゼーションの階層を適用します。 我々は、緩和問題の双対の解がジョンソングラフとクネーサーグラフのエッジウェイトを見つけることに関連していることを示した。
  論文  参考訳（メタデータ） (2021-02-16T08:36:19Z)
• Online Dense Subgraph Discovery via Blurred-Graph Feedback [87.9850024070244]
  我々は高密度サブグラフ発見のための新しい学習問題を導入する。 まず,確率の高いほぼ最適解を求めるエッジ時間アルゴリズムを提案する。 そして、理論的保証のあるよりスケーラブルなアルゴリズムを設計する。
  論文  参考訳（メタデータ） (2020-06-24T11:37:33Z)
• The Quantum Approximate Optimization Algorithm Needs to See the Whole Graph: Worst Case Examples [6.810856082577402]
  量子近似最適化アルゴリズムは、エッジに対応する項の和であるコスト関数を持つグラフ上の探索問題に適用することができる。 我々は、$(d-1)2p nA$ の QAOA が任意の$A1$ に対して、d 大のランダムな d-正規グラフ上の Max-Cut に対して 1/2 の近似比しか達成できないことを示す。
  論文  参考訳（メタデータ） (2020-05-18T14:23:09Z)
• Wasserstein-based Graph Alignment [56.84964475441094]
  我々は,より小さいグラフのノードと大きなグラフのノードをマッチングすることを目的とした,1対多のグラフアライメント問題に対する新しい定式化を行った。 提案手法は,各タスクに対する最先端のアルゴリズムに対して,大幅な改善をもたらすことを示す。
  論文  参考訳（メタデータ） (2020-03-12T22:31:59Z)

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

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