多品種流・施設配置・ネットワークデザインに対する離散構造とアルゴリズム
【研究分野】数理情報学
【研究キーワード】
多品種フロー / 施設配置問題 / ネットワークデザイン / 離散凸解析 / 劣モジュラ最適化 / 多項式時間アルゴリズム
【研究成果の概要】
本研究課題において，離散最適化分野における多品種流，施設配置問題，ネットワークデザイン問題にまたがる新しい有用な離散構造論を展開した．特に，整数格子上の離散凸関数の理論であった離散凸解析をより一般的な離散構造上へと部分的に拡張することに成功した．この理論に基づいて，これまで良いアルゴリズムが知られていなかった多品種流問題のクラスに対し組合せ的多項式時間アルゴリズムの開発した．さらに，その応用として，点容量型マルチカット問題へ組合せ的２近似アルゴリズムを開発した．
【研究代表者】
【研究種目】基盤研究(C)
【研究期間】2014-04-01 - 2018-03-31
【配分額】3,770千円 (直接経費: 2,900千円、間接経費: 870千円)