論文の概要: Quantum-Inspired Perfect Matching under Vertex-Color Constraints
- arxiv url: http://arxiv.org/abs/2209.13063v1
- Date: Mon, 26 Sep 2022 22:55:25 GMT
- ステータス: 処理完了
- システム内更新日: 2023-01-25 02:46:02.132082
- Title: Quantum-Inspired Perfect Matching under Vertex-Color Constraints
- Title（参考訳）: 頂点色制約下での量子インスパイアされた完全マッチング
- Authors: Moshe Y. Vardi and Zhiwei Zhang
- Abstract要約: PM-VCは2種類の色制約の下で複雑でアルゴリズム的な結果を与える。
PM-VC-Sym は,平面グラフ上でデランドマイズ可能なシンボリックアルゴリズムにより RNC に含まれることを示す。
PM-VC-DDでは,グラフガジェット法によりNP硬度を明らかにする。
- 参考スコア（独自算出の注目度）: 39.96302127802424
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We propose and study the graph-theoretical problem PM-VC: perfect matching
under vertex-color constraints on graphs with bi-colored edges. PM-VC is of
special interest because of its motivation from quantum-state identification
and quantum-experiment design, as well as its rich expressiveness, i.e., PM-VC
subsumes many constrained matching problems naturally, such as exact perfect
matching. We give complexity and algorithmic results for PM-VC under two types
of vertex color constraints: 1) symmetric constraints (PM-VC-Sym) and 2)
decision-diagram constraints (PM-VC-DD).
We prove that PM-VC-Sym is in RNC via a symbolic determinant algorithm, which
can be derandomized on planar graphs. Moreover, PM-VC-Sym can be expressed in
extended MSO, which encourages our design of an efficient dynamic programming
algorithm for PM-VC-Sym on bounded-treewidth graphs. For PM-VC-DD, we reveal
its NP-hardness by a graph-gadget technique. Our novel results for PM-VC
provide insights to both constrained matching and scalable quantum experiment
design.
- Abstract（参考訳）: 二色エッジを持つグラフの頂点色制約下での完全マッチング問題pm-vcを提案し,検討する。
PM-VCは、量子状態同定と量子実験設計の動機と、その豊かな表現性、すなわちPM-VCは、完全整合のような多くの制約付きマッチング問題を自然に仮定するため、特に関心がある。
2種類の頂点色制約の下でPM-VCの複雑性とアルゴリズム的結果を与える。
1)対称制約(pm-vc-sym)及び
2)決定ダイアグラム制約(pm-vc-dd)。
PM-VC-Sym は、平面グラフ上でデランドマイズ可能なシンボリック決定式アルゴリズムにより RNC に含まれることを示す。
さらに,PM-VC-Symを拡張MSOで表現することで,有界木幅グラフ上でのPM-VC-Symの効率的な動的プログラミングアルゴリズムの設計を促進することができる。
PM-VC-DDでは,グラフガジェット法によりNP硬度を明らかにする。
PM-VCの新たな結果は、制約付きマッチングとスケーラブルな量子実験設計の両方に対する洞察を提供する。
関連論文リスト
- 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。