重み付きCSPの超再パラメータ化:特性と最適化の展望【JST・京大機械翻訳】

Dlask Tomas; Werner Tomas; de Givry Simon

プレプリント

J-GLOBAL ID：202202221298237653 整理番号：22P0024255

重み付きCSPの超再パラメータ化:特性と最適化の展望【JST・京大機械翻訳】

Super-Reparametrizations of Weighted CSPs: Properties and Optimization Perspective

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

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

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

※このプレプリント論文は学術誌に掲載済みです。なお、学術誌掲載の際には一部内容が変更されている可能性があります。

重み付けCSPs(WCSPs)の再パラメータ化の概念(WCSPの等価保存変換としても知られる)はよく知られており,最適WCSP値を近似または結合するために多くのアルゴリズムでの使用を見出す。対照的に,超再パラメータ化の概念(あらゆる割当に対するWCSP目標を保っているか増加する重みの変化である)は既に提案されているが,詳細には研究されていない。このギャップを埋めるために,超パラメータ化の多くの理論的特性を提示し,それらを再パラメータ化のそれらと比較した。さらに,超再パラメータ化を用いて(最大)WCSPの最適値の上限を計算するためのフレームワークを提案した。境界を改善するために,任意の(いくつかの技術的条件)制約伝搬ルールを採用することが原理的に可能であることを示した。特にアーク一貫性のために,この方法は既知の仮想AC(VAC)アルゴリズムに縮小する。シングルトンアーク一貫性(SAC)の方法を実装し,それを公開ベンチマーク上のWCSPにおける他の強い局所一貫性と比較した。結果は,SACから得られた限界が,多くの実例グループで優れていることを示す。【JST・京大機械翻訳】

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

計算理論 , 数理計画法 , 電力変換器 , 数値計算 , 人工知能

, , ,

前のページに戻る