あらまし

半整数緩和とその応用

岩田　陽一 

Vol.101 No.3pp.284-287

発行日:2018/03/01

Online ISSN:2188-2355

Print ISSN:0913-5693

種別:小特集　グラフアルゴリズムの最先端

専門分野:

キーワード:
LP緩和, 劣モジュラ性, 分枝限定法, パラメータ化計算量, 

本文:PDF(314.6KB)>>

記事を購入

あらまし:
NP困難問題の整数制約を緩めたLP緩和は，近似計算や分枝限定法などで広く用いられている．問題によっては，最適緩和解が整数値のほかに0.5のみを持つ場合があり，そのような緩和は半整数緩和と呼ばれる．本稿では，半整数緩和の持つ良い性質を解説し，パラメータ化計算量などの理論研究への応用を紹介する．また，これらの理論研究がアルゴリズムの実性能の改善へつながることを紹介する．

ログイン

 > 

パスワードを忘れた場合は

メニュー

Online ISSN:2188-2355

…ジュニア会員・学生員に
　お勧めの記事