論文の概要: Exact Optimal Transport by Matching

• arxiv url: http://arxiv.org/abs/2610.04085v1
• Date: Fri, 02 Oct 2026 21:46:52 GMT
• ステータス: 情報取得中
• システム内更新日: 2026-10-06 21:43:57.366071
• Title: Exact Optimal Transport by Matching
• Title（参考訳）: マッチングによるエクササイズ輸送
• Abstract要約: 正マッチングは、中等度n体制のどの近似法よりも高速であることを示す。 単純なkNNプールギャップ証明書は、高密度で実現可能な下界を生成する。 シンクホーン家の大規模な高密度政権は認められておらず、触れられていない。
• 参考スコア（独自算出の注目度）: 0.0
• License:
• Abstract: Balanced discrete optimal transport between n sources and n targets of unit mass is exactly the minimum-cost assignment problem-a bipartite perfect matching-and is therefore solvable exactly by industrial matching engines in milliseconds to seconds. We ask when the exact approach beats the standard approximate alternatives, entropic Sinkhorn and its accelerated variant Greenkhorn, and make the sparse-exact side certified by a textbook LP dual-feasibility clip. Three contributions. (i) Measurement: on dense 2-D instances, exact matching (Jonker-Volgenant) is faster and strictly more accurate than either approximate method throughout the moderate-n regime (0.01 s at n=500 to 11.5 s at n=8000); reaching a 1% quality target on the same hardware requires roughly 10-80 min for Greenkhorn (factors 4e2-6e4 over exact; plain Sinkhorn is 20-650x slower still), a rough power-law projection beyond the measured range. Greenkhorn's measured speedup over plain Sinkhorn is only 1.0-1.5x on most converged cells. (ii) A simple kNN-pool gap certificate: given a pool matching and its Blossom dual, a one-pass O(n^2) clip produces a dense-feasible lower bound; combined with the Sinkhorn dual potential (valid at every iterate, not just at convergence), the bound is valid on all 45 measured configurations and tightens monotonically with k. (iii) A multi-robot task-allocation sanity check where the discrete plan is the deliverable: per-round exact assignment costs 0.1-68 ms, while a Sinkhorn-plus-hardening pipeline costs 0.12-15.9 s and accumulates 6-27% extra travel over 15 rounds. The Sinkhorn family's large-n dense regime is acknowledged and left untouched. Code, data, and results under MIT: https://github.com/dimkadimon/OT-Blossom.
• Abstract（参考訳）: 単位質量の n 個のソースと n 個のターゲットの間のバランスの取れた最適な輸送は、正確には最小コストの割り当て問題であり、二部完全マッチングであり、したがって工業用マッチングエンジンによってミリ秒から秒で正確に解ける。 エントロピー的なシンクホーンとその加速された変種であるGreenkhornに対して,正確なアプローチが標準的な近似代替品に勝るかどうかを問うとともに,教科書LP二重実現クリップによりスパースエクサクティサイドを認定する。 3つの貢献。 (i)高密度2次元の場合において、正正整合(Jonker-Volgenant)は、中等度n系全体(n=500から11.5 s、n=8000)の近似法よりも高速で正確であり、同じハードウェア上で1%の品質目標に達するには、グリーンクホーン(正確には4e2-6e4)の約10-80 分(正確には4e2-6e4)が必要であり、通常のシンクホーンは20-650 倍遅い。 グリーンホーンのシンクホーン上の測定速度は、ほとんどの収束した細胞では1.0-1.5倍である。 (ii)単純なkNNプールギャップ証明書:プールマッチングとそのBlossom双対が与えられた場合、ワンパスのO(n^2)クリップは、シンクホーン双対ポテンシャル(収束だけではなく、全ての反復で無効)と組み合わせて、45個の測定された構成すべてに有効であり、kで単調に締め付ける。 三 個別の計画が納品されるマルチロボットのタスク割り当て衛生チェック。一周あたりの正確な割り当ては0.1～68ms、シンクホーン+硬化パイプラインは0.12～15.9s、合計15回以上は6～27%の余分な旅行費がかかる。 シンクホーン家の大規模な高密度政権は認められておらず、触れられていない。 MITのコード、データ、結果:https://github.com/dimkadimon/OT-Blossom.com

関連論文リスト

