論文の概要: Gromov-Wasserstein and optimal transport: from assignment problems to probabilistic numeric

• arxiv url: http://arxiv.org/abs/2509.04089v1
• Date: Thu, 04 Sep 2025 10:44:30 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-09-05 20:21:10.133438
• Title: Gromov-Wasserstein and optimal transport: from assignment problems to probabilistic numeric
• Title（参考訳）: Gromov-Wassersteinと最適輸送:代入問題から確率的数値へ
• Authors: Iman Seyedi, Antonio Candelieri, Enza Messina, Francesco Archetti,
• Abstract要約: この研究は、古典的な定式化やアルゴリズムから現代の最適輸送理論への進化を辿る。 提案するマルチ初期化戦略(GW-MultiInit)を含む、正確な解法、遺伝的アルゴリズム(GA)および複数のGW変種を提示する。 本研究は, OT法およびGW法をQAPや他の実世界のマッチング問題に適用するための理論的基礎, 計算的洞察, 実践的ガイドラインを提供する。
• 参考スコア（独自算出の注目度）: 2.4216621644867495
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The assignment problem, a cornerstone of operations research, seeks an optimal one-to-one mapping between agents and tasks to minimize total cost. This work traces its evolution from classical formulations and algorithms to modern optimal transport (OT) theory, positioning the Quadratic Assignment Problem (QAP) and related structural matching tasks within this framework. We connect the linear assignment problem to Monge's transport problem, Kantorovich's relaxation, and Wasserstein distances, then extend to cases where source and target lie in different metric-measure spaces requiring Gromov-Wasserstein (GW) distances. GW formulations, including the fused GW variant that integrates structural and feature information, naturally address QAP-like problems by optimizing alignment based on both intra-domain distances and cross-domain attributes. Applications include graph matching, keypoint correspondence, and feature-based assignments. We present exact solvers, Genetic Algorithms (GA), and multiple GW variants, including a proposed multi-initialization strategy (GW-MultiInit) that mitigates the risk of getting stuck in local optima alongside entropic Sinkhorn-based approximations and fused GW. Computational experiments on capacitated QAP instances show that GW-MultiInit consistently achieves near-optimal solutions and scales efficiently to large problems where exact methods become impractical, while parameterized EGW and FGW variants provide flexible trade-offs between accuracy and runtime. Our findings provide theoretical foundations, computational insights, and practical guidelines for applying OT and GW methods to QAP and other real-world matching problems, such as those in machine learning and logistics.
• Abstract（参考訳）: 運用研究の要点である代入問題は、総コストを最小限に抑えるために、エージェントとタスク間の最適な1対1マッピングを求める。 この研究は、古典的な定式化やアルゴリズムから現代の最適輸送(OT)理論へと発展し、二次割り当て問題(QAP)と関連する構造的マッチングタスクをこのフレームワーク内に配置した。 線形代入問題をモンゲの輸送問題、カントロビッチの緩和、ワッサーシュタイン距離と結びつけ、Gromov-Wasserstein (GW) 距離を必要とする異なる測度空間にソースとターゲットが配置されている場合に拡張する。 構造情報と特徴情報を統合する融合GW変種を含むGWの定式化は、ドメイン内距離とクロスドメイン属性の両方に基づいてアライメントを最適化することでQAPライクな問題に自然に対処する。 アプリケーションには、グラフマッチング、キーポイント対応、機能ベースの割り当てが含まれる。 提案するマルチ初期化戦略 (GW-MultiInit) は, エントロピックなシンクホーン近似と融合したGWと並行して, 局所最適に立ち往生するリスクを緩和する。 容量化QAPインスタンス上での計算実験により、GW-MultiInitは、ほぼ最適解を一貫して達成し、正確なメソッドが実用的でないような大きな問題に効率よくスケールし、パラメータ化されたEGWとFGWは、精度と実行時の間の柔軟なトレードオフを提供する。 本研究は, OT法とGW法をQAPや機械学習やロジスティクスなどの実世界のマッチング問題に適用するための理論的基礎, 計算的洞察, 実践的ガイドラインを提供する。

関連論文リスト

• Weighted strategies to guide a multi-objective evolutionary algorithm for multi-UAV mission planning [12.97430155510359]
  この研究は、新しい個体の生成と突然変異のための重み付きランダム・ジェネレータを提案する。 この研究の主な目的は、マルチUAVミッション計画のためのMOEAソルバの収束率を下げることである。
  論文  参考訳（メタデータ） (2024-02-28T23:05:27Z)
