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

【研究キーワード】

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

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

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

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

【研究分野】数理情報学

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

【研究キーワード】

オンラインマッチング / 線形相補性問題 / 公平割当 / 線形計画問題 / アルゴリズム / ロバスト最適化 / マトロイド / 組合せ最適化

【研究成果の概要】

本研究の目的は，組合せ的制約をもつ線形システムを解くアルゴリズムの構築と理論解析である．2021年度は，研究課題に関連して，オンラインタスク割当問題にも取り組んだ．ライドシェアやクラウドソーシングといった状況では，乗客やタスクが逐次的に現れ，アルゴリズムはこれらを運転手や労働者に逐次的に割り当てることにより利益を得る．このような問題はオンラインマッチングとして捉えることができる．近年，上記のような現実的な状況を動機としたオンラインマッチングの研究が盛んに行われている．現実には，(1) 労働者が割り当てられた仕事を終えたら次の仕事を受け入れ可能であり，(2) 労働者が割り当てられた仕事を確率的に断ることがあり，さらに(3) ひとつのタスクを複数の労働者に割り当てられることがある．本研究はこれらの設定を考慮したオンラインタスク割当問題のアルゴリズムを提案した．アルゴリズムの結果の良さは「情報を事前に知っていれば達成可能な最大利益」との比較で評価することが一般的である（競合比解析）．本研究は提案アルゴリズムがある条件下では理論的に最適であることを示した．さらに，提案アルゴリズムは関連研究の設定にも適用可能であり，既存アルゴリズムよりも良い性能をもつことも示した．この成果は国際会議AAAI-22で発表済みである．
他にも，これまでも着目してきたマトロイド制約に関係する公平割当問題の研究も行い，その成果は国際会議で発表済みである．

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

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

【配分額】3,770千円 (直接経費: 2,900千円、間接経費: 870千円)

【研究分野】数理情報学

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

【研究キーワード】

組合せ最適化 / アルゴリズム / ストリーミングアルゴリズム / 劣モジュラ関数 / マトロイド / マッチング / 近似アルゴリズム / コミュニティ検出 / ストリーミング計算 / 数理工学 / 情報基礎 / 数理モデル

【研究成果の概要】

本年度は，昨年度に引き続き，大規模なネットワークを解析するための基本的な問題のひとつである，制約付き劣モジュラ関数最大化問題を扱い，この問題に対するストリーミングアルゴリズムの計算複雑度の解析に取り組んだ．昨年度に，制約付き劣モジュラ関数最大化問題に対する近似不可能性と空間複雑度との関係の解明に取り組み，入力データがストリームとして与えられメモリが制限されている状況において，0.585近似よりよい近似比を達成するアルゴリズムが存在しないことを示した．この成果は，本年度に論文改訂を経て査読付き論文誌SIAM Journal on Discrete Mathematicsに採択された．また，組合せ最適化における基本的な概念であるマトロイドに関連して，買い手が動的に市場にやってくる組合せ市場での価格付け問題に取り組み，昨年度に得た成果を改善したものが査読付き論文誌SIAM Journal on Discrete Mathematicsに掲載された．さらに，二部マッチングマーケットにおいて，エージェントが確率過程にもとづき出入りする場合に，貪欲アルゴリズムなど基本的なアルゴリズムの漸近的性能と各エージェントの待ち時間との関係を解明した．この成果は，ウェブとインターネット経済に関する査読付き国際会議The 17th Conference on Web and Internet Economics(WINE)に採択された．

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

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

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

【研究分野】数理情報学

【研究領域課題番号】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千円)

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

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

【研究キーワード】

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

【研究成果の概要】

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

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

【研究期間】2009 - 2011

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

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

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

【研究キーワード】

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

【研究成果の概要】

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

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

【研究期間】2008 - 2012

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

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

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

【研究キーワード】

ネットワーク理論 / アルゴリズム / 組合せ最適化 / 組合せ日適化

