权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

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. Discrete mathematics, structural analysis, overseas PD, employment, impact of COVID-19 (new type of COVID-19 infection), researcher's supplement, the following two fields, RA and co-investigator's implementation 2. 3. The development and application of mechanical learning technology 2. The division of mechanical learning, the division of theoretical application, the division of research. 2. The optimization of the recommended system is based on the selection and evaluation of indicators, the rational decision-making of uncertain conditions, and the improvement of the selection and optimization of the system. The results of this research are reviewed by the world. The results of this research are published in NeuRIPS, AAAI and AISTAT. 3. The results of research on the analysis of the theory and the knowledge of the structure of Kawahara Hayashi are still incomplete (ICLR'21). This paper is about the performance and limits of the company.

项目成果

期刊论文数量（0）

专著数量（0）

科研奖励数量（0）

会议论文数量（0）

专利数量（0）

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

Directed Graph Minors

有向图未成年人

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

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

Directed Tangle Tree-Decompositions and Applications

有向缠结树分解与应用

DOI：
10.1137/1.9781611977073.19
发表时间：
2022
期刊：
SODA'22
影响因子：
0
作者：
Giannopoulou Archontia C.;Kawarabayashi Ken-ichi;Kreutzer Stephan;Kwon O-joung
通讯作者：
Kwon O-joung

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