Discovery Sagaサイレントキーワード俯瞰

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

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

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

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

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

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

ニュ-ラルネットワ-ク / グラフ / クリ-ク / ボルツマン機械 / 確率化アルゴリズム / Nークィ-ン問題 / 近似アルゴリズム / アルゴリズム / nークィ-ン問題

1.逐次探索方式によって出来る限り最大に近いクリ-クを抽出するため、いくつかのヒュ-リスティックな方法を考察・組合せ、節点数の3乗オ-ダ時間計算量の近似アルゴリズムを開発し、解精度・実行速度について良好な結果を得た。
2.Boltzmann機械の概念を基礎として、局所最適解から容易に脱出し易いエネルギ-関数を考案し、逐次より最大に近いクリ-クを抽出結果として出してゆく確率アルゴリズムを提案した。更に、それに対していくつかの改良・変形版を考案した。先ず、このアルゴリズムは、前記1のアルゴリズムと同程度の実行時間をかけた場合には、前記によるのと同等あるいはそれ以上の解精度を得た。更に、解探索の反復を行うことにより、時間計算量の多項式オ-ダ性を保ったまま、この解精度を逐次改善してゆけることを確認した。
一方、確率処理を除いた決定性アルゴリズムも開発し、さほど解精度を低下させることなく、実行時間を前記確率アルゴリズムの1/10以下にすることに成功した。更に、前記確率アルゴリズムを組み合せることにより、解精度・実行時間共に優れたアルゴリズムを確立し、その有効性を大量の計算機実験により実証した。
また、対象グラフが刻々時間的に変動する場合にも、前記アルゴリズムは単純な変更により容易に対応可能となることを明らかにし、実験的にその有効性を確認した。
3.nーqueen問題に対して前記2の方法を適用することにより、従来のシミュレ-テッドアニ-リングを用いる方法による場合に比べて2桁〜3桁以上高速に解を求めることができることを実験的に明らかにした。

【研究分担者】
横森貴	電気通信大学	電気通信学部	助教授	(Kakenデータベース)
武田光夫	電気通信大学	電気通信学部	教授	(Kakenデータベース)
高橋治久	電気通信大学	電気通信学部	助教授	(Kakenデータベース)