KEIO RESEARCHERS INFORMATION SYSTEM

Career 【 Display / hide 】

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

  -

  2024.03

  Keio University, Department of Mathematics, Associate Professor

display all >>

Academic Background 【 Display / hide 】

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

Academic Degrees 【 Display / hide 】

Academic Degrees 【 Display / hide 】

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

Research Areas 【 Display / hide 】

Research Areas 【 Display / hide 】

• Informatics / Theory of informatics

• Informatics / Mathematical informatics

• Informatics / Mathematical informatics

Research Keywords 【 Display / hide 】

Research Keywords 【 Display / hide 】

• Graph algorithms

• Mathematical Optimization

• Mathematical optimization

• Theoretical Computer Science

• Combinatorial Optimization

Books 【 Display / hide 】

Books 【 Display / hide 】

• 組合せ最適化への招待 : モデルとアルゴリズム

  垣村, 尚徳, サイエンス社, 2024.07,  Page： v, 203p

  • CiNii Research

Papers 【 Display / hide 】

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 >>

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

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

• Designing algorithms for network analysis with combinatorial optimization theory

  Kakimura, Naonori

  科学研究費補助金研究成果報告書 2022

• Efficient algorithms for combinatorial optimization problems with submodularity

  Kakimura, Naonori

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

Reviews, Commentaries, etc. 【 Display / hide 】

Reviews, Commentaries, etc. 【 Display / hide 】

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

  垣村 尚徳

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

  ISSN  0386-2240

  • CiNii Research

• Combinatorial Optimization for Network Analysis

  垣村 尚徳

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

  Other, Single Work

  • CiNii Research

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

  垣村 尚徳

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

  Other, Single Work,  ISSN  0386-2240

  • CiNii Research

• ネットワーク型交渉ゲームの安定化アルゴリズム

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

  情報処理学会研究報告(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 >>

Presentations 【 Display / hide 】

Presentations 【 Display / hide 】

• Matchings in Bipartite Graphs with Stochastic Arrivals and Departures

  Naonori Kakimura

  [International presentation]  12th Japanese-Hungarian Symposium on Discrete Mathematics and Its Applications, 

  2023.03

  , 

  Oral presentation (general)

• ストリーミングデータにおけるアイテム頻出数を求める省領域乱択アルゴリズム

  Naonori Kakimura, Riku Nitta

  [Domestic presentation]  電子情報通信学会コンピュテーション研究会, 

  2022.09

  , 

  Oral presentation (general)

• マトロイドランク効用関数をもつ組合せ市場の価格付け

  Bérczi Kristóf，垣村尚徳，小林佑輔

  [Domestic presentation]  日本応用数理学会 2021年研究部会連合発表会, 

  2021.03

  , 

  Oral presentation (general)

• Improved Streaming Algorithms for Maximizing Monotone Submodular Functions under a Knapsack Constraint

  垣村尚徳，Chien-Chung Huang

  [Domestic presentation]  情報処理学会第174回アルゴリズム研究会, 

  2019.09

  , 

  Oral presentation (general)

• 大規模ネットワーク解析のための組合せ最適化アルゴリズム

  垣村尚徳

  [Domestic presentation]  第32回回路とシステムワークショップ, 

  2019.08

  , 

  Oral presentation (general)

display all >>

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

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

• Theory and algorithms of combinatorial optimization for modern computational models

  2026.04

  -

  2031.03

  基盤研究(B), Principal investigator

• 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.

display all >>

Awards 【 Display / hide 】

Awards 【 Display / hide 】

• 日本オペレーションズ・リサーチ学会第14回研究賞

  2024

• Best Paper Award at COCOON2023

  Naonori Kakimura, Tomohiro Nakayoshi, 2023.12

• 第19回情報科学技術フォーラムFIT船井ベストペーパー賞

  岡本 吉央, 伊藤 健洋, 垣村 尚徳, 神山 直之, 小林 佑輔, 2021, 船井情報科学振興財団, 構造変化に応じるロバスト修復可能マトロイド基問題に対する固定パラメータアルゴリズム

  Type of Award： Award from Japanese society, conference, symposium, etc.

• 若手優秀講演賞

  2011, 日本応用数理学会

• 第4回文献賞奨励賞

  2009, 日本オペレーションズ・リサーチ学会

display all >>

Courses Taught 【 Display / hide 】

Courses Taught 【 Display / hide 】

• GRADUATE RESEARCH ON INFORMATICS, MANAGEMENT, AND HUMAN SCIENCES B1

  2026

• GRADUATE RESEARCH ON INFORMATICS, MANAGEMENT, AND HUMAN SCIENCES B2

  2026

• GRADUATE RESEARCH ON INFORMATICS, MANAGEMENT, AND HUMAN SCIENCES A1

  2026

• COMPUTER SCIENCE & LABORATORY

  2026

• DOCTORAL RESEARCH ON INFORMATICS, MANAGEMENT, AND HUMAN SCIENCES

  2026

display all >>

Courses Previously Taught 【 Display / hide 】

Courses Previously Taught 【 Display / hide 】

• 計算機科学同実習

  Keio University

  2017.04

  -

  2018.03

  , 

  Autumn Semester

• 数学1B

  Keio University

  2017.04

  -

  2018.03

  , 

  Autumn Semester

• 計算数学特論

  Keio University

  2017.04

  -

  2018.03

  , 

  Spring Semester

• 数学2A

  Keio University

  2017.04

  -

  2018.03

  , 

  Spring Semester

Memberships in Academic Societies 【 Display / hide 】

Memberships in Academic Societies 【 Display / hide 】

• 日本オペレーションズリサーチ学会

  　

• 情報処理学会

  　

• The Japan Society for Industrial and Applied Mathematics