慶應義塾研究者情報データベース

経歴 【 表示 ／ 非表示 】

経歴 【 表示 ／ 非表示 】

• 2008年04月

  -

  2012年03月

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

• 2012年04月

  -

  2015年03月

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

• 2013年01月

  -

  2018年03月

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

• 2015年04月

  -

  2017年03月

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

• 2017年04月

  -

  継続中

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

学歴 【 表示 ／ 非表示 】

学歴 【 表示 ／ 非表示 】

• 2003年03月

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

  大学, 卒業

• 2003年04月

  -

  2005年03月

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

  大学院, 修了, 修士

• 2005年04月

  -

  2008年03月

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

  大学院, 修了, 博士

学位 【 表示 ／ 非表示 】

学位 【 表示 ／ 非表示 】

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

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

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

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

• 情報通信 / 数理情報学

• 情報通信 / 数理情報学

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

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

• グラフアルゴリズム

• 数理最適化

• 数理最適化

• 理論計算機科学

• 組合せ最適化

論文 【 表示 ／ 非表示 】

論文 【 表示 ／ 非表示 】

• Monotone edge flips to an orientation of maximum edge-connectivity à la Nash-Williams∗

  T Ito, Y Iwamasa, N Kakimura, N Kamiyama, Y Kobayashi, S Maezawa, ...

  Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms … 2022年

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

• Reforming an Envy-Free Matching

  T Ito, Y Iwamasa, N Kakimura, N Kamiyama, Y Kobayashi, Y Nozaki, ...

  2022年

• Online Task Assignment Problems with Reusable Resources

  H Sumita, S Ito, K Takemura, D Hatano, T Fukunaga, N Kakimura, ...

  arXiv preprint arXiv:2203.07605 abs/2203.07605 2022年

  • Access to Document (DOI)

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

• Submodular reassignment problem for reallocating agents to tasks with synergy effects

  N Kakimura, N Kamiyama, Y Kobayashi, Y Okamoto

  Discrete Optimization, 100631 2021年

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

全件表示 >>

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

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

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

  垣村 尚徳

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

  ISSN  0386-2240

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

  垣村 尚徳

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

  その他, 単著

• Shortest Reconfiguration of Perfect Matchings via Alternating Cycles

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

   2019年07月

  　概要を見る

  Motivated by adjacency in perfect matching polytopes, we study the shortest
  reconfiguration problem of perfect matchings via alternating cycles. Namely, we
  want to find a shortest sequence of perfect matchings which transforms one
  given perfect matching to another given perfect matching such that the
  symmetric difference of each pair of consecutive perfect matchings is a single
  cycle. The problem is equivalent to the combinatorial shortest path problem in
  perfect matching polytopes. We prove that the problem is NP-hard even when a
  given graph is planar or bipartite, but it can be solved in polynomial time
  when the graph is outerplanar.
  

• Causal Bandits with Propagating Inference

  Akihiro Yabe, Daisuke Hatano, Hanna Sumita, Shinji Ito, Naonori Kakimura, Takuro Fukunaga, Ken-ichi Kawarabayashi

   2018年06月

  　概要を見る

  Bandit is a framework for designing sequential experiments. In each
  experiment, a learner selects an arm $A \in \mathcal{A}$ and obtains an
  observation corresponding to $A$. Theoretically, the tight regret lower-bound
  for the general bandit is polynomial with respect to the number of arms
  $|\mathcal{A}|$. This makes bandit incapable of handling an exponentially large
  number of arms, hence the bandit problem with side-information is often
  considered to overcome this lower bound. Recently, a bandit framework over a
  causal graph was introduced, where the structure of the causal graph is
  available as side-information. A causal graph is a fundamental model that is
  frequently used with a variety of real problems. In this setting, the arms are
  identified with interventions on a given causal graph, and the effect of an
  intervention propagates throughout all over the causal graph. The task is to
  find the best intervention that maximizes the expected value on a target node.
  Existing algorithms for causal bandit overcame the
  $\Omega(\sqrt{|\mathcal{A}|/T})$ simple-regret lower-bound; however, their
  algorithms work only when the interventions $\mathcal{A}$ are localized around
  a single node (i.e., an intervention propagates only to its neighbors).
  We propose a novel causal bandit algorithm for an arbitrary set of
  interventions, which can propagate throughout the causal graph. We also show
  that it achieves $O(\sqrt{ \gamma^*\log(|\mathcal{A}|T) / T})$ regret bound,
  where $\gamma^*$ is determined by using a causal graph structure. In
  particular, if the in-degree of the causal graph is bounded, then $\gamma^* =
  O(N^2)$, where $N$ is the number $N$ of nodes.
  

• 情報科学と線形代数 --- ネットワーク解析と行列固有値 ---

  垣村 尚徳

  数理科学    45 - 51 2016年08月

  記事・総説・解説・論説等（商業誌、新聞、ウェブメディア）, 単著

全件表示 >>

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

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

• 対称行列の符号付けとグラフスペクトル

  垣村 尚徳

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

  2018年03月

  , 

  口頭発表（一般）

• Streaming Submodular Maximization under a Knapsack Constraint

  Huang Chien-Chung, 垣村 尚徳, 吉田 悠一

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

  2017年05月

  , 

  口頭発表（一般）

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

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

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

  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で開発した手法を踏まえ、この方向でも研究を進めたい。
  また分散計算においても、当該分野の最大の研究課題である「マッチング問題」「独立点問題」に貢献したいと考えている。

• 組合せ最適化理論を用いたネットワーク解析手法の設計

  2017年04月

  -

  2021年03月

  文部科学省・日本学術振興会, 科学研究費助成事業, 垣村　尚徳, 基盤研究(C), 補助金,  研究代表者

  　研究概要を見る

  本研究課題の目的は，ネットワーク内の有用な構造を検出するための数理モテルの構築と効率的な計算手法の設計である．本年度は，昨年度に引き続き，大規模なネットワークを解析するために，制約付き劣モジュラ関数最大化に対するストリーミングアルゴリズムの設計に取り組んだ．我々が提案したアルゴリズムは，入力データを定数回しか見ずに効率的に近似解を計算するものであり，メモリ効率が高くデータが大規模な場合に有用である．まず，サイズ制約付きの問題に対して，従来手法よりも高速に，理論的に最適な近似解を求めるアルゴリズムを提案した．さらに，ナップサック制約付の問題について初めて非自明な近似比解析を与えた．本成果はフランス ENS の Chien-Chung Huang 氏との共同研究である．
  さらに，ネットワークの中から同じ性質や構造を持つ部分（コミュニティ）を検出するための最適化モデルを提案した．ネットワーク内のコミュニティを検出する問題はグラフマイニングにおける基本的な問題である．本研究課題では，コミュニティがその内部では密なつながりを持つが外へのつながりが薄いという性質を持つことに着目し，コミュニティ検出のための新しい最適化モデルを提案した．提案モデルは，最密グラフ問題と呼ばれる組合せ最適化問題の拡張でありモジュラリティ密度最大化問題とも関連が深い．本研究ではまず，提案モデルが多項式時間で計算可能であることを示した．具体的には，線形計画問題に基づくものと最大流アルゴリズムを用いたものという2つのアルゴリズムを提案した．さらに，大規模ネットワークに適用できる，ほぼ線形時間の貪欲近似アルゴリズムを提案した．データセットを用いた計算機実験により提案アルゴリズムが効果的にコミュニティを検出できることを確認した．本成果は宮内 敦史氏（理研AIP）との共同研究であり，査読付国際会議CIKMに採択された．
  昨年度の研究を発展させ，劣モジュラ関数最大化という組合せ最適化問題に対するストリーミング計算手法の開発に取り組み，一定の成果を得た．また，当初の計画通り，ネットワーク内のコミュニティ構造を見つけるための組合せ最適化モデルを提案することができた．よって計画は順調に進展していると言える.
  本年度に提案した劣モジュラ関数最大化問題に対するストリーミング計算手法の有用性を検証する．計算時間や近似比等の改善の可能性や実用的な有効性の確認などを，共同研究者と協力しつつ引き続き研究を推進する．また，ネットワーク内のコミュニティ構造を見つけるための組合せ最適化モデルについて，より現実に近い状況が扱えるように提案モデルを改良し，高速・高精度な計算手法の設計に取り組む．このための情報収集や研究討論を目的として，国内外の研究集会への参加や共同研究者先への訪問を計画している．また，研究の過程で得られた理論的成果，実験結果に関する情報交換を行なうために，国内外の研究会等で発表する．

全件表示 >>

受賞 【 表示 ／ 非表示 】

受賞 【 表示 ／ 非表示 】

• 若手優秀講演賞

  2011年, 日本応用数理学会

• 第4回文献賞奨励賞

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

• 「計算と最適化」研究部会S@CO 最優秀発表賞

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

• コンピュータサイエンス領域奨励賞

  2008年, 情報処理学会

• 第23回学生論文賞

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

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

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

• 数学１Ｂ

  2022年度

• 数学１Ａ

  2022年度

• 総合教育セミナーⅡ

  2022年度

• 情報数学第１

  2022年度

• 基礎理工学課題研究

  2022年度

全件表示 >>

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

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

• 計算機科学同実習

  慶應義塾

  2017年04月

  -

  2018年03月

  , 

  秋学期

• 数学1B

  慶應義塾

  2017年04月

  -

  2018年03月

  , 

  秋学期

• 計算数学特論

  慶應義塾

  2017年04月

  -

  2018年03月

  , 

  春学期

• 数学2A

  慶應義塾

  2017年04月

  -

  2018年03月

  , 

  春学期

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

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

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

  　

• 情報処理学会

  　

• 日本応用数理学会