• The Complexity of Optimizing Atomic Congestion [14.845310803203724]
  アトミック・渋滞ゲームは、ネットワーク設計、ルーティング、アルゴリズムゲーム理論において古典的なトピックである。 非常に単純なネットワークでも問題は非常に難解なままである。 我々は、この問題の(さらに難しい)min-max変種に対する分析を拡張して結論付ける。
  論文  参考訳（メタデータ） (2023-12-15T21:31:30Z)
• Optimizing Solution-Samplers for Combinatorial Problems: The Landscape of Policy-Gradient Methods [52.0617030129699]
  本稿では,DeepMatching NetworksとReinforcement Learningメソッドの有効性を解析するための新しい理論フレームワークを提案する。 我々の主な貢献は、Max- and Min-Cut、Max-$k$-Bipartite-Bi、Maximum-Weight-Bipartite-Bi、Traveing Salesman Problemを含む幅広い問題である。 本分析の副産物として,バニラ降下による新たな正則化プロセスを導入し,失効する段階的な問題に対処し,悪い静止点から逃れる上で有効であることを示す理論的および実験的証拠を提供する。
  論文  参考訳（メタデータ） (2023-10-08T23:39:38Z)
• Let the Flows Tell: Solving Graph Combinatorial Optimization Problems with GFlowNets [86.43523688236077]
  組合せ最適化(CO)問題はしばしばNPハードであり、正確なアルゴリズムには及ばない。 GFlowNetsは、複合非正規化密度を逐次サンプリングする強力な機械として登場した。 本稿では,異なる問題に対してマルコフ決定プロセス(MDP)を設計し,条件付きGFlowNetを学習して解空間からサンプルを作成することを提案する。
  論文  参考訳（メタデータ） (2023-05-26T15:13:09Z)
• Multi-Objective Policy Gradients with Topological Constraints [108.10241442630289]
  本稿では, PPOアルゴリズムの簡単な拡張により, TMDPにおけるポリシー勾配に対する新しいアルゴリズムを提案する。 シミュレーションと実ロボットの両方の目的を任意に並べた実世界の多目的ナビゲーション問題に対して,これを実証する。
  論文  参考訳（メタデータ） (2022-09-15T07:22:58Z)
• Multi-Task Learning on Networks [0.0]
  マルチタスク学習コンテキストで発生する多目的最適化問題は、特定の特徴を持ち、アドホックな方法を必要とする。 この論文では、入力空間の解は、関数評価に含まれる知識をカプセル化した確率分布として表現される。 確率分布のこの空間では、ワッサーシュタイン距離によって与えられる計量が与えられ、モデルが目的関数に直接依存しないような新しいアルゴリズムMOEA/WSTを設計することができる。
  論文  参考訳（メタデータ） (2021-12-07T09:13:10Z)
• Result Diversification by Multi-objective Evolutionary Algorithms with Theoretical Guarantees [94.72461292387146]
  両目的探索問題として結果の多様化問題を再構成し,多目的進化アルゴリズム(EA)を用いて解くことを提案する。 GSEMOが最適時間近似比1/2$を達成できることを理論的に証明する。 目的関数が動的に変化すると、GSEMOはこの近似比をランニングタイムで維持することができ、Borodinらによって提案されたオープンな問題に対処する。
  論文  参考訳（メタデータ） (2021-10-18T14:00:22Z)
• Local AdaGrad-Type Algorithm for Stochastic Convex-Concave Minimax Problems [80.46370778277186]
  大規模凸凹型ミニマックス問題は、ゲーム理論、堅牢なトレーニング、生成的敵ネットワークのトレーニングなど、多くの応用で発生する。 通信効率のよい分散外グレードアルゴリズムであるLocalAdaSientを開発した。 サーバモデル。 等質な環境と異質な環境の両方において,その有効性を実証する。
  論文  参考訳（メタデータ） (2021-06-18T09:42:05Z)
• A hybrid MGA-MSGD ANN training approach for approximate solution of linear elliptic PDEs [0.0]
  MGA-MSGD(Modified Genetic-Multilevel Gradient Descent)トレーニングアルゴリズムを導入しました。 ANNによるPDEによって記述された3次元機械的問題の精度と効率を大幅に改善する。
  論文  参考訳（メタデータ） (2020-12-18T10:59:07Z)

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

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