論文の概要: Unlocking the Potential of Operations Research for Multi-Graph Matching
- arxiv url: http://arxiv.org/abs/2406.18215v1
- Date: Wed, 26 Jun 2024 09:58:05 GMT
- ステータス: 処理完了
- システム内更新日: 2024-06-27 13:59:06.911643
- Title: Unlocking the Potential of Operations Research for Multi-Graph Matching
- Title（参考訳）: マルチグラフマッチングのための操作研究の可能性の解き放つ
- Authors: Max Kahl, Sebastian Stricker, Lisa Hutschenreiter, Florian Bernard, Bogdan Savchynskyy,
- Abstract要約: マルチグラフマッチングはコンピュータビジョンにおいて、例えば画像や形状のマッチングにおいて中心的な役割を果たす。
我々はMDAPのよく知られた近似アルゴリズムを不完全な多重グラフマッチングに転送する。
私たちのアルゴリズムは、2分以内でそれぞれ500以上のキーポイントを持つ29の画像と一致します。
- 参考スコア（独自算出の注目度）: 14.3836693915104
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We consider the incomplete multi-graph matching problem, which is a generalization of the NP-hard quadratic assignment problem for matching multiple finite sets. Multi-graph matching plays a central role in computer vision, e.g., for matching images or shapes, so that a number of dedicated optimization techniques have been proposed. While the closely related NP-hard multi-dimensional assignment problem (MDAP) has been studied for decades in the operations research community, it only considers complete matchings and has a different cost structure. We bridge this gap and transfer well-known approximation algorithms for the MDAP to incomplete multi-graph matching. To this end, we revisit respective algorithms, adapt them to incomplete multi-graph matching, and propose their extended and parallelized versions. Our experimental validation shows that our new method substantially outperforms the previous state of the art in terms of objective and runtime. Our algorithm matches, for example, 29 images with more than 500 keypoints each in less than two minutes, whereas the fastest considered competitor requires at least half an hour while producing far worse results.
- Abstract（参考訳）: 複数の有限集合をマッチングするNPハード二次代入問題の一般化である不完全多重グラフマッチング問題を考察する。
マルチグラフマッチングは、画像や形状をマッチングするコンピュータビジョンにおいて中心的な役割を果たすため、多くの専用最適化技術が提案されている。
NP-hard multi-dimensional assignment problem (MDAP) は、運用研究コミュニティにおいて何十年も研究されてきたが、完全なマッチングのみを考慮し、コスト構造が異なる。
このギャップを埋め、MDAPのよく知られた近似アルゴリズムを不完全な多重グラフマッチングに転送する。
この目的のために、各アルゴリズムを再検討し、不完全な多重グラフマッチングに適応し、拡張および並列化バージョンを提案する。
実験により,我々の新しい手法は,目的と実行の両面で,従来の最先端の手法よりも大幅に優れていたことが確認された。
私たちのアルゴリズムは、2分未満でそれぞれ500以上のキーポイントを持つ29の画像と一致します。
関連論文リスト
- Recombination vs Stochasticity: A Comparative Study on the Maximum Clique Problem [0.393259574660092]
最大傾き問題(英: maximum clique problem、MCP)は、グラフ理論と計算複雑性の基本的な問題である。
様々なメタヒューリスティックがMPPを近似するために使われており、遺伝的アルゴリズムやメメティックアルゴリズム、アリコロニーアルゴリズム、欲求アルゴリズム、タブアルゴリズム、シミュレートされたアニーリングなどがある。
以上の結果から,モンテカルロのアルゴリズムはランダム検索を用いてグラフを生成するが,速度と能力の両面で遺伝的アルゴリズムを上回っていることが示唆された。
論文 参考訳（メタデータ） (2024-09-26T12:50:00Z) - Semisupervised score based matching algorithm to evaluate the effect of public health interventions [3.221788913179251]
1対1のマッチングアルゴリズムでは、マッチする多数の"ペア"は、大きなサンプルからの情報と多数のタスクの両方を意味する可能性がある。
本稿では,2次スコア関数 $S_beta(x_i,x_j)= betaT (x_i-x_j)(x_i-x_j)T beta$ に基づく新しい1対1マッチングアルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-03-19T02:24:16Z) - Multilevel Memetic Hypergraph Partitioning with Greedy Recombination [0.0]
KaHyPar-Eはハイパーグラフ分割問題のために設計された最初のマルチレベルメメティック計算アルゴリズムである。
問題固有のリコンビネーションと突然変異演算子を導入し,KaHyPar-Eとそれらの演算子を組み合わせることで,新しいマルチレベルメメティックアルゴリズムを開発した。
我々のアルゴリズムは他のすべてより優れていて、最高のソリューションは12ドル、15ドル、25ドル、それぞれ2ドル、4ドル、そして8ドルだ。
論文 参考訳（メタデータ） (2022-04-07T20:45:17Z) - Multidimensional Assignment Problem for multipartite entity resolution [69.48568967931608]
Multipartiteエンティティ解決は、複数のデータセットから1つのエンティティにレコードを統合することを目的としている。
代入問題を解くために、グリーディアルゴリズムと大規模近傍探索という2つの手順を適用する。
データベースのサイズが大きくなるにつれて、設計ベースのマルチスタートがより効率的であることを示す。
論文 参考訳（メタデータ） (2021-12-06T20:34:55Z) - Graph Matching via Optimal Transport [11.93151370164898]
グラフマッチング問題の解決は、運用研究、コンピュータビジョン、神経科学などへの応用により、ますます重要になっている。
現在の最先端のアルゴリズムは、非常に大きなグラフのマッチングには非効率であるが、精度は高い。
我々は,最新のグラフマッチングアルゴリズム "FAQ" (Vogelstein, 2015) を改良した GOAT を,その線形和割り当てステップを Cuturi (2013) の "Lightspeed Optimal Transport" メソッドに置き換える。
論文 参考訳（メタデータ） (2021-11-09T19:18:18Z) - Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。
問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。
本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-01-07T08:00:02Z) - Isometric Multi-Shape Matching [50.86135294068138]
形状間の対応を見つけることは、コンピュータビジョンとグラフィックスの基本的な問題である。
アイソメトリーは形状対応問題においてしばしば研究されるが、マルチマッチング環境では明確には考慮されていない。
定式化を解くのに適した最適化アルゴリズムを提案し,コンバージェンスと複雑性解析を提供する。
論文 参考訳（メタデータ） (2020-12-04T15:58:34Z) - Efficient Computation of Expectations under Spanning Tree Distributions [67.71280539312536]
本稿では,エッジファクター,非プロジェクティブ・スパンニングツリーモデルにおいて,一階期待と二階期待の重要なケースに対する統一アルゴリズムを提案する。
我々のアルゴリズムは勾配と期待の基本的な関係を利用しており、効率的なアルゴリズムを導出することができる。
論文 参考訳（メタデータ） (2020-08-29T14:58:26Z) - Learning to Accelerate Heuristic Searching for Large-Scale Maximum
Weighted b-Matching Problems in Online Advertising [51.97494906131859]
バイパルタイトbマッチングはアルゴリズム設計の基本であり、経済市場や労働市場などに広く適用されている。
既存の正確で近似的なアルゴリズムは、通常そのような設定で失敗する。
我々は、以前の事例から学んだ知識を活用して、新しい問題インスタンスを解決するtextttNeuSearcherを提案する。
論文 参考訳（メタデータ） (2020-05-09T02:48:23Z) - Finite-Time Last-Iterate Convergence for Multi-Agent Learning in Games [116.0771177871705]
我々は,$lambda$-cocoerciveゲーム上での連立OGD学習における有限時間最終点収束率を特徴付ける。
新たなダブルストッピング時間法により, この適応アルゴリズムは, 非適応的手法と同じ有限時間終点収束率が得られることを示す。
論文 参考訳（メタデータ） (2020-02-23T01:46:34Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。