[3Xin2-35] 整凸関数の線形補間によるL拡張可能性に関する一考察
キーワード：離散凸解析、整凸関数、L拡張可能性、半整数緩和、単体分割
整凸関数は，M凸関数やL凸関数などを含む離散凸解析における基本的な関数クラスである．近年，離散最適化問題に対するアルゴリズム開発のために，L拡張可能関数という概念が提案された．整数格子点上の関数hがL拡張可能とは，半整数格子点上のL凸関数gが存在して，gの定義域を整数格子点上に制限したものがhに一致するときにいう．このとき，gはhのL凸緩和という．L拡張可能性は，NP困難である様々な離散最適化問題に対して，近似アルゴリズムや高速な厳密解法などを開発する際に有用であることが知られている．本論文では，整凸関数のL拡張可能性について調べることを目的とする．特に，線形補間によるL拡張可能性に着目し，そのような拡張が可能である整凸関数の特徴付けについて議論する．
講演PDFパスワード認証
論文PDFの閲覧にはログインが必要です。参加登録者の方は「参加者用ログイン」画面からログインしてください。あるいは論文PDF閲覧用のパスワードを以下にご入力ください。