バイアスCSPに対する近似可能性の特性化【JST・京大機械翻訳】

Ghoshal Suprovat; Lee Euiwoong

プレプリント

J-GLOBAL ID：202202209907115527 整理番号：22P0026854

バイアスCSPに対する近似可能性の特性化【JST・京大機械翻訳】

A Characterization of Approximability for Biased CSPs

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

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

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

述語ψ:{0,1} ̄r>0,1}を持つμバイアスMax-CSPインスタンスは,制約の最大分率を満たすほとんどのμで相対重みのラベリングを見つけるための制約充足問題(CSP)の例である。Biased CSPsは汎用性があり,高密度k-Sub(Hyper)グラフや小型SetExpansionのようないくつかのよく研究されている問題を発現する。本研究では,バイアスパラメータμがバイアスCSPsの近似性に与える影響を調べた。そのようなCSPsの近似性は,最密-k-Subハイパーグラフ(DkSH)のバイアス近似曲線を用いて,特性化できる(希少性rの因子の損失まで)ことを示した。特に,これはバイアスパラメータμに依存しない近似保証を保証する述語の厳密な特性化を与える。上述のことにより,DkSHの新しい近似と硬度結果を与えた。特に,小集合拡張仮説(SSEH)を仮定すると,希少性rとk=μnを持つDkSHは,各r≧2とμ<2 ̄-rに対して,Ω(r ̄3μ ̄r-1log(1/μ))の因子に近似するNP困難であることを示した。また,同じ設定に対してO(μ ̄r-1log(1/μ))近似アルゴリズムを与えた。この上限と下限は,パリティrが一定で,特に線形バイアス領域における最密-k-Subgraph問題に対する最初の厳密な近似限界を意味するとき,一定因子まで堅くなった。さらに,上記の特性評価を用いて,著者らの結果はまた,一定の希少性のあらゆるバイアスされたCSPに対するマッチングアルゴリズムと硬度を暗示する。【JST・京大機械翻訳】

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

測光と光検出器一般 , 数値計算 , AD・DA変換回路 , 金属-絶縁体-半導体構造 , システム最適化手法

, , , ,

前のページに戻る