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

【研究キーワード】

組合せ最適化 / アルゴリズム / オンライン最適化 / 離散構造

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

【研究期間】2021-04-01 - 2026-03-31

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

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

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

【研究キーワード】

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

【研究成果の概要】

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

【研究の社会的意義】

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

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

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

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

【研究分野】知能情報学

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

【研究キーワード】

離散構造 / アルゴリズム / 論理関数 / 組合せ集合 / 大規模データ処理 / グラフ理論 / 最適化 / 列挙 / 離散構造処理系 / 二分決定グラフ / 列挙アルゴリズム / ZDD / データ構造 / 演算処理系 / 索引化 / BDD / グラフアルゴリズム / 網羅的解析

【研究成果の概要】

研究課題

【研究の社会的意義】

論理関数や組合せ集合などの離散構造を表す大規模データを計算機上にコンパクトに表現し演算処理を効率よく行う技法は，システム設計，データマイニング，遺伝子解析，web 解析等，計算機科学の様々な応用分野に共通する基盤技術として非常に重要であり，現代社会に対する大きな波及効果を持つ．本研究成果は社会を支える基盤技術として，今後も活用され続ける．

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

【研究期間】2015-05-29 - 2020-03-31

【配分額】134,420千円 (直接経費: 103,400千円、間接経費: 31,020千円)

【研究分野】情報学基礎

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

【研究キーワード】

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

【研究成果の概要】

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

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

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

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

【研究分野】情報工学

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

【研究キーワード】

アルゴリズム / 並列処理 / 組合せ問題 / 離散構造 / 計算幾何学 / ネットワ-ク / 分散処理

【研究成果の概要】

初年度には離散構造を処理するアルゴリズムについて種々の観点から調査・検討を行った.これにより現在のアルゴリズムの限界や新しいアルゴリズム論に関する知見を得るに至った.特に並列・分散アルゴリズムに関して現状の調査・検討が行われ,新しいアルゴリズムの設計のための土台が築かれた.さらに,最終年度には,前年において得られた研究成果を土台として,総合的見地から種々の新しいアルゴリズムを設計解析した.現在から将来に向け有用となる近似・確率・並列・分散・ハ-ドウェアアルゴリズムに関する新しい知見を得るに至った.さらに計算理論に関する成果も種々得られた.代表的な成果を以下に示す.
1.VLSIのレイアウト設計における重要な問題に一つに回路分割問題があり,これまでに様々なアルゴリズムが提案されてきている.本研究では回路を構成するモジュ-ルの集合とネットリストが与えられたとき,モジュ-ル集合を2分割して左右の部分の面積をほぼ等しくし,かつ両方の部分に跨る配線の本数を最小にする問題に関するアルゴリズムを与えた.グラフの表現に基づいた方法と平面上の点集合に写像した上で点集合の2分割問題を解く方法を比較した.この結果はアルゴリズムを構成するときにグラフモデルと幾何モデルのいずれを用いるかを決定するために有用である.
2.NP完全問題などの複雑さの高い問題に対して,平均時間的には効率良く解くと主張されるアルゴリズムが数多く開発されている.それらの評価は通常解析的になされるが,実際的立場の研究者からは,実際に計算機実験によっても行われるべきだとの指摘がある.本研究では充足可能性問題に対するこのようなアルゴリズムの評価に用いるべき例題生成はいかにあるべきかについて調査・検討した.さらに,その要求を満足するような例題生成アルゴリズムが存在することを示した.

【研究種目】総合研究(A)

【研究期間】1990 - 1991

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