論文の概要: Quantum-Inspired Perfect Matching under Vertex-Color Constraints
- arxiv url: http://arxiv.org/abs/2209.13063v2
- Date: Thu, 30 Mar 2023 03:55:03 GMT
- ステータス: 処理完了
- システム内更新日: 2023-03-31 17:59:30.440634
- Title: Quantum-Inspired Perfect Matching under Vertex-Color Constraints
- Title（参考訳）: 頂点色制約下での量子インスパイアされた完全マッチング
- Authors: Moshe Y. Vardi and Zhiwei Zhang
- Abstract要約: EXISTS-PMVCは、二色のエッジを持つグラフ上での完全マッチングのためのグラフ理論上の問題である。
色制約が2種類あるEXISTS-PMVCに対して,複雑でアルゴリズム的な結果を与える。
有界な色数を持つEXISTS-PMVC-Symは、Exact Perfect Matchingと同じくらい難しいことを証明する。
- 参考スコア（独自算出の注目度）: 39.96302127802424
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We propose and study the graph-theoretical problem EXISTS-PMVC: the existence
of perfect matching under vertex-color constraints on graphs with bi-colored
edges. EXISTS-PMVC is of special interest because of its motivation from
quantum-state identification and quantum-experiment design, as well as its rich
expressiveness, i.e., EXISTS-PMVC naturally subsumes many constrained matching
problems, such as exact perfect matching. We give complexity and algorithmic
results for EXISTS-PMVC under two types of vertex color constraints: 1)
symmetric constraints (EXISTS-PMVC-Sym) and 2) decision-diagram constraints
(EXISTS-PMVC-DD).
For EXISTS-PMVC-DD, we reveal its NP-hardness by a graph-gadget-based
technique. We prove that EXISTS-PMVC-Sym with a bounded number of colors
(EXISTS-PMVC-Sym-Bounded) is as hard as Exact Perfect Matching (XPM), which
indicates EXISTS-PMVC-Sym-Bounded is in RNC on general graphs and PTIME on
planar graphs. Directly applying algorithms for XPM to solve
EXISTS-PMVC-Sym-Bounded is, however, impractical due to the overhead brought by
the reduction. Therefore, we propose algorithms that natively handle
EXISTS-PMVC-Sym-Bounded with significantly better efficiency. Our novel results
for EXISTS-PMVC provide insights into both constrained matching and scalable
quantum experiment design.
- Abstract（参考訳）: 両色エッジを持つグラフに頂点色制約の下で完全マッチングが存在するというグラフ理論問題EXISTS-PMVCを提案する。
EXISTS-PMVCは、量子状態の同定と量子実験設計によるモチベーションと、その豊かな表現性、すなわち、EXISTS-PMVCは、完全マッチングのような多くの制約付きマッチング問題を自然に仮定するため、特に関心がある。
我々は,2種類の頂点色制約の下で,EXISTS-PMVCの複雑さとアルゴリズム的結果を与える。
1)対称制約(EXISTS-PMVC-Sym)と
2)決定ダイアグラム制約(exists-pmvc-dd)。
EXISTS-PMVC-DDでは,グラフガジェット法によりNP硬度を明らかにする。
有界な色数(EXISTS-PMVC-Sym-Bunded)のEXISTS-PMVC-Sym-BundedがExact Perfect Matching(XPM)と同じくらい硬いことを証明した。
しかしながら、XPM が EXISTS-PMVC-Sym-Bounded を解くために直接アルゴリズムを適用することは、削減によって引き起こされるオーバーヘッドのために現実的ではない。
そこで本研究では,EXISTS-PMVC-Sym-Boundedを効率よくネイティブに処理するアルゴリズムを提案する。
EXISTS-PMVCの新たな結果は、制約付きマッチングとスケーラブルな量子実験設計の両方に関する洞察を提供する。
関連論文リスト
- Collaborative non-parametric two-sample testing [55.98760097296213]
目標は、null仮説の$p_v = q_v$が拒否されるノードを特定することである。
グラフ構造を効率的に活用する非パラメトリックコラボレーティブ2サンプルテスト(CTST)フレームワークを提案する。
提案手法は,f-divergence Estimation, Kernel Methods, Multitask Learningなどの要素を統合する。
論文 参考訳（メタデータ） (2024-02-08T14:43:56Z) - Damped Proximal Augmented Lagrangian Method for weakly-Convex Problems
with Convex Constraints [17.25924791071807]
弱拘束的目的と凸・非拘束的制約の問題を解くために、減衰した近位グランジアン法(DPALM)を提案する。
DPALM は APG を用いて各サブプロブレムを線形に滑らかに解くことで,約$varepsilon$-KK 点を生成可能であることを示す。
論文 参考訳（メタデータ） (2023-11-15T16:05:43Z) - Graph-Aware Contrasting for Multivariate Time-Series Classification [50.84488941336865]
既存のコントラスト学習手法は主に、時間的拡張とコントラスト技術による時間的一貫性を達成することに焦点を当てている。
MTSデータ間の空間的整合性を考慮したグラフ認識コントラストを提案する。
提案手法は,様々なMSS分類タスクにおける最先端性能を実現する。
論文 参考訳（メタデータ） (2023-09-11T02:35:22Z) - Scalable Incomplete Multi-View Clustering with Structure Alignment [71.62781659121092]
本稿では,新しいアンカーグラフ学習フレームワークを提案する。
ビュー固有のアンカーグラフを構築し、異なるビューから補完情報をキャプチャする。
提案したSIMVC-SAの時間と空間の複雑さはサンプル数と線形に相関していることが証明された。
論文 参考訳（メタデータ） (2023-08-31T08:30:26Z) - Single-Stage Visual Relationship Learning using Conditional Queries [60.90880759475021]
TraCQは、マルチタスク学習問題とエンティティペアの分布を回避する、シーングラフ生成の新しい定式化である。
我々は,DETRをベースとしたエンコーダ-デコーダ条件付きクエリを用いて,エンティティラベル空間を大幅に削減する。
実験結果から、TraCQは既存のシングルステージシーングラフ生成法よりも優れており、Visual Genomeデータセットの最先端の2段階メソッドを多く上回っていることがわかった。
論文 参考訳（メタデータ） (2023-06-09T06:02:01Z) - HyRSM++: Hybrid Relation Guided Temporal Set Matching for Few-shot
Action Recognition [51.2715005161475]
そこで本研究では,数発のアクション認識のための時間的マッチング手法として,ハイブリッドリレーションド・テンポラル・セット・マッチングを提案する。
HyRSM++の中核となる考え方は、すべてのビデオをタスクに統合して差別的な表現を学ぶことである。
提案手法は,様々な撮影条件下での最先端性能を実現する。
論文 参考訳（メタデータ） (2023-01-09T13:32:50Z) - Deep Graph Matching under Quadratic Constraint [30.72996618021077]
深部グラフマッチングフレームワークに組み込まれたtextbfquadratic 制約として,ペアワイズグラフ構造を明示的に定式化することを提案する。
二次制約はグラフ間の対構造的な相違を最小限に抑え、抽出したCNN特徴のみを用いて得られるあいまいさを軽減できる。
より正確かつ適切な監視を行うために、クラス不均衡に対する適切に設計された偽マッチング損失が提案され、過度に適合しない偽陰性や偽陽性をよりよく罰できる。
論文 参考訳（メタデータ） (2021-03-11T12:51:12Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。