文献

J-GLOBAL ID：202202257903489131   整理番号：22A0801882

最適化におけるツリー幅ベーストラクトビリティの新しい限界【JST・京大機械翻訳】

New limits of treewidth-based tractability in optimization

著者 (4件)： Faenza Yuri (Industrial Engineering and Operations Research, Columbia University, New York, USA) ,  Munoz Gonzalo (Institute of Engineering Sciences, Universidad de O’Higgins, Rancagua, Chile) ,  Pokutta Sebastian (Zuse Institute Berlin, Berlin, Germany) ,  Pokutta Sebastian (Department of Mathematics, Technische Universitaet Berlin, Berlin, Germany)
資料名： Mathematical Programming  (Mathematical Programming)
巻： 191  号： 2  ページ： 559-594  発行年： 2022年 
JST資料番号： B0847B  ISSN： 0025-5610  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： ドイツ (DEU)  言語： 英語 (EN)

抄録/ポイント： スパース構造は,最適化問題における扱いやすさを追求するとき,しばしば探索される。それらは,スパース性が存在するとき管理可能になる複雑な問題を取り扱うために,理論的および計算的展望の両方から活用される。このタイプの構造の用例は,木幅によって与えられる:グラフ理論パラメータ,グラフがグラフであるかどうかを測定するグラフ理論パラメータ。このパラメータは,様々な最適化問題の複雑性を分析し,このパラメータが有界である問題のための扱いやすいアルゴリズムを得るために数十年間使用されてきた。本研究の目標は,最適化における木幅ベースの扱いやすさの限界の理解に寄与することである。結果は次の通りである。最初に,ある意味において,低木幅に基づく拡張複雑性に関する既に知られている肯定的結果が,最良であることを証明する。第2に,穏やかな仮定の下で,著者らは,ツリー幅が,広いクラスの最適化問題,機械学習におけるグラフモデルにおいてよく知られている事実,および,ここでは,最適化における近似設定に拡張する制約充足問題において,扱いやすさを与える唯一のグラフ理論パラメータであることを証明した。Copyright Springer-Verlag GmbH Germany, part of Springer Nature and Mathematical Optimization Society 2020 Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： アルゴリズム ,  グラフ ,  *最適化 ,  グラフ理論 ,  最適化問題 ,  理論 ,  近似法 ,  限界 ,  機械学習 ,  制約充足問題
準シソーラス用語： 木幅 ,  スパース性 ,  グラフモデル ,  複雑性 ,  有界 , 【Automatic Indexing@JST】

著者キーワード (4件)： ツリー幅 ,  構造化スパース性 ,  半確定拡張複雑性 ,  QCQPの近似

分類 (2件)： グラフ理論基礎  (IA02020S) ,  計算理論  (JB02000A)

タイトルに関連する用語 (2件)： 最適化 ,  限界