モバイルエージェントシステムにおけるメモリ領域の導入

移动Agent系统中内存区域的介绍

• 批准号: 19J22696
• 负责人: 北村 直暉
• 金额: $ 1.6万
• 依托单位: Nagoya Institute of Technology
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for JSPS Fellows
• 财政年份: 2019
• 资助国家: 日本
• 起止时间: 2019-04-25 至 2022-03-31
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-19J22696/
• 关键词: モバイルエージェント; 分散アルゴリズム; ランデブー問題

今年度は前年度までの研究成果を取りまとめるとともに分散アルゴリズムに関する幅広い研究を行った．モバイルエージェントに関する研究では前年度より研究を行っていたランデブー問題について取り扱った．ランデブー問題に関する結果はIEICE Transactionsに採択が決定した．また，分散グラフアルゴリズムに関してもいくつかの研究を行った．前年度より研究を行っていた低競合ショートカットに関する研究は新しくIEICE Transactionsに採択が決定した．2つ目の研究ではCONGESTモデルにおける最大マッチング問題について取り扱った．頂点数nのCONGESTモデルにおける最大マッチング問題に対して，これまでの研究ではCONGESTモデルにおける自明な上界であるO(n^2)ラウンドよりも高速なアルゴリズムは知られていなかった．本研究ではO(n^{3/2})ラウンドの最大マッチングを解くアルゴリズムを新たに構築した．この結果は国内の情報科学ワークショップならびに国際ジャーナルのIEICE Transactionsに新しく投稿し採択された．3つ目の研究はCONGESTモデルにおける最小カットを高速に発見するアルゴリズムである．CONGESTモデルにおける厳密な最小カットを求める問題はDory等によって \tilde{O}(n^1/2+D)ラウンドのアルゴリズムが知られており，これは入力の対数時間を無視すれば下界に一致することが知られている．本研究では最小カットのサイズが小さい場合のアルゴリズムについて研究を行った．具体的にはグラフがサイズkのカットを持つときO(2^{O(k^2 )}D^{(k-2)}log n)ラウンドで最小カット問題を解くアルゴリズムが存在することを示した．この結果は国内ワークショップである情報科学ワークショップで発表されており自分は共著者となっている．

This year's research results are distributed. The study of the previous year was carried out in the middle of the study. IEICE Transactions is the result of a problem. In addition, it is necessary to carry out research on decentralization. Previous year's research was conducted on low competition issues. Research on new IEICE Transactions was conducted on mining decisions. 2 Research on CONGEST was conducted on maximum competition issues. The CONGEST number n is the maximum number of vertices in the CONGEST problem. The upper bound of the CONGEST problem is O(n^2). In this study, O(n^{3/2}) was used to construct a new structure for solving the problem of the maximum number of clusters. The results of this study are new contributions to IEICE Transactions in China and in the international community. 3. The study of CONGEST is based on the minimum space for high-speed development. CONGEST is based on the minimum space for high-speed development. The problem of finding the minimum space for high-speed development is based on the problem of Dory, etc. The number of entries is ignored. This study is aimed at the research of the minimum size of the system. The problem of minimal space exists in the physical space of the object, O(2^{O(k^2 )}D^{(k-2)}log n). The results of this research are as follows:

项目成果

CONGEST モデルにおける最大マッチングのための劣二乗アルゴリズム

CONGEST 模型中最大匹配的 Subsquares 算法

• 发表时间: 2021
• 作者: 北村 直暉;泉 泰介
• 通讯作者: 泉 泰介

k-極大独立検証問題の分散計算複雑性

k-最大独立验证问题的分布式计算复杂度

• 发表时间: 2021
• 作者: 佐藤僚祐;北村直暉;江口僚太;金 鎔煥，泉泰介
• 通讯作者: 金 鎔煥，泉泰介

最小カットを高確率で発見する乱択分散アルゴリズム

以高概率找到最小割的随机分布算法

• 发表时间: 2021
• 作者: 森本椋太;北村直暉;泉泰介
• 通讯作者: 泉泰介

Uniform distribution for Pachinko

弹珠机均匀分布

• DOI: 10.1016/j.tcs.2020.05.032
• 发表时间: 2020
• 期刊: Theoretical Computer Science
• 影响因子: 1.1
• 作者: Ryota Eguchi;Naoki Kitamura;Taisuke Izumi;Naoki Kitamura,Yuya Kawabata Yuya,Taisuke Izumi
• 通讯作者: Naoki Kitamura,Yuya Kawabata Yuya,Taisuke Izumi

地図を持つエージェントの平均的に高速なランデブーアルゴリズム

具有地图的代理的平均快速交会算法

• 发表时间: 2019
• 作者: 北村 直暉;泉 泰介;佐藤 僚祐;鉾館 歩;Ryota Eguchi;Taisuke Izumi;Frederic Magniez;Noga Harlev;Yuichi Sudo;Yuval Emek;Magnus M. Halldorsson;Francois Le Gall;Yuichi Sudo;Shimon Bitton;Naoki Kitamura;柿澤一輝
• 通讯作者: 柿澤一輝