Large Graphs: Theory and Algorithms

大图：理论和算法

基本信息

批准号：
18H05291
负责人：
河原林健一
金额：
$ 123.55万
依托单位：
National Institute of Informatics
依托单位国家：
日本
项目类别：
Grant-in-Aid for Scientific Research (S)
财政年份：
2018
资助国家：
日本
起止时间：
2018-06-11 至 2023-03-31
项目状态：
已结题

项目摘要

１．離散数学、グラフアルゴリズムにおける構造解析を行うための海外からのPDを雇う予定であったが、それがCOVID-19（新型コロナウィルス感染症）の影響により研究員を補充することが全くできなかったため、以下の2分野をRAと共同研究者とともに遂行した。２．オンラインアルゴリズム開発と機械学習への応用、そして、３．アルゴリズム技術を機械学習への応用、を行う予定である。この２つは、機械学習分野において、理論分野の応用が活発に行われている研究分野である。２に関しては、推薦システムの最適化やポートフォリオ選択など、評価指標が不確定な状況で意思決定をしながら逐次的に戦略を改善するための取り組みとして、オンライン最適化やバンディット最適化の枠組みに取り組んだ。これらの成果は、世界的に評価されている研究成果をNeuRIPS、AAAI、AISTATなどで発表してきた。３に関しては、河原林はすでにグラフ理論的な解析とグラフ構造の知見を利用し、グラフニューラルネットワーク解析において、すでにインパクトのある研究成果を残している（ICLR'21）。これらの論文は、グラフニューラルネットワークの性能と限界に関して大きなインパクトを与えた。

1。他们计划从海外雇用PDS来在离散数学和图形算法中进行结构分析，但是由于COVID-19（Covid-19）的影响，他们根本无法补充研究人员，因此他们与RA和RA和协作者一起进行了以下两个领域。 2。在线算法开发和机器学习的应用，以及3。公司计划将算法技术应用于机器学习。这两个是在机器学习领域积极应用理论领域的研究领域。关于2，我们在在线优化和强盗优化的框架上致力于依次改善策略的努力，同时在评估指标不确定的情况下做出决策，例如优化建议系统和投资组合选择。这些结果已在神经，AAAI，AISTAT和其他组织的全球认可的研究结果中介绍。关于3，卡瓦拉巴亚西已经使用了图理论分析和图形结构知识来在图形神经网络分析（ICLR'21）中取得了影响力的研究结果。这些论文对图神经网络的性能和局限性产生了重大影响。

项目成果

期刊论文数量（0）

专著数量（0）

科研奖励数量（0）

会议论文数量（0）

专利数量（0）

Directed Graph Minors

有向图未成年人

DOI：
发表时间：
2018
期刊：
影响因子：
0
作者：
Kazuyo Moro;Ken-ichi Kawarabayashi;Ken-ichi Kawarabayashi
通讯作者：
Ken-ichi Kawarabayashi

Spectral Hypergraph Sparsifiers of Nearly Linear Size

近线性尺寸的谱超图稀疏器

DOI：
10.1109/focs52979.2021.00114
发表时间：
2022
期刊：
FOCS'21
影响因子：
0
作者：
Kapralov Michael;Krauthgamer Robert;Tardos Jakab;Yoshida Yuichi
通讯作者：
Yoshida Yuichi

Complexity of the Multi-Service Center Problem

多服务中心问题的复杂性

DOI：
10.1016/j.tcs.2020.07.021
发表时间：
2020
期刊：
Theoretical Computer Science
影响因子：
1.1
作者：
Takehiro Ito;Naonori Kakimura;and Yusuke Kobayashi
通讯作者：
and Yusuke Kobayashi

Embeddings of Planar Quasimetrics into Directed ℓ 1 and Polylogarithmic Approximation for Directed Sparsest-Cut

将平面拟度量嵌入有向 α 1 和有向稀疏割的多对数逼近

DOI：
10.1109/focs52979.2021.00055
发表时间：
2022
期刊：
2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS
影响因子：
0
作者：
Kawarabayashi, Ken-Ichi;Sidiropoulos, Anastasios
通讯作者：
Sidiropoulos, Anastasios

A nearly 5/3-approximation FPT Algorithm for Min-k-Cut

一种近 5/3 近似的 Min-k-Cut FPT 算法

DOI：
10.1137/1.9781611975994.59
发表时间：
2020
期刊：
Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms (SODA 2020)
影响因子：
0
作者：
Kawarabayashi Ken-ichi;Lin Bingkai
通讯作者：
Lin Bingkai