垣村　尚徳 （カキムラ　ナオノリ）

Kakimura, Naonori

写真a

所属（所属キャンパス）

理工学部 数理科学科 （矢上）

職名

教授

HP

外部リンク
このページの先頭へ▲

経歴 【 表示 ／ 非表示 】

  • 2008年04月
    -
    2012年03月

    東京大学, 大学院情報理工学系研究科 数理情報学専攻, 助教

  • 2012年04月
    -
    2015年03月

    東京大学, 大学院総合文化研究科 附属国際環境学教育機構, 特任講師

  • 2013年01月
    -
    2018年03月

    国立情報学研究所, 客員教員

  • 2015年04月
    -
    2017年03月

    東京大学, 大学院総合文化研究科 附属国際環境学教育機構, 講師

  • 2017年04月
    -
    2024年03月

    慶應義塾大学, 理工学部 数理科学科, 准教授

全件表示 >>

このページの先頭へ▲

学歴 【 表示 ／ 非表示 】

  • 2003年03月

    東京大学, 工学部, 計数工学科 数理情報工学コース

    大学, 卒業

  • 2003年04月
    -
    2005年03月

    東京大学, 大学院情報理工学系研究科, 数理情報学専攻

    大学院, 修了, 修士

  • 2005年04月
    -
    2008年03月

    東京大学, 大学院情報理工学系研究科, 数理情報学専攻

    大学院, 修了, 博士

このページの先頭へ▲

学位 【 表示 ／ 非表示 】

  • 博士(情報理工学), 東京大学, 課程, 2008年03月

このページの先頭へ▲
 

研究分野 【 表示 ／ 非表示 】

  • 情報通信 / 情報学基礎論

  • 情報通信 / 数理情報学

  • 情報通信 / 数理情報学

このページの先頭へ▲

研究キーワード 【 表示 ／ 非表示 】

  • グラフアルゴリズム

  • 数理最適化

  • 数理最適化

  • 理論計算機科学

  • 組合せ最適化

このページの先頭へ▲
 

著書 【 表示 ／ 非表示 】

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

    垣村, 尚徳, サイエンス社, 2024年07月,  ページ数： v, 203p

このページの先頭へ▲

論文 【 表示 ／ 非表示 】

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

    査読有り,  ISSN  0167-6377

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

    研究論文（学術雑誌）, 査読有り

  • 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 J. Discrete Math. 36 （ 1 ） 355 - 382 2022年

    査読有り

  • Multi-Pass Streaming Algorithms for Monotone Submodular Function Maximization

    Chien-Chung Huang, Naonori Kakimura

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

    査読有り

  • Shortest Reconfiguration of Perfect Matchings via Alternating Cycles.

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

    SIAM J. Discrete Math. 36 （ 2 ）  2021年

    研究論文（学術雑誌）, 査読有り

全件表示 >>

このページの先頭へ▲

KOARA（リポジトリ）収録論文等 【 表示 ／ 非表示 】

このページの先頭へ▲

総説・解説等 【 表示 ／ 非表示 】

全件表示 >>

このページの先頭へ▲

研究発表 【 表示 ／ 非表示 】

  • Matchings in Bipartite Graphs with Stochastic Arrivals and Departures

    Naonori Kakimura

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

    2023年03月
    , 

    口頭発表（一般）

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

    垣村尚徳，新田陸

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

    2022年09月
    , 

    口頭発表（一般）

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

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

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

    2021年03月
    , 

    口頭発表（一般）

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

    垣村尚徳，Chien-Chung Huang

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

    2019年09月
    , 

    口頭発表（一般）

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

    垣村尚徳

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

    2019年08月
    , 

    口頭発表（一般）

全件表示 >>

このページの先頭へ▲

競争的研究費の研究課題 【 表示 ／ 非表示 】

  • グラフアルゴリズム基盤と最適化：理論研究と高速アルゴリズム開発

    2022年04月
    -
    2027年03月

    科学研究費助成事業, 河原林 健一, 垣村 尚徳, 小林 佑輔, 吉田 悠一, Avis David, 黒木 祐子, 基盤研究(S), 研究分担者

    　研究概要を見る

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

  • 不確実性をもつ組合せ最適化モデルに対する理論基盤の構築

    2021年04月
    -
    2026年03月

    慶應義塾大学, 科学研究費助成事業 基盤研究(B), 垣村 尚徳、田村 明久, 福永 拓郎, 澄田 範奈, 基盤研究(B), 研究代表者

    　研究概要を見る

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

  • 数学アプローチによる組合せ遷移の展開：活用事例を手がかりとして新解法へ

    2020年10月
    -
    2023年03月

    電気通信大学, 科学研究費助成事業 学術変革領域研究(B), 岡本 吉央、神山 直之, 垣村 尚徳, 小関 健太, 小林 佑輔, 野崎 雄太, 岩政 勇仁, 学術変革領域研究(B), 研究分担者

    　研究概要を見る

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

  • 遺伝統計学と最適化理論の学際連携による大規模ゲノム情報の再解釈

    2020年07月
    -
    2022年03月

    大阪大学, 科学研究費助成事業 挑戦的研究(萌芽), 岡田 随象、垣村 尚徳, 挑戦的研究(萌芽), 研究分担者

    　研究概要を見る

    大規模ゲノム情報は、①：長大なゲノム配列の中で一部の遺伝子変異のみが関与する「スパース性」、②：遺伝子変異数がサンプル数と比べて著しく大きい「P>>N問題」、が特徴である。遺伝統計学で扱われるヒト集団ゲノム情報は単純なグラフ構造として記述でき、即ち組合せ最適化問題として解釈可能である。本研究は、遺伝統計学と最適化理論の学際連携を通じて、大規模ヒトゲノム・臨床情報の組合せ最適化問題としての再定義を目指すものである。

  • 巨大グラフとビッグデータ解析の基礎基盤：　理論研究と高速アルゴリズム開発

    2018年06月
    -
    2023年03月

    国立情報学研究所, 科学研究費助成事業 基盤研究(S), 河原林 健一、垣村 尚徳, 小林 佑輔, 吉田 悠一, Avis David, 基盤研究(S), 研究分担者

    　研究概要を見る

    本研究では、基礎的なアルゴリズムに関する研究を行い、成果をあげた。以下に主要な２点を挙げる。
    グラフの連結度を求める問題は、東西冷戦時代（つまり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で開発した手法を踏まえ、この方向でも研究を進めたい。
    また分散計算においても、当該分野の最大の研究課題である「マッチング問題」「独立点問題」に貢献したいと考えている。

全件表示 >>

このページの先頭へ▲

受賞 【 表示 ／ 非表示 】

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

    2024年

  • Best Paper Award at COCOON2023

    Naonori Kakimura, Tomohiro Nakayoshi, 2023年12月

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

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

    受賞区分： 国内学会・会議・シンポジウム等の賞

  • 若手優秀講演賞

    2011年, 日本応用数理学会

  • 第4回文献賞奨励賞

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

全件表示 >>

このページの先頭へ▲
 

担当授業科目 【 表示 ／ 非表示 】

  • 計算数学特論Ｂ

    2025年度

  • 情報数学第１

    2025年度

  • 基礎理工学課題研究

    2025年度

  • 基礎理工学特別研究第２

    2025年度

  • 基礎理工学特別研究第１

    2025年度

全件表示 >>

このページの先頭へ▲

担当経験のある授業科目 【 表示 ／ 非表示 】

  • 計算機科学同実習

    慶應義塾

    2017年04月
    -
    2018年03月
    , 

    秋学期

  • 数学1B

    慶應義塾

    2017年04月
    -
    2018年03月
    , 

    秋学期

  • 計算数学特論

    慶應義塾

    2017年04月
    -
    2018年03月
    , 

    春学期

  • 数学2A

    慶應義塾

    2017年04月
    -
    2018年03月
    , 

    春学期

このページの先頭へ▲
 

所属学協会 【 表示 ／ 非表示 】

  • 日本応用数理学会

    　

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

    　

  • 情報処理学会

    　
このページの先頭へ▲