• UltraMatch: Transport Path Routing for Ultra-Fast and Memory-Efficient Image Matching [76.1295726577623]
  UltraMatchは、超効率的でスケーラブルなセミセンスマッチングフレームワークである。 これは、候補マッチングパスのごく一部だけをルーティングすることで、高密度トークンレベルのマッチングの二次計算とメモリコストをバイパスする。
  論文  参考訳（メタデータ） (2026-09-29T08:15:55Z)
• SinkSLOT: Sinkhorn via Sparse Lifted Optimal Transport [3.4494862188977637]
  Standard Sinkhorn-Knoppアルゴリズムには2つの制限がある。 SinkSLOTは、Gibsカーネルを非依存の事前結合でスパースする自然な方法として、期待されるスライスされたリフテッドトランスポート計画を公開した。 合成ベンチマークの実験により、SinkSLOTは最先端の高密度でスパースなEOT法よりもかなり高速であることが示された。
  論文  参考訳（メタデータ） (2026-08-28T12:24:40Z)
• ForgettingOT: Certified Speculative Batching from Sinkhorn's Projective Forgetting [0.0]
  固定点ヤコビアン$J_tstar=QP=Pstar P$ の固有モードが厳密な補正テールを制御することを示す。 ForgettingOTは、この非線形ペロン-フロベニウスの事実をシンクホーン問題のストリームの認定執行者に変える。
  論文  参考訳（メタデータ） (2026-07-27T17:59:36Z)
• Non-Expansive Two-Time-Scale Stochastic Approximation: A Fixed-Schedule One-Quarter Barrier and Bias-Corrected Acceleration [46.80389197344682]
  遅いクラスノセルスキイ-マンの不動点反復が支配する2次元近似について検討する。 ネストされたTikhonov-KMアルゴリズムでは、補正されていないオラクルは総サンプルレートが$T-1/4+o(1)$となる。
  論文  参考訳（メタデータ） (2026-07-15T03:33:03Z)
• Towards Scalable Persistence-Based Topological Optimization [44.16669776030478]
  永続性に基づく位相最適化は、点クラウド $X の部分集合 mathbbRd$ を $L(X) = ell(mathrmDgm(X))$ という形の目的を最小化することによって変形する。 実際、最適化は2つの結合した問題によって制限される: 永続ホモロジーは典型的にはサブサンプル上で計算され、結果として生じる位相勾配は非常にスパースであり、非ゼロ更新を受けるアンカーポイントはわずかである。
  論文  参考訳（メタデータ） (2026-05-09T15:47:20Z)
• Statistical Analysis of the Sinkhorn Iterations for Two-Sample Schrödinger Bridge Estimation [11.478463820527745]
  2サンプル推定設定における中間シンクホーン反復の統計的性能について検討した。 我々はシンクホーン橋の繰り返しの2乗全変分誤差の統計的境界を確立する。 この結果は、Schr"odingerブリッジ推定器の有限サンプル性能を理論的に保証する。
  論文  参考訳（メタデータ） (2025-10-26T07:39:36Z)
• Near-Optimal Clustering in Mixture of Markov Chains [74.3828414695655]
  我々は、長さ$H$の軌跡を、大きさ$S$の有限状態空間上の未知のエルゴードマルコフ鎖の1つによって生成される、$T$ trajectories of length $H$の問題を研究する。 我々は、連鎖の遷移核間の重み付きKL分散によって支配されるクラスタリングエラー率に基づいて、インスタンス依存で高い確率の低い境界を導出する。 次に,新しい2段階クラスタリングアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2025-06-02T05:10:40Z)
• Accelerating Sinkhorn Algorithm with Sparse Newton Iterations [14.094908995798757]
  本稿ではSinkhornアルゴリズムの拡張であるSinkhorn-Newton-Sparse(SNS)を提案する。 SNSは、広範囲の実践事例において、注文を桁違いに早く収束させる。
  論文  参考訳（メタデータ） (2024-01-20T21:23:09Z)
• Unimon qubit [42.83899285555746]
  超伝導量子ビットは、量子コンピュータを実装する最も有望な候補の1つである。 本稿では,高非線形性,dc電荷雑音に対する完全な感度,フラックス雑音に対する感度,共振器内の1つのジョセフソン接合のみからなる単純な構造を結合した超伝導量子ビット型ユニモンについて紹介し,実演する。
  論文  参考訳（メタデータ） (2022-03-11T12:57:43Z)

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

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