整凸関数の線形補間によるL拡張可能性に関する一考察

DOI

書誌事項

タイトル別名
  • A study on L-extendability of integrally convex functions by linear interpolation

説明

<p>整凸関数は，M凸関数やL凸関数などを含む離散凸解析における基本的な関数クラスである．近年，離散最適化問題に対するアルゴリズム開発のために，L拡張可能関数という概念が提案された．整数格子点上の関数hがL拡張可能とは，半整数格子点上のL凸関数gが存在して，gの定義域を整数格子点上に制限したものがhに一致するときにいう．このとき，gはhのL凸緩和という．L拡張可能性は，NP困難である様々な離散最適化問題に対して，近似アルゴリズムや高速な厳密解法などを開発する際に有用であることが知られている．本論文では，整凸関数のL拡張可能性について調べることを目的とする．特に，線形補間によるL拡張可能性に着目し，そのような拡張が可能である整凸関数の特徴付けについて議論する．</p>

収録刊行物

キーワード

詳細情報 詳細情報について

  • CRID
    1390581920995810816
  • DOI
    10.11517/pjsai.jsai2024.0_3xin235
  • ISSN
    27587347
  • 本文言語コード
    ja
  • データソース種別
    • JaLC
  • 抄録ライセンスフラグ
    使用不可

問題の指摘

ページトップへ