Theory and algorithms for combinatorial optimization under uncertainty

不确定性下的组合优化理论与算法

• 批准号: 21H03397
• 负责人: 垣村 尚徳
• 金额: $ 10.98万
• 依托单位: Keio University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (B)
• 财政年份: 2021
• 资助国家: 日本
• 起止时间: 2021-04-01 至 2026-03-31
• 项目状态: 未结题
• 来源: https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-21H03397/
• 关键词: 組合せ最適化; アルゴリズム; 離散構造; オンライン最適化; マッチング

本研究課題では，不確実性をもつ組合せ最適化モデルに対して，計算効率性や近似可能性を特徴付ける組合せ構造の解析を行なうことを目指す．期間初年度である今年度は，関連する文献や国際会議における研究動向の調査，および，海外の共同研究者との情報交換を行なった．そして，基本的な組合せ最適化問題であるマッチング問題について入力データの不確実性が計算効率性に与える影響を解析した．具体的には，二部グラフにおいて，頂点が確率的（ポアソン過程）に出入りする状況で最大マッチングを求める問題の解析に取り組んだ．このモデルでは，各頂点の滞在時間は指数分布にしたがうが，滞在中どの時点でマッチングを形成するかが，マッチングを求めるアルゴリズムの性能に関わる．本研究では，貪欲法など基本的なマッチングアルゴリズムを考えることで，各頂点の待ち時間とアルゴリズムの性能の関係を解析した．この成果は，マッチングマーケットの解析を動機としており，ウェブとインターネット経済に関する査読付き国際会議The 17th Conference on Web and Internet Economics(WINE2021)に採択された．また，この研究成果を中心に，2022年度には離散数学とその応用に関する日洪シンポジウムにおいて招待講演を行なった．そのほかにも，オンラインマッチング問題の拡張であるオンラインタスク割り当て問題に対するオンラインアルゴリズムの提案や，関連研究である組合せ遷移の研究成果を得た．

This research topic is to optimize the combination of uncertainty and probability, to calculate probability and probability, to analyze the combination of characteristics and structure. In the beginning of this year, we will conduct research on related documents and international conferences, and exchange information with overseas co-researchers. The basic combinatorial optimization problem is solved by analyzing the influence of computational efficiency and uncertainty. Specific, two-part transformation, vertex accuracy of the (complex solution process), in and out of the situation, the maximum solution to the problem of analysis and selection of groups. The time lag of each vertex is exponentially distributed, and the time lag of each vertex is formed. In this paper, we analyze the relationship between the waiting time of each vertex and the performance of each vertex. The 17th Conference on Web and Internet Economics(WINE2021) In 2022, the research results of the Center for Discrete Mathematics and Application were presented. The research results of combinatorial migration in association research were obtained.

项目成果

Eotvos Lorand University(ハンガリー)

罗兰大学（匈牙利）

Market Pricing for Matroid Rank Valuations

Matroid 排名估值的市场定价

• DOI: 10.1137/20m1386335
• 发表时间: 2021
• 期刊: SIAM Journal on Discrete Mathematics
• 影响因子: 0.8
• 作者: Kristof Berczi;Naonori Kakimura;Yusuke Kobayashi
• 通讯作者: Yusuke Kobayashi

Dynamic Bipartite Matching Market with Arrivals and Departures

• 发表时间: 2021-10
• 作者: Naonori Kakimura;Donghao Zhu

Monotone edge flips to an orientation of maximum edge-connectivity a la Nash-Williams

单调边缘翻转到最大边缘连通性的方向，如纳什-威廉姆斯

• DOI: 10.1145/3561302
• 发表时间: 2023
• 期刊: ACM Transactions on Algorithms
• 影响因子: 1.3
• 作者: Takehiro Ito;Yuni Iwamasa;Naonori Kakimura;Naoyuki Kamiyama;Yusuke Kobayashi;Shun-ichi Maezawa;Yuta Nozaki;Yoshio Okamoto;Kenta Ozeki
• 通讯作者: Kenta Ozeki

Shortest reconfiguration of perfect matchings via alternating cycles

通过交替循环实现完美匹配的最短重构

• DOI: 10.1137/20m1364370
• 发表时间: 2022
• 期刊: SIAM Journal on Discrete Mathematics
• 影响因子: 0.8
• 作者: Takehiro Ito;Naonori Kakimura;Naoyuki Kamiyama;Yusuke Kobayashi;Yoshio Okamoto
• 通讯作者: Yoshio Okamoto