【研究分野】情報学基礎理論

【研究領域課題番号】16K00023 (KAKENデータベースで見る）

【研究キーワード】

離散資源配分問題 / 離散最適化 / 離散凸解析 / 離散配分問題 / 離散凸関数 / 離散構造 / 情報基礎 / アルゴリズム

【研究成果の概要】

離散凸解析を武器としての複雑な制約をもつ離散資源配分問題の研究と現実問題へのフィードバックを目的とした研究課題ですが，設定した５つのテーマそれぞれについて理論的な研究成果を得ました．また，現実問題へのフィードバックに関しては，提案したアルゴリズムをソフトウエア化し，研究期間初年度末から現在に至るまで所属機関のおける学科分けという現実問題を解くために利用しています．

【研究の社会的意義】

離散資源配分問題は，学生の学科への配属等の現実問題と強い関係があります．現実的な離散資源配分問題は複雑な制約を有することが多く，これらに対する研究は学術的にも社会的にも意義のあるものです．本研究成果では，良い構造を有する離散凸解析を武器として，理論的な研究成果を得た一方で，複雑な制約を有する学科分け問題という現実問題の解決に理論的成果を応用した点であり，他の現実的な問題への拡大利用も可能であることから，その社会的意義は高いと思われます．

【研究種目】基盤研究(C)

【研究期間】2016-04-01 - 2022-03-31

【配分額】4,420千円 (直接経費: 3,400千円、間接経費: 1,020千円)

【研究分野】数理情報学

【研究領域課題番号】15K00030 (KAKENデータベースで見る）

【研究キーワード】

離散凸関数 / 離散凸解析 / 離散DC関数 / 離散最適化 / アルゴリズム / DC関数

【研究成果の概要】

離散ＤＣ関数最小化問題に対して，解きやすい問題クラスの検出や精度保証付き近似アルゴリズムの構築を目指した．また，DC関数を構成するM凸関数，L凸関数自体の構造をより良く理解することを目的として，M凸関数およびL凸関数の最小化問題という，基本的な問題の再検討を行い，アルゴリズムの改良を行うと同時に，計算量の解析方法の改善を実現した．さらに，離散凸関数の制約なし最小化問題と離散DC関数最小化問題の中間に位置する問題についても調査し，これらの問題の構造を明らかにするとともに，その結果を利用して高速なアルゴリズムを提案した．

【研究の社会的意義】

本研究課題で得られた成果により，高速に解くことのできる離散最適化問題の新たな枠組みを提示できた．また，これまで高速なアルゴリズムが知られていなかった様々な離散最適化問題に対して高速なアルゴリズムを提供できたとともに，高速なアルゴリズムが存在していた問題に対しては，より高速なアルゴリズムを提供できた．これらの研究成果が直接，現実の問題に適用できるとは限らないが，現実の複雑な問題を高速に解くことを目指す際，本研究課題で得られたアルゴリズムの活用が期待される．

【研究種目】基盤研究(C)

【研究期間】2015-04-01 - 2019-03-31

【配分額】4,680千円 (直接経費: 3,600千円、間接経費: 1,080千円)

【研究分野】数理情報学

【研究領域課題番号】25280004 (KAKENデータベースで見る）

【研究キーワード】

離散最適化 / 組合せ最適化 / 劣モジュラ関数 / 離散アルゴリズム / アルゴリズム / 劣モジュラ構造 / 数理計画

【研究成果の概要】

劣モジュラ的な離散構造に基づいて、離散最適化・組合せ最適化の理論とアルゴリズムの基礎研究を展開し、多くの研究成果を上げている。中でも、劣モジュラ構造を基礎とする離散凸関数の新たな理論を構築し、最近世界で注目される劣モジュラ的な関数(新たに導入した横断劣モジュラ関数、歪双劣モジュラ関数等）に関連する最大・最小定理を始め、離散最適化・組合せ最適化の理論と効率的アルゴリズムの基礎となる離散構造を解明した。さらに、非分割財の経済やゲーム論的配分の問題における劣モジュラ構造の有用性を明らかにした。

【研究の社会的意義】

大規模な離散最適化・組合せ最適化問題を厳密に、あるいは、近似的に解くための効率的アルゴリズムの構築に向けて、劣モジュラ的な離散構造の有効性を明らかにした。学術的な意義としては、離散最適化・組合せ最適化の理論と効率的アルゴリズムの基礎となる、離散凸関数の新たな理論構築や、新たな劣モジュラ的関数に関連する最大・最小定理の導出等であり、社会的意義としては、非分割財の経済やゲーム論的配分の問題における劣モジュラ構造の有用性の解明等である。

【研究種目】基盤研究(B)

【研究期間】2013-04-01 - 2019-03-31

【配分額】17,420千円 (直接経費: 13,400千円、間接経費: 4,020千円)

【研究分野】情報学基礎

【研究領域課題番号】24500002 (KAKENデータベースで見る）

【研究キーワード】

整数計画問題 / 非線形関数 / アルゴリズム / 離散最適化 / 離散凸解析 / 非線形計画問題 / 近似アルゴリズム / 離散凸関数 / 組合せ最適化

【研究成果の概要】

本研究では，非線形な不等式制約の下で非線形関数を最大化するという整数計画問題に対し，解の精度および計算時間に関する理論的な保証を与える近似解法を開発することを目指した．本研究の主結果として，ナップサック制約の下で１つのM凹関数を最大化するという問題に対し，制約が複数個の場合でも，連続緩和アプローチを用いて任意の精度の近似解を多項式時間で求められることを示した．また，目的関数が２つのM凹関数の和の場合には，ラグランジュ緩和アプローチを用いて任意の精度の近似解が得られることを示した．

【研究種目】基盤研究(C)

【研究期間】2012-04-01 - 2016-03-31

【配分額】5,330千円 (直接経費: 4,100千円、間接経費: 1,230千円)

【研究分野】情報学基礎

【研究領域課題番号】24300003 (KAKENデータベースで見る）

【研究キーワード】

離散最適化 / 離散構造 / 離散凸解析 / 資源配分問題 / マッチング / 戦略的頑健性 / アルゴリズム / 配属問題 / 国際情報交換 / 国際研究者交流 / ハンガリー / 安定結婚 / 安定マッチング / 安定割当

【研究成果の概要】

学生の学科への配属や研修医の病院への配属の決定という離散資源配分問題は実用性の高い重要な問題である．グラフ構造や離散凸解析などの離散構造を導入し，安定マッチングモデルを一般化して適用範囲の広い離散資源配分問題を構築し，その解析を行うことを目的とした．
包括的な離散資源配分問題に対する戦略的頑健性をもつメカニズムの構築，安定マッチングモデル（2部グラフ上のモデル）の一般の有向グラフへの拡張等の研究を実施し，雑誌論文6編，投稿中の論文2編，執筆中論文2編の成果を得た．

【研究種目】基盤研究(B)

【研究期間】2012-04-01 - 2017-03-31

【配分額】5,850千円 (直接経費: 4,500千円、間接経費: 1,350千円)

【研究分野】計算機システム・ネットワーク

【研究領域課題番号】23240005 (KAKENデータベースで見る）

【研究キーワード】

自動チューニング / 性能モデリング / 逐次実験計画 / 自動チューニング記述言語 / コンパイラ技術 / 軽量化 / 行列計算 / 大規模探索 / ハイパフォーマンスコンピューティング / コンパイラ / ミドルウェア / アルゴリズム / 性能相関 / 探索アルゴリズム / 実験計画 / 最適化コンパイラ / 性能評価 / 線形計算 / 離散最適化 / バイオインフォマティクス

【研究成果の概要】

自動チューニング（AT）を汎用的技術として確立することをめざし、以下の４領域にて研究を行った。数理領域では、AT数理コアライブラリATMathCoreLibを開発・公開、また性能相関を扱う数理手法を開発した。プログラミング領域では、上記ライブラリをAT記述言語ppOpen-ATに組込み、またコード配置の偶発性による性能変化を打ち消す手法を提案。システム領域では汎用的Auto-Tunerの構成法提示、また性能情報取得を軽量化した。アプリケーション領域では行列計算・大規模探索のAT、上記ライブラリのアプリに適用した。このように4領域を連携しつつ集中的に研究、ATの汎用技術化に向けて成果を挙げた。

【研究種目】基盤研究(A)

【研究期間】2011-04-01 - 2015-03-31

【配分額】40,950千円 (直接経費: 31,500千円、間接経費: 9,450千円)

【研究分野】数学一般(含確率論・統計数学)

【研究領域課題番号】21740060 (KAKENデータベースで見る）

【研究キーワード】

離散最適化 / 組合せ最適化 / 数理計画 / 離散凸関数 / 近似アルゴリズム / アルゴリズム / マトロイド / 劣モジュラ関数 / マトロスド

【研究成果の概要】

本研究では, 申請者が近年携わってきた離散凸解析の理論に基づき, 計算時間や解の精度の面で理論的な保証をもつアルゴリズムを構築することを目的とした. 3年間の間に様々な結果を得ることが出来たが, とくに, 複数のナップサック制約の下でのM凹関数の最大化問題に対して, 多項式時間近似スキームを構築することに成功した. また, 近傍システムという, 一般的な解集合の構造を明らかにするとともに, 近傍システムに関する分離凸最適化問題が多項式時間で解けることを示した.

【研究種目】若手研究(B)

【研究期間】2009 - 2011

【配分額】4,420千円 (直接経費: 3,400千円、間接経費: 1,020千円)

【研究分野】工学基礎

【研究領域課題番号】21360045 (KAKENデータベースで見る）

【研究キーワード】

離散最適化 / 凸関数 / 双対性 / 劣モジュラ関数 / マトロイド / 数理工学 / 最適化 / アルゴリズム

【研究成果の概要】

工学や社会科学の諸分野における最適化の理論と応用を「離散凸パラダイム」に よって統合する研究を行った．離散凸解析の理論と応用を， 連続・離散軸，凸・非凸軸，分野横断軸，の３つの観点から整理することによって，個々の数 理的技法や応用諸問題の相互関係を明確にし，数理の深化，応用の開拓，ソフト ウェアの整備の３つの観点から研究を行い，新たな展開を達成した．とくに，数理の深化については，Ｌ凸関数最小化アルゴリズムの詳細な解析やＤＣ計画の枠組みの提示などの成果をあげた．

【研究種目】基盤研究(B)

【研究期間】2009-04-01 - 2015-03-31

【配分額】17,810千円 (直接経費: 13,700千円、間接経費: 4,110千円)

【研究分野】社会システム工学・安全システム

【研究領域課題番号】20310088 (KAKENデータベースで見る）

【研究キーワード】

OR / 離散最適化 / アルゴリズム / 劣モジュラ関数 / 組合せ最適化 / 数理計画 / 細合せ最滴化

【研究成果の概要】

大規模離散最適化問題の有する劣モジュラ的な離散構造に注目し, 効率的なアルゴリズムの構築のために有効な離散構造を研究した.個別には,ネットワーク・フロー, マッチング,多品種フロー, 施設配置問題, 資源配分問題, グラフ連結度,通信網設計,待ち行列ネットワークに関わる離散構造,双対貪欲アルゴリズムに関わる離散構造(双対貪欲多面体, ゾノトープ) ,ホーン論理関数や安定マッチングの離散凸構造,などであり,個別の劣モジュラ的な離散構造の解明に基づき,それらの知見を横断的に総合する基礎理論の構築と高速アルゴリズムの開発を行った.

【研究種目】基盤研究(B)

【研究期間】2008 - 2012

【配分額】19,630千円 (直接経費: 15,100千円、間接経費: 4,530千円)

【研究分野】工学基礎

【研究領域課題番号】20560057 (KAKENデータベースで見る）

【研究キーワード】

微分代数方程式 / 行列束 / 離散最適化 / 非線形回路 / 混合解析 / アルゴリズム / 数値計算 / モデル化

【研究成果の概要】

集積回路や化学プラントに代表される大規模動的システムは,微分演算子と代数方程式が混在した微分代数方程式(DAE)によって自然に記述される.しかし,微分代数方程式の数値解析においては,常微分方程式の場合と比較して,初期値の設定や安定性の保証が著しく困難となる.本研究課題では,回路の過渡現象をモデル化する微分代数方程式の導出において,数値的に最も解き易いものを効率的に見出す手法を開発した

【研究種目】基盤研究(C)

【研究期間】2008 - 2010

【配分額】4,160千円 (直接経費: 3,200千円、間接経費: 960千円)

【研究分野】社会システム工学・安全システム

【研究領域課題番号】16310111 (KAKENデータベースで見る）

【研究キーワード】

離散最適化 / アルゴリズム / 劣モジュラ関数 / 組合せ最適化 / 数理計画

【研究成果の概要】

平成16年度〜19年度に亘る本研究において,劣モジュラ的な新しい構造の発見,知見及び新しい効率的なアルゴリズムの開発などの多くの成果が得られた.主要な成果としては,以下のものが挙げられる.
1.離散凹関数と上下限付き手付を導入することにより,安定結婚モデルや割当モデルの統一モデルを提案し,さらにはこのモデルが常に安定な解を持つことを構成的に示した.この統一モデルは既存の多くのモデルを包含するものであり,既存のモデルの有する離散構造の本質を明らかにした.
2.木構造ネットワークにおける動的フローと施設配置問題を複合した1-センター問題の動的フロー版として考えられる問題に対して,動的に構造変更が可能な平衡2分木である区間木を用いた高速アルゴリズムを導出した.
3.劣モジュラ関数を一般化した双劣モジュラ関数を最小化する多項式時間アルゴリズムを求め,さらに,その強多項式時間アルゴリズムを初めて構築した.
4.木構造ネットワークに対する単調なmin-max型連結分割問題の初めての多項式時間アルゴリズムを開発した.また,単調でない場合のmin-max型連結分割問題,min-sum型連結分割問題は,NP困難であることを示した.
5.グラフ上の半教師付き学習のための学習機械「電気回路判別器」を提案した.この判別器は非線形電気回路理論に基づいて構成され,データセットを電位の符号によって分類するものである.
6.ネットワーク設計問題として広く研究されているソース配置問題や外部ネットワーク問題などの自然な拡張として最小横断問題を考察し,ある種の劣モジュラ的な条件の下での最小横断問題に対する多項式時間アルゴリズムを開発した.また,このアルゴリズムを用いることで無向ネットワークにおける外部ネットワーク問題も効率的に解けることを示した.

【研究種目】基盤研究(B)

【研究期間】2004 - 2007

【配分額】16,320千円 (直接経費: 15,600千円、間接経費: 720千円)

【研究分野】工学基礎

【研究領域課題番号】15360043 (KAKENデータベースで見る）

【研究キーワード】

凸解析 / 凸関数 / 凸集合 / マトロイド / 離散最適化 / 数理計画 / 非線形計画 / ネットワークフロー / 双対性 / 劣モジュラ関数 / アルゴリズム / 離散凸関数 / 組合せ最適化

【研究成果の概要】

本研究課題の目的は,経済学,システム工学,オペレーションズ・リサーチ,最適化理論,アルゴリズム理論などの広汎な分野における基礎的諸問題に関わる離散構造を,離散凸性という横断的視点から整理し,「離散凸」という新しいパラダイムを確立することにある.本研究課題では下記に挙げた研究成果を得ることが出来た.いずれの研究成果も査読つき国際会議や学術雑誌に採択されている.
(1)離散双対性に関わる最適化問題,とくに,M凸関数を目的関数に含む劣モジュラ流問題に対して,容量スケーリング手法に基づくアルゴリズムを提案した.一般のM凸劣モジュラ流問題に対して,このアルゴリズムはこれまでで最良の時間計算量をもつ.
(2)離散凸解析の枠組みとは独立に研究されてきたマルチモジュラー性という概念が,実質的にL凸性と等価な概念であることを示した.この結果をふまえ,整数格子点上で定義されたマルチモジュラー関数に対する離散分離定理などの諸性質を導いた.
(3)2次のM凸関数と木距離の間の密接な関係を示した.より具体的には,2次のM凸関数のヘッセ行列は実質的に木距離行列(にマイナスを掛けたもの)であることを証明した.
(4)整凸集合上の離散不動点定理を与えた.これは,数理経済学における一般均衡理論ならびに非協力ゲームへの応用をもつ.
(5)M凸関数の概念が,数理経済学で良く知られた粗代替性や単改良性と等価であることを明らかにした.
(6)離散凸解析の数理経済学への応用として,複数の不可分財と貨幣からなる市場において競争均衡が存在するための条件を与えるなどの理論構築を行うとともに,競争均衡を求めるアルゴリズムをM凸劣モジュラ流問題の枠組みを利用して開発した.

【研究種目】基盤研究(B)

【研究期間】2003 - 2005

【配分額】10,200千円 (直接経費: 10,200千円)

【研究分野】工学基礎

【研究領域課題番号】14750047 (KAKENデータベースで見る）

【研究キーワード】

クラスタリング / 離散最適化 / アルゴリズム / 多変量解析 / 劣モジュラ関数 / 相関行列 / 情報量規準 / 因子分析 / 相関分析

【研究成果の概要】

本研究課題は,離散最適化の最新の成果を応用して,多変量データの新たな統計的解析手法を確立することを目的としている.多変量データの統計的解析に当たっては各変量を,相関行列に基づいて比較的少数のグループに分類することが重要なステップとなる.しかし,因子分析に代表される従来からの手法は,変量の線形結合を用いており,問題点が少なくない.本研究課題は,変量の線形結合を経由せずに,相関行列の半正定値対称性とその離散構造を積極的に利用した手法の開発を目的としている.
この目的を達成するために,最大対数尤度を基準として対称劣モジュラ関数最小化を用いる手法や,情報量規準の観点から最適な分割を局所近傍探索によって求める手法を開発し,計算機上で実現した.さらに,各種の人工データ及び実データに適用して,計算時間や分割精度の観点から手法の比較検討を行った.最大対数尤度を基準とする方法は,効率的な厳密解法を用いることができるという利点の反面,クラスタリングの鎖効果と呼ばれる現象が頻繁におこるという致命的な欠点があることが明らかになった.一方,AICやBICなどの情報量規準の最適化は,効率的な厳密解法を得ることが難しく,局所近傍探索を用いた手法を設計せざるを得ない.しかし,計算機実験の結果,多くのテストデータに対して,合理的な分割を安定して提示することが確認され,実際上有望な手法であるとの結論を得た.

【研究種目】若手研究(B)

【研究期間】2002 - 2004

【配分額】2,100千円 (直接経費: 2,100千円)

【研究分野】社会システム工学

【研究領域課題番号】13480113 (KAKENデータベースで見る）

【研究キーワード】

アルゴリズム / 離散最適化 / 組合せ最適化 / 劣モジュラ関数 / 大規模システム

【研究成果の概要】

社会システムや産業活動に関係して現れる生産計画,環境計画,最適配送計画,スケジューリング,最適投資などを始めとする重要な問題の多くは,大規模かつ離散構造を有するシステムの最適化問題として捉えられる.本研究では,離散最適化問題の有用な構造的性質の抽出,および,その性質に基づいた高速アルゴリズム開発に主眼をおき,最適化分野における基礎理論の構築を試み,研究に取り組んだ.活発な研究活動の結果,新しい離散構造の発見や新しい効率的なアルゴリズムの開発などの多くの成果を得た.主要な成果としては,以下のものが挙げられる.
1.ネットワークのカット関数の劣モジーラ性に基づき,フロー要求条件を満足する供給施設の最適配置問題の効率的アルゴリズムを示した.
2.新しい最大2部マッチングアルゴリズム及び最大隣接順序に基づく新しい最大フローアルゴリズムを提案した.
3.劣モジュラ関数最小化のためのメンバシップ・オラクルに基づく0(n^2)アルゴリズムを提案し,劣モジュラ関数最小化問題への新しいアプローチを示した.
4.経済学における祖代替性と離散凹性の等価性を明らかにし,離散凹効用関数を用いてGale-Shapleyの安定マッチングの概念を拡張し,その安定解の存在を構成的に示した。
5.劣モジュラ構造の基本である基多面体の概念を一般化した複基多面体の概念を創出し,劣モジュラ構造の新しい枠組みを提示した.
6.単調線形システムの極小整数解を列挙する逐次擬多項式時間アルゴリズムを示した.
7.極大頻出集合の列挙が計算量的に難しいこと,ならびに,極小非頻出集合列挙が多項式時間で可能であることを示した.
8.ホーン理論とqホーン理論に対する関数従属性が効率よく求められることを示した.
9.単調論理関数の非双対性判定がo(log n)の推定ビットで可能であることを示した.また,様々な部分クラスの双対化問題を多項式時間で解くことが可能であることを示した.
10.データ解析手法として,データの本質を表す属性集合を求めるアルゴリズムを提案した.また,不完全なデータを説明する問題への拡張に対して,不完全性の度合いを考慮した4つの拡張を提案し,構造的性質,ならびに,計算量的性質を明らかにした.

【研究種目】基盤研究(B)

【研究期間】2001 - 2003

【配分額】7,200千円 (直接経費: 7,200千円)

【研究分野】工学基礎

【研究領域課題番号】12450040 (KAKENデータベースで見る）

【研究キーワード】

凸解析 / 凸関数 / 凸集合 / マトロイド / 離散最適化 / 数理計画 / 非線形計画 / ネットワークフロー / 離散凸解析 / 数理経済学 / 不可分財市場 / 競争均衡 / M凸関数最小化 / アルゴリズム

【研究成果の概要】

本研究課題の主題,研究代表者が1990年代の中頃から提唱している離散凸解析の応用開拓である.本研究課題では下記に挙げた研究成果を得ることが出来た.いずれの研究成果も査読つき国際会議や学術雑誌に採択されている.
(1)数理経済学において,離散凸解析の応用研究として3つの成果を上げた.第1の成果は,複数の不可分財と貨幣からなる市場において競争均衡が存在するための十分条件を与えるなど,理論構築を行なった.第2の成果は,離散凸解析のおいて中心的役割をなすM凸関数の新しい特徴付けを与えた.この特徴付けは,数理経済学では良く知られた粗代替性や単改良性を用いたものである.第3の成果は,先に述べた不可分財と貨幣からなる市場において,競争均衡を求めるアルゴリズムの開発である.このアルゴリズムは,離散凸解析における最適化問題の一つであるM凸劣モジュラ流問題を利用したもので,多項式時間で均衡の存在判定を行ない,均衡が存在する場合はその一つを求める.
(2)離散凸解析において中心的な役割を果たすM凸関数の最小化問題に対する近接定理を示すとともに,高速なアルゴリズムを開発した.
(3)工学システムのもつ組合せ構造を離散凸解析の立場から論じた.特に,電気回路や制御システムの取扱いを目的として,混合多項式行列を考察し,効率的な組合せ緩和アルゴリズムを提案した.
(4)オペレーションズ・リサーチの諸問題に対し,離散凸解析の結果を利用した解法が適用可能か否かを検証した.その結果を踏まえて,ネットワークデザインや最大カット問題に対して効率的な解法を提案した.

【研究種目】基盤研究(B)

【研究期間】2000 - 2002

【配分額】7,600千円 (直接経費: 7,600千円)

【研究分野】数学一般(含確率論・統計数学)

【研究領域課題番号】11640105 (KAKENデータベースで見る）

【研究キーワード】

グラフ論 / 離散最適化 / アルゴリズム / 計算幾何 / 離散幾何 / 組み合せ幾何 / 組合せ論 / 極値グラフ理論 / 組み合わせ幾何 / 組み合わせ論 / 位相幾何的グラフ論 / 位相幾何学的グラフ論

【研究成果の概要】

グラフ論、離散最適化、計算幾何学の諸分野に渡る本研究の研究成果の概要を以下に示す。
計算幾何学の分野の直線成分の抽出問題では従来用いられてきたハフ変換の性能の限界を理論的に示し,理論的に最適な方法を提案した。画像の等高線表現では、整数格子の性質を研究し、グラフ論、離散最適化を適用した問題解決法を提案した。ディジタルハーフトーニングを数学的最適化問題として定義し,ある種の測度を基礎にした実数要素行列の整数要素行列への変換法を導入することにより、ある制約のもとで効率よく実行できるアルゴリズムの開発に成功した。
離散最適化の分野では有向グラフの一般化として双向グラフを定義し、双向グラフ上で安定集合問題の一般化を定式化した。クローフリーグラフの最大重み独立集合を求めるMintyのアルゴリズムの訂正版を提案した。離散凸解析における重要な基本問題の一つであるM-凸関数の最小化問題に対する新しい多項式時間アルゴリズムを提案した。
グラフの距離構造についてはk-辺ワイド直径はグラフの直径のk次式のオーダーであることを示した。グクフの連結度については先行の結果を含むk-可縮辺の存在を保証するより一般的な禁止部分グラフ条件を示した。5-可縮臨界グラフでは少なくともその1/5の頂点が次数5であること、6-可縮臨界グラフでは少なくともその1/7の頂点が次数6であることを示した。与えられた任意のグラフをその誘導部分グラフに含む5-可縮臨界グラフの存在を示した。
極値グラフ理論の分野では新しい擬確率的手法を開発して当該分野の基本定理であるErdos-Stoneの拡張、Bollobas-Kohayakawa予想を肯定的に解決した。グラフを同型な部分グラフで敷き詰めることができるための次数条件を述べたAlon-Yusterの定理を必ずしも同型でない部分グラフの場合に拡張し、長年未解決であったEl-Zahar予想など多くの定理、予想を近似的に含む一般的な結果を得た。

【研究種目】基盤研究(C)

【研究期間】1999 - 2001

【配分額】3,500千円 (直接経費: 3,500千円)

【研究分野】数学一般(含確率論・統計数学)

【研究領域課題番号】09874046 (KAKENデータベースで見る）

【研究キーワード】

離散最適化 / 凸解析 / マトロイド / アルゴリズム / 双対定理

【研究成果の概要】

マトロイドの公理を拡張することにより,整数格子点上で定義された整数値をとる関数に対して離散凸関数とでも呼ぶべき概念が得られることが,本研究の開始時に明らかになっていた.連続世界の凸解析におけるルジャンドル変換の離散版を導入することによって,整数格子点上で定義された整数値関数に対して共役関数の概念が定義され,これによって,離散凸関数はM凸性,L凸性といういわば表と裏(数理計画の用語ではprimalとdual)の姿をもつ,M凸性は交換公理の拡張により,また,L凸性は劣モジュラ性の拡張により特徴付けられる.本研究では,以下の結果を得た.
1.L凸集合の多面体的な特徴付けを与えた.とくに,L凸集合が三角不等式を満たす距離関数と同等であることを示した.これは,M凸集合が劣モジュラ不等式を満たす集合関数と同等であるという(既知の)事実に対応する結果である.
M凸関数の実効定義域は基多面体であるが,これを,一般化ポリマトロイドの場合に定式化し直したものはM^〓凸関数と呼ばれる(M凸関数の射影がM^〓凸関数である).これに共役な操作(制限)をL凸関数に施したものをL^〓凸関数と名付け,その性質を調べた.これによって,従来の関連研究との関係が明らかとなった.とくに,L^〓凸関数がFavati-Tardellaによる整凸関数に一致すること,離散中点凸性により特徴付けられることを示した.
3.M凸関数,L凸関数に関する離散双対定理の原証明は,M凸関数に対して構成的に最適双対変数を与え,L凸関数に対してはその共役をとるという形であった.本研究では,M凸関数とL凸関数に関して,独立に多面体的な別証明を見いだした.その結果,整多面体と離散凸関数の関係が明確になった.

【研究種目】萌芽的研究

【研究期間】1997

【配分額】1,000千円 (直接経費: 1,000千円)