【研究成果の概要】

ネットワーク理論において横の広がりとなる基礎理論の構築と縦の広がりを作る実社会に適応したモデルの伸張を行い,基礎問題と拡張問題の両方に対して,アルゴリズム開発を行った.具体的には,修正可能性を考慮したネットワーク上の配置問題に対するアルゴリズム提案,通信ネットワークにおける耐故障性の指標開発,社会ネットワークにおけるコミュニティ抽出のハイパーグラフ上への拡張,グラフの向き付けに関する基本的性質やアルゴリズム開発などを行った.

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

【研究期間】2007 - 2009

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

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

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

【研究キーワード】

組合せ最適化 / 非線形関数 / 整数計画 / 離散凸関数 / 近似解法 / アルゴリズム / マトロイド / 劣モジュラ関数 / 非線形計画 / 凸解析 / 凸関数 / 離散凸解析

【研究成果の概要】

整数計画問題とは,与えられた制約条件を満たす整数ベクトルの中から,与えられた目的関数を最小化(または最大化)する解を求める問題である.一般に整数計画問題は短時間で解くことが困難である,ということが理論的にも現実的にも知られている.とくに,目的関数と条件が非線形関数で与えられる非線形整数計画問題は,解くことが最も困難な整数計画のクラスである.本研究では,様々な非線形整数計画問題に対して,その良質な近似解を短時間で求めるアルゴリズムを提案した.

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

【研究期間】2006 - 2008

【配分額】3,760千円 (直接経費: 3,400千円、間接経費: 360千円)

【研究分野】工学基礎

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

【研究キーワード】

行列束 / Kronecker標準形 / アルゴリズム / 組合せ緩和法 / 微分代数方程式 / 大規模システム / ロバスト計算 / 組合せ最適化 / 大規模疎行列

【研究成果の概要】

行列束のKronecker標準形は,微分代数方程式で記述される動的システムの解析において本質的な役割を果たしている.しかし,標準形の摂動に対する感度が非常に高く,計算誤差の発生しうる数値計算によって正確な標準形を得ることには困難を伴う.
本研究課題では,計算誤差が発生し得ない組合せ的計算を利用することによって数値計算の負担を減らして,できるだけ正確な標準形を安定に計算する手法を確立することを目的としている.従来の研究の結果,Kronecker標準形の構造指数のうち,冪零指数に関して,2部グラフ上の最大重みマッチングを利用した組合せ緩和法が確立されている.本研究課題は,組合せ緩和法に基づいて行指数・列指数を計算するアルゴリズムの設計と計算機上での実現を目的としている.
昨年度までの研究成果より,周期的な構造を有する2部グラフ上の最大マッチングを計算することによって,行指数・列指数の推定値が得られることが明らかとなった.
本年度は,引き続き,組合せ緩和法の設計に取り組み,世界標準的なソフトであるGUPTRIで採用されているアルゴリズムよりも効率的な新たなアルゴリズムを得た.しかし,計算精度に関しては,GUPTRIの方が優れているため,現時点では,組合せ的な推定値とGUPTRIとを併用するのが,最も適切な計算法であるとの結論に達した.
また,微分代数方程式の指数減少法への応用研究を行い,電気回路の数値解析手法として知られる混合解析の枠組みにおいて,最小指数を達成する微分代数方程式を導出する効率的なアルゴリズムを開発した.

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

【研究期間】2005 - 2007

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

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

【研究領域課題番号】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千円)

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

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

【研究キーワード】

応用数学 / 組合せ論 / アルゴリズム / 巡回セールスマン問題 / 計算量理論 / 組合せ最適化 / 計算幾何学 / 離散数学

【研究成果の概要】

巡回セールスマン問題(以下、TSP)とは与えられた複数の都市をすべて1回ずつ通り、出発点に戻ってくるような最短経路を見つける問題である。この問題はNP困難のクラスに属し、都市数が増えたとき実用的な時間(多項式時間)で最短経路(最適解)を求めるのは不可能と予想される代表例になっている。そこで、実社会での応用の観点から、実用的は時間で最適解に近い解を求める近似解法の研究がさかんに行われてきた。
TSPの近似解法を考える際、木は重要な概念の1つである。この木は、グラフ理論においてもさまざまな研究がなされている。例えば、与えられたグラフG_1,…,G_k,Hに対し、HがG_1,…,G_kを辺素に含むことができるかどうかを判定する問題はNP完全に属しており、一般にその判定は難しい。そこで、さまざまなグラフのクラスに関する十分条件について研究されてきた。この問題に対し、特にHを平面グラフにした場合どのようなグラフを辺素に含むことができるかに興味を持っている。今年度は2つの木の平面グラフへの埋め込みに関する研究を行った。
Garciaら(2002)は、2つのスターでない木はある平面グラフに辺素に埋め込むことができると予想した。同じ論文で、Garciaらは、スターでない木とパスはある平面グラフに辺素に埋め込めることを示している。予想の解決を目標に、より広い木のクラスについて考えた。まず、スターのいくつかの辺を1回細分して得られるグラフとスターでない木に、2つのキャタピラ、について榎本,太田,神田,枡井とともに示した。また、直径5以下のキャタピラとスターでない木に関して構成的に証明し、最終的にスターでないキャタピラとスターでない木について太田とともに示した。この証明方法が予想の解決の糸口にならないかを考察することが今後の課題である。

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

【研究期間】2003 - 2005

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

【研究分野】工学基礎

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

【研究キーワード】

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

【研究成果の概要】

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

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

【研究期間】2003 - 2005

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

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

【研究領域課題番号】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千円)

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

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

【研究キーワード】

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

【研究成果の概要】

本研究の目的は,組合せ凸解析の理論に基づいて,生産システム設計に現れる最適化問題の組合せ構造を明確にすると共に,最適な生産システムを設計するための実用的な解法を構築することである.この目的を実現するため,本年度は以下の研究を行った.
・スケーリング技法によるM凸関数最小化アルゴリズムの研究.M凸関数の最小化問題に対しては,最急降下法や領域縮小法が提案されているが,本研究においては,組合せ最適化のアルゴリズムにおいて基本的な技法であるスケーリング技法をM凸関数最小化に用いる可能性を研究した.一般にM凸関数はスケーリングに関して閉じていないが,ツリー型M凸関数や2次のM凸関数などのクラスのM凸関数がスケーリングに関して閉じていることを示すとともに,スケーリング技法と最急降下法とを組み合わせた効率的な算法を提案した.
・M凸関数の運搬経路問題への応用.時間枠制約つき運搬経路問題とは,各顧客への訪問時間枠制約をなるべく満たし,かつ運搬費用を最小にする経路及びスケジュールを求める問題である.経路決定とスケジューリングを分離するタイプのヒューリスティックにおいて,最適なスケジュールを求める問題がツリー型M凸関数の最小化問題として定式化できることを示した.
・2次のM凸関数・L凸関数の特徴付け.一般に2次の凸関数は半正定値対称行列で表現されるが,本研究では,どのような付加的条件がM凸性・L凸性を特徴づけかという問題意識をもち,この問題に対して完全な解答を与えた.その副産物として,確率過程論などで研究されてきたディリクレ形式との関連が明らかとなった.

【研究種目】萌芽的研究

【研究期間】1999 - 2000

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

【研究分野】工学基礎

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

【研究キーワード】

組合せ緩和法 / 行列ペンシル / システム解析 / 組合せ最適化 / アルゴリズム / 多項式行列

【研究成果の概要】

動的システムの解析や設計に重要な役割を果たす多項式行列の小行列式の最大次数を求める算法設計の新しい方法論として、代数的手法と組会せ的手法を融合した。『組合せ緩和法』が提唱されている。本研究では、組合せ緩和法の枠組みを尊重しつつ、多項式行列の変形に多くの記憶領域を要するという問題点を克服するために、動的システムの解析や設計に本質的な行列ペンシルに対象を限定した上で、定数行列による行列変換のみを用いた新しい組合せ緩和算法を開発した。この成果を、99年1月にボルチモアで開かれた第10回ACM/SIAM離散アルゴリズム会議で発表した。
行列ペンシルの小行列式の最大次数は、Kronecker標準形の構造指数と密接な関係がある。行列のKronecker標準形を求めるアルゴリズムとしては、従来、反復法を中心とした研究が行われてきたが、本研究を通じて、消去法を基礎とした直接法によって構造指数を求められることが明らかとなった。
組合せ緩和法は、優れて斬新な方法論であるが、未だ実用的なレベルに達してはいない。その原因としては、算法の正当性を理解するために、数値計算の専門家やシステムの解析や設計に携わる技術者に馴染みの薄い、組合せ最適化のかなり高度な議論を必要としていることが挙げられる。この問題点は、使い勝手のよい信頼できるソフトウェアを提供することによって解消されるであろう。
また、行列の組合せ論的な側面を抽象化したマトロイドと不可分の関係にある劣モジュラ関数に関して、多項式時間で最小値を求める組合せ的なアルゴリズムを開発した。

【研究種目】奨励研究(A)

【研究期間】1998 - 1999

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

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

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

【研究キーワード】

組合せ最適化 / アルゴリズム / グラフ理論 / 双向グラフ / クローフリーグラフ / 安定集合問題 / 多項式時間アルゴリズム

【研究成果の概要】

「双向グラフに対する最適化問題とその解法の研究」という目的で昨年度に引き続き本年度は研究を進めて来た。
昨年度の研究成果“The generalized stable set problem for claw-free bidirected graphs"について、1998年の6月に開催された国際会議Integer Programming and Combinatorial Optimization(査読付き)にて口頭発表を行った。その際の旅費として本年度の研究費を用いた。また本論文はこの会議のプロシーディングスに掲載された。
本年度の研究成果は“A linear time algorthm for the generalized stable set problem on triangulated bidirected graphs"としてまとめ、Journal of the Operations Research Society of Japanに投稿し、1999年3月17〜19日に京都大学で開催されるJapan-Hungarian Symposium on Discrete Mathematics and Its Applicationsにて口頭発表する。また、この成果については来年度開催される国内外の学術会議、研究会においても口頭発表を行う予定である。この成果は本年度計画していた「一般の双向グラフについて一般化安定集合問題に対する効率的な解放の開発」を含むものである。もう一つの計画「平面上の与えられた点集合の最小重み三角形分割問題へのこの解法の応用」については現在研究中でありまだ成果を得るに至っていない。
また開発した解法については、当研究費によって購入した計算機を用いてその実用面での有効性の検証も行った。

【研究種目】奨励研究(A)

【研究期間】1997 - 1998

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

【研究分野】工学基礎

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

【研究キーワード】

マトロイド / 線型回路 / アルゴリズム / 分解 / 組合せ最適化 / 劣モジュラ関数

【研究成果の概要】

線型マトロイド・マッチングは,ジャイレータ抵抗回路網の構造可解性判定に応用されている.しかし,実際問題としては,構造的に可解であることを保証するばかりでなく,数値誤差の影響を受けない組合せ的な情報に基づいて,数値計算の合理的な解法手順を示すことが望まれる.
本研究では,線型マトロイド・マッチングの分解原理を確立し,分解を求める効率的な算法を与えることによって,この問題を解決した.
さらに,海外との共同研究によって,線型マトロイド・マッチングの一般化である線型デルタマトロイド・パリティ問題に関する最大最小定理と効率的な多項式時間算法を導いた.その結果,線型マトロイド・マッチング問題が効率的に解ける仕組みについても理解が深まった.

【研究種目】奨励研究(A)

【研究期間】1996

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