Details of a Researcher - Kakimura, Naonori

Kakimura, Naonori

写真a

Affiliation: Faculty of Science and Technology, Department of Mathematics （Yagami）

Position: Associate Professor

Related Websites

http://www.math.keio.ac.jp/~kakimura/index.html

Page Top ▲

Career 【 Display / hide 】

2008.04

-

2012.03

University of Tokyo, Department of Mathematical Informatics, Assistant Professor
2012.04

-

2015.03

University of Tokyo, Graduate School of Arts and Sciences, Project Lecturer
2013.01

-

2018.03

National Institute of Informatics, 客員教員
2015.04

-

2017.03

University of Tokyo, Graduate School of Arts and Sciences, Lecturer
2017.04

-

Present

Keio University, Department of Mathematics, Associate Professor

Page Top ▲

Academic Background 【 Display / hide 】

2003.03

The University of Tokyo, 工学部, 計数工学科数理情報工学コース

University, Graduated
2003.04

-

2005.03

The University of Tokyo, 大学院情報理工学系研究科, 数理情報学専攻

Graduate School, Completed, Master's course
2005.04

-

2008.03

The University of Tokyo, 大学院情報理工学系研究科, 数理情報学専攻

Graduate School, Completed, Doctoral course

Page Top ▲

Academic Degrees 【 Display / hide 】

博士(情報理工学), The University of Tokyo, Coursework, 2008.03

Page Top ▲

Research Areas 【 Display / hide 】

Informatics / Theory of informatics
Informatics / Mathematical informatics
Informatics / Mathematical informatics

Page Top ▲

Research Keywords 【 Display / hide 】

Graph algorithms
Mathematical Optimization
Mathematical optimization
Theoretical Computer Science
Combinatorial Optimization

Page Top ▲

Papers 【 Display / hide 】

A Parameterized View to the Robust Recoverable Base Problem of Matroids Under Structural Uncertainty

T Ito, N Kakimura, N Kamiyama, Y Kobayashi, Y Okamoto

Operations Research Letters （Elsevier BV) 50 （ 3 ） 370 - 375 2022

Accepted, ISSN 0167-6377
- Access to Document (DOI)
Monotone edge flips to an orientation of maximum edge-connectivity à la Nash-Williams.

Takehiro Ito, Yuni Iwamasa, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi 0001, Shun-ichi Maezawa, Yuta Nozaki, Yoshio Okamoto, Kenta Ozeki

ACM Transactions on Algorithms (TALG) 2022

Research paper (scientific journal), Accepted
- Access to Document (DOI)
Approximability of Monotone Submodular Function Maximization under Cardinality and Matroid Constraints in the Streaming Model

Chien-Chung Huang, Naonori Kakimura, Simon Mauras, and Yuichi Yoshida

SIAM Journal on Discrete Mathematics 36 （ 1 ） 355 - 382 2022

Accepted
Multi-Pass Streaming Algorithms for Monotone Submodular Function Maximization

CC Huang, N Kakimura

Theory of Computing Systems 66 （ 1 ） 354 - 394 2022

Accepted
Shortest Reconfiguration of Perfect Matchings via Alternating Cycles.

Takehiro Ito, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, Yoshio Okamoto

SIAM Journal on Discrete Mathematics 36 （ 2 ） 2021

Research paper (scientific journal), Accepted

display all >>

Page Top ▲

Papers, etc., Registered in KOARA 【 Display / hide 】

Efficient algorithms for combinatorial optimization problems with submodularity

Kakimura, Naonori

学事振興資金研究成果実績報告書（慶應義塾大学) 2018

Page Top ▲

Reviews, Commentaries, etc. 【 Display / hide 】

離散数学入門 : グラフ,マトロイドから離散凸解析まで (特集離散数学に親しむ)

垣村尚徳

数理科学 (サイエンス社) 59 ( 12 ) 22 - 29 2021.12

ISSN 0386-2240
Combinatorial Optimization for Network Analysis

垣村尚徳

回路とシステムワークショップ論文集 Workshop on Circuits and Systems ([電子情報通信学会]) 32 55 - 60 2019.08

Other, Single Work
情報科学と線形代数 : ネットワーク解析と行列固有値 (特集線形代数の探究 : 様々な問題を通してみるその姿)

垣村尚徳

数理科学 (サイエンス社) 54 ( 8 ) 45 - 51 2016.08

Other, Single Work, ISSN 0386-2240
ネットワーク型交渉ゲームの安定化アルゴリズム

伊藤健洋, 垣村尚徳, 神山直之, 小林佑輔, 岡本吉央

情報処理学会研究報告(Web) 2016 ( AL-157 ) VOL.2016‐AL‐157,NO.3 (WEB ONLY) 2016.02

Other, Joint Work
イマージョンを含まないグラフに対する彩色アルゴリズム

垣村尚徳, 河原林健一

日本応用数理学会年会講演予稿集(CD-ROM) 2016 ROMBUNNO.9GATSU13NICHI,11:00,3E,3 2016

Other, Joint Work, ISSN 1345-3378

display all >>

Page Top ▲

Presentations 【 Display / hide 】

Spectral Aspects of Symmetric Matrix Signings

KAKIMURA Naonori

日本応用数理学会2018年研究部会連合発表会 (大阪大学) ,

2018.03
,
Oral presentation (general)
Streaming Submodular Maximization under a Knapsack Constraint

Huang Chien-Chung, KAKIMURA Naonori, Yoshida Yuichi

The 10th Japanese-Hungarian Symposium on Discrete Mathematics and Its Applications,

2017.05
,
Oral presentation (general)

Page Top ▲

Research Projects of Competitive Funds, etc. 【 Display / hide 】

Graph Algorithms and Optimization: Theory and Scalable Algorithms

2022.04

-

2027.03

Grants-in-Aid for Scientific Research, Grant-in-Aid for Scientific Research (S), Coinvestigator(s)

　View Summary

現在の情報検索技術（GoogleのPageRank）、セキュリティ技術（Appleの(Local)　Differential Privacy）などのアルゴリズム革新は国家規模のビジネス創成につながり、現在のGAFAを作り上げた。ここで重要なのは、PageRankもDifferential Privacyもアルゴリズム、離散数学の基礎・理論研究であり、最初から応用を志向した仕事ではない点である。本研究では、このような背景を踏まえ、グラフアルゴリズム、離散数学、組合せ最適化分野での世界的な研究成果発信を目指す。またこれらを通して「人材育成」およびアルゴリズム国際共同研究拠点構築を目指す。
Theory and algorithms for combinatorial optimization under uncertainty

2021.04

-

2026.03

Keio University, Grants-in-Aid for Scientific Research Grant-in-Aid for Scientific Research (B), Grant-in-Aid for Scientific Research (B), Principal investigator

　View Summary

組合せ最適化は膨大な組合せの中から最適なものを見つけるための方法論であり実社会への応用が数多くある．本研究課題では，不確実性をもつ組合せ最適化モデルに対して，計算効率性や近似可能性を特徴付ける組合せ構造の解析を行う．情報通信・社会システム設計などの応用分野では，センサーの観測にもとづきリアルタイムで最適化することや，データを予測しつつ逐次的に最適化することなど，必要な情報が後から得られる状況下での最適化が重要となる．このようなモデルの記述が不確実・不完全な状況を扱える汎用的な組合せ最適化モデルの解析に取り組み，応用分野に有用となる新しい理論基盤を創出する．
Development of Combinatorial Reconfiguration by Mathematics Approach: From Examples to New Methods

2020.10

-

2023.03

The University of Electro-Communications, Grants-in-Aid for Scientific Research Grant-in-Aid for Transformative Research Areas (B), Grant-in-Aid for Transformative Research Areas (B), Coinvestigator(s)

　View Summary

組合せ遷移とは「状態空間上での遷り変り」を数理モデル化・解析するアルゴリズム理論であり，その概念は，理論から応用まで多種多様な分野に現れる．本研究領域では，組合せ遷移のアルゴリズム基盤，実装技術基盤，数学基盤を構築することで，研究でも実務でも障壁なく，組合せ遷移のアルゴリズム技術を利活用するための共通基盤を構築する．本研究は計画研究C01班であり，数学を背景分野とする．特に，組合せ遷移における数学活用事例の体系的収集と組合せ遷移の研究に資する数理手法の開発を推進する．これにより，個別的にアドホックな手法で研究されていた組合せ遷移を，数学の視点から組織的に捉え直し，体系化を図る．
Re-annotation of large-scale human genome data by integration of statistical genetics and operations research

2020.07

-

2022.03

Osaka University, Grants-in-Aid for Scientific Research, Okada Yukinori, Challenging Research (Exploratory), Coinvestigator(s)

　View Summary

Large-scale human genome data has two major characteristics; (i) limited fractions of the human genome variations only affects human disease risk, (ii) numbers of the human genome variations are much larger than those of samples (i.e., P>>N problem). Statistical genetics handles human population genome data as input, which can be described as simple graphs. We considered that these graphs can be solved by operations researches. This project aims re-annotation of large-scale human genome data by integration of statistical genetics and operations research through iterdisciplinary cooperative studies.
Large Graphs: Theory and Algorithms

2018.06

-

2023.03

National Institute of Informatics, Grants-in-Aid for Scientific Research Grant-in-Aid for Scientific Research (S), Grant-in-Aid for Scientific Research (S), Coinvestigator(s)

　View Summary

本研究では、基礎的なアルゴリズムに関する研究を行い、成果をあげた。以下に主要な２点を挙げる。
グラフの連結度を求める問題は、東西冷戦時代（つまり1950 年代）より組合せ最適化における中心的課題の一つである。以下の論文では、辺連結度に関して、初の「決定的」な「ほぼ」線形アルゴリズムを与えた。辺連結度に関する「非決定的」な「ほぼ」線形アルゴリズムは、Karger により2000 年に開発されていたが、「決定的」アルゴリズムは長年未解決であった。本論文はその最終的な解決を与えている。本論文は、コンピューターサイエンス分野の最高峰の国際学術雑誌 Journal of the ACM（ J. ACM）に掲載されている。またグラフの連結度を求める問題は、グラフの最小カットを求める問題に相当する。この最小カットを拡張するk-カット問題は、NP困難問題であることが知られているが、既存の近似アルゴリズムを大幅に更新した。
バンディット問題は、現在機械学習分野における一大分野であり、最悪ケースにおけるリグレット解析、および計算量の解析が主要課題である。またバンディット問題の中にも、組合せ最適化問題、オンライン線形計画化問題など、数多くのバリエーションがある。本研究では、１．バンディット組合せ的最適化問題に対して、最悪ケースにおけるリグレット損失の下界を改善。２．バンディットフィードバックを持つオンライン線形最適化問題に対して、オフライン線形最適化問題を解くオラクルを仮定したもとで、劣線形リグレットを達成しつつ効率的な（つまりオラクル呼び出し回数が少ない）アルゴリズムを与えた。３．バンディット問題のオンラインポートフォリオ版に対しても、最善のリグレットバウンドを与えた。
現時点で得られている成果は、計算機科学分野の国際会議ランキングで最も信頼度が高いThe Computing Research and Education Association of Australasia (CORE)において、トップにあたるCORE　A*国際会議に、11本の論文が採択され、CORE　A*に次ぐランクのCORE Aには、全部で8本の論文が採択されている。CORE A* およびCORE　Aにランクされる論文を20本近く過去2年弱で発表した事実は、当該研究分野で世界に十分認められる研究業績の生産性を表している。さらに計算機科学全体でトップのジャーナルであるJ.ACMに論文が採択され、計算機科学分野のトップ会議であるICALP’19のベストペーパーも獲得している。これらは、世界をリードするような研究成果である。
現在一番力を入れているのは「向き付きグラフマイナー理論」である。向きなしグラフマイナー理論が、多くのステップ（23論文、500ページ以上）が必要であったように、向き付けグラフマイナー理論も、今後多くのステップが必要であることは多くのグラフ理論研究者やアルゴリズム研究コミュニティに理解されている。現在の研究成果として、アルゴリズム分野のトップ会議に採用された2つの論文（SODA’19、SODA’20）は、向き付きグラフマイナー理論構築の途中経過の結果であるが、アルゴリズム研究コミュニティに高く評価されている。なおSODA’19はグラフマイナー論文VIIの一部、そしてSODA’20はグラフマイナー論文XIIIにあたる。グラフマイナー論文自体は、XXIIIまであり、本研究期間終了までは、XXまでの仕事が完了すると考えている。
グラフのトポロジー面を考慮したアルゴリズム開発は、STOC’19に代表されるような、曲面上に埋め込まれたグラフの解析が最も大きな課題である。STOC’19で開発した手法を踏まえ、この方向でも研究を進めたい。
また分散計算においても、当該分野の最大の研究課題である「マッチング問題」「独立点問題」に貢献したいと考えている。