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

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

【研究キーワード】

エルゴード理論 / 連分数 / ユークリッドアルゴリズム / 一様分布論 / アルゴリズム / 国際研究者交流 / イスラエル、フランス、韓国 / 多国籍 / 国際情報交換 / イタリア：イギリス / イスラエル:フランス:オランダ:韓国:ポーランド

【研究成果の概要】

エルゴード理論の研究はその初期から現在に至るまで数論の研究と密接な関わり合いを持ってきた。とりわけ、実数の2進あるいは10進展開や連分数展開の研究は依然として多くの未解決な問題があり、また一方で情報科学における暗号理論、通信理論などからの要請による新しい研究課題も多く存在する。本研究では連分数展開などの収束、近似の問題あるいはユークリッドアルゴリズムの計算コストの評価を確率論的に取扱い、新たな知見を得ることができた。また、一様分布論など関連する周辺分野についてもいくつかの新しい結果を得た。

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

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

【配分額】17,290千円 (直接経費: 13,300千円、間接経費: 3,990千円)

【研究分野】情報学基礎

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

【研究キーワード】

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

【研究成果の概要】

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

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

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

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

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

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

【研究キーワード】

組合せ論 / 離散数学 / アルゴリズム論 / 巡回セールスマン問題 / 計算量理論 / アルゴリズム / 国際研究者交流 / アメリカ : イギリス / 車両配送問題 / 多項式時間アルゴリズム / 国際情報交換 / ニュージーランド

【研究成果の概要】

巡回セールスマン問題は与えられた複数の都市をすべて1回ずつ通り、出発点に戻ってくるような最短経路を見つける問題である。この問題は板の穴あけなど実社会の問題にも直結する有名な最適化問題の1つである。しかし、都市数が増えるにつれ、コンピュータを利用しても計算にかる時間が指数的に増大する。そこで、問題がどのような条件をみたしていれば、実用的な時間で解が得られるかという研究がなされてきた。研究では、この効率よく解ける状況を考察するとともに、巡回セールスマン問題におけるこれらの条件を車両配送問題に適用した場合に、最適がもつ構造を明らかにした。

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

【研究期間】2006 - 2008

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