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

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