【研究分野】数理情報学

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

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

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

【研究キーワード】

アルゴリズム / 固定パラメタ容易性 / 点モデル / Pottsモデル / Tutte多項式 / グラフ向き付け / 組合せ物理 / Iceモデル / 6点モデル / マトロイド / グラフ / アルゴリズム論 / マトロイドマイナー理論 / アルゴリズム理論

【研究成果の概要】

マトロイドの分解理論とTutte多項式理論の研究を組合せ物理と融合し、計算論的組合せ物理という面からの研究を行った。Iceモデルとその拡張の6点モデルに対して、carving幅に関するFPTアルゴリズム構成した。Pottsモデルで枝幅に関するFPTアルゴリズムも構成した。Tutte多項式に関するMerino-Welsh予想に関して、グラフの枝の向き付けに関する問題を計算解析してTutte予想の一部解決を行った。

【研究の社会的意義】

従来、数理物理において数学と物理の両面から研究されてきた組合せ物理において、計算解析を行うアルゴリズムの開発と、本研究グループメンバが構築した組合せ構造のデータベースを活用した解析を行うことによって、新たに計算論的組合せ物理という研究アプローチを示した。融合する諸分野の理論予想の一部解決も行え、アルゴリズム論からはFPTアルゴリズムの有用性を広げた。物理モデルの量子情報処理との関係を通した量子コンピュータへ研究を展開することが期待できる。

【研究種目】挑戦的萌芽研究

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

【配分額】3,380千円 (直接経費: 2,600千円、間接経費: 780千円)

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

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

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

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

【研究キーワード】

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

【研究成果の概要】

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

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

【研究期間】2006 - 2008

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

【研究分野】工学基礎

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

【研究キーワード】

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

【研究成果の概要】

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

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

【研究期間】2003 - 2005

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

【研究分野】工学基礎

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

【研究キーワード】

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

【研究成果の概要】

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

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

【研究期間】2000 - 2002

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

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

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

【研究分野】工学基礎

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

【研究キーワード】

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

【研究成果の概要】

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

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

【研究期間】1996

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