文献

J-GLOBAL ID：202002213642000765   整理番号：20A1865030

定義可能楕円体法,和二乗証明および同形問題【JST・京大機械翻訳】

Definable Ellipsoid Method, Sums-of-Squares Proofs, and the Isomorphism Problem

著者 (2件)： Atserias Albert (Universitat Politecnica de Catalunya) ,  Ochremiak Joanna (Universite Paris Diderot)
資料名： ACM Proceedings  (ACM Proceedings)
号： LICS ’18  ページ： 66-75  発行年： 2018年 
JST資料番号： D0698C  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： アメリカ合衆国 (USA)  言語： 英語 (EN)

抄録/ポイント： 楕円体法は,(弱)分離問題に対するオラクルの呼び出しにより,凸集合に対する(弱)実現可能性と線形最適化問題を解決するアルゴリズムである。筆者らは,線形および半定値プログラムに対する計数(FPC)による固定点論理において,この低減が実行できることを示すための以前に知られている方法を,明示的有界凸集合の任意のファミリーに適用した。この観測を用いて,半定値プログラムに対する正確な実現可能性問題をFPCの無限バージョンで表現できることを示した。corollaryとして,グラフ等写像問題に対して,緩和のLasserre/Sums-of-Squares半定値計画階層は,Sherali-Adams線形プログラミング階層に崩壊し,その程度は小さい損失になる。Please refer to this article’s citation page on the publisher website for specific rights information. Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： アルゴリズム ,  写像 ,  線形計画法 ,  *凸集合 ,  楕円体 ,  線形性
準シソーラス用語： オラクル ,  有界 ,  半正定値プログラム , 【Automatic Indexing@JST】

著者キーワード (5件)： 楕円体法 ,  固定点論理 ,  グラフ同形問題 ,  半定値プログラミング ,  二乗和

分類 (1件)： 数理計画法  (KA03030M)

タイトルに関連する用語 (3件)： 定義 ,  楕円体 ,  証明