数理計画問題に内在する大域的性質に基づく多項式時間アルゴリズムの構築

点击翻译按钮获取中文摘要

数理計画問題の解法として単体法[Dantzig(1947)]を起源とするピボットアルゴリズムがある。多項式時間を達成するピボットアルゴリズムの存在解明は数理計画問題における重要な未解決事項である。線形計画問題の一部を多項式回数の反復で解くアルゴリズムの達成[Gaertner(2002)]を機に，研究代表者はこの成功の核となった数理計画問題に内在する大域的性質に着目し，従来のピボットアルゴリズムが注視する数理計画問題の局所構造からは得られない大域的性質の重要性を明らかにしてきた。本研究では「(A)数理計画問題の大域的性質に基づく多項式時間ピボットアルゴリズムの構築」を目指して進めてきたが，そのアプローチの1つと想定していた「(B)離散勾配流によるピボットアルゴリズムの高速化の実現」について当初の想定より難しいことが判明した。また，22年度は私事により研究代表者の研究時間の確保が難しかったことから，最終年度の23年度（延長）に向けて研究計画の見直しをする必要が生じた。そこで，(A)を達成するうえで数理計画問題の多面体的構造の把握が重要であることと，もう1つの目標として「(C)マトロイドとその表現可能性からみた多面体の離散構造」があることから，23年度に向けて多面体の離散構造の把握に集中することにした。22年度は，20年度後半より開始した多面体とその計算に関する本の執筆を終え，現在校正段階である。本著を執筆する過程で多面体に関する書籍が少ないことを改めて認識し，本著より更に平易な内容を含む多面体の離散構造に関する別の書籍の執筆を開始した。