文献

J-GLOBAL ID：201602213709533763   整理番号：16A0007099

安定集合問題のコポジティブな定式化に対するLPベース近似について

On LP-based approximation for copositive formulation of stable set problem

著者 (1件)： TONO Katsuya (Graduate School of Information Sci. and Technol., The Univ. of Tokyo)
資料名： JSIAM Letters (Web)  (JSIAM Letters (Web))
巻： 7  ページ： 69-72 (J-STAGE)  発行年： 2015年 
JST資料番号： U0115A  ISSN： 1883-0617  資料種別： 逐次刊行物 (A)
記事区分： 短報  発行国： 日本 (JPN)  言語： 英語 (EN)

抄録/ポイント： De Klerk-Pasechnik(2002年)はコポジティブなプログラミングによって安定数α(G)を計算する方法を示し,コポジティブなプログラムに対するLPおよびSDPベース近似方式を提案した。本論文において筆者らは,安定集合問題に対する彼らのLPベース近似が,Motzkin-Straus理論の離散化バージョンとして見ることができる,シンプレックス上の合理的グリッドにわたる2次形式を最小化する問題と等価であることを示した。さらに筆者らは,LPベース近似の最適解から最大安定集合を回復するアルゴリズムを与え,安定集合問題に対する単純な局所検索ヒューリスティクスを提案した。

シソーラス用語： *集合 ,  *定式化 ,  *線形計画法 ,  近似法 ,  数学的変換 ,  格子 ,  二次形式 ,  アルゴリズム
準シソーラス用語： *LP【線形計画法】 ,  グリッド ,  *近似 ,  離散化

分類 (2件)： 数値解析,近似法  (AB04000F) ,  数理計画法  (KA03030M)

タイトルに関連する用語 (5件)： 集合 ,  問題 ,  定式化 ,  LP ,  近似