二分完全マッチングの近似次数【JST・京大機械翻訳】

Beniamini Gal

プレプリント

J-GLOBAL ID：202202200418357448 整理番号：21P0030492

二分完全マッチングの近似次数【JST・京大機械翻訳】

The Approximate Degree of Bipartite Perfect Matching

出版者サイト {{ this.onShowPLink() }} 複写サービスで全文入手
高度な検索・分析はJDreamⅢで

この文献はプレプリントです。プレプリントについてはこちらをご確認ください。

著者 (1件)：
資料名：
発行年： 2020年04月29日プレプリントサーバーでの情報更新日： 2022年03月02日
JST資料番号： O7000B 資料種別：プレプリント
記事区分：プレプリント発行国：アメリカ合衆国 (USA) 言語：英語 (EN)

Boole関数の近似度は,Booleハイパーキューブ上のl_∞ノルムで近似する実際の多重線形多項式の最小度である。完全マッチングを持つ全二部グラフの指標であるBiparite Perfect Matching関数の近似度はΘ(n ̄3/2)であることを示した。上界は,完全マッチング関数のBoole二重を表すユニークな多重線形多項式を,実物上で完全に特性化することによって得られる。明らかに,この多項式は,Θ(nlogn)において非常に小さなl_1ノルムのみ指数を持つことを示す。下限は,完全マッチング関数のスペクトル感度を結合して,それは,ハイパーキューブcitearonson2020度,huang2019誘導に関するそのカットグラフのスペクトル半径である。完全マッチングのスペクトル感度が正確にΘ(n ̄3/2)であることを示した。【JST・京大機械翻訳】

, , , , , , , , , , ,
, , , , 【Automatic Indexing@JST】

グラフ理論基礎 , 計算理論 , CAD,CAM , 集積回路一般

, ,

前のページに戻る