Kakimura, Naonori

写真a

Affiliation

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

Position

Associate Professor

Related Websites
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 】

  • Theory of informatics

  • Mathematical informatics

Page Top ▲

Research Keywords 【 Display / hide 】

  • Mathematical Optimization

  • Theoretical Computer Science

  • Combinatorial Optimization

Page Top ▲
 

Papers 【 Display / hide 】

  • Market Pricing for Matroid Rank Valuations

    K Bérczi, N Kakimura, Y Kobayashi

    arXiv preprint arXiv:2007.08759  2020

    Research paper (scientific journal), Accepted

  • Approximability of monotone submodular function maximization under cardinality and matroid constraints in the streaming model

    CC Huang, N Kakimura, S Mauras, Y Yoshida

    arXiv preprint arXiv:2002.05477  2020

    Research paper (scientific journal), Accepted

  • Shortest reconfiguration of perfect matchings via alternating cycles

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

    Leibniz International Proceedings in Informatics, LIPIcs （Leibniz International Proceedings in Informatics, LIPIcs)  144 2019.09

    Research paper (scientific journal), Accepted,  ISSN  9783959771245

    　View Summary

    © Takehiro Ito, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, and Yoshio Okamoto. 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.

  • Shortest Reconfiguration of Perfect Matchings via Alternating Cycles

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

     2019.07

    Research paper (scientific journal), Accepted

    　View Summary

    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.

  • Total dual integrality of the linear complementarity problem.

    Hanna Sumita,Naonori Kakimura,Kazuhisa Makino

    Annals OR （Annals of Operations Research)  274 （ 1-2 ） 531 - 553 2019.03

    Research paper (scientific journal), Joint Work, Accepted,  ISSN  02545330

    　View Summary

    © 2018, Springer Science+Business Media, LLC, part of Springer Nature. In this paper, we introduce total dual integrality of the linear complementarity problem (LCP) by analogy with the linear programming problem. The main idea of defining the notion is to propose the LCP with orientation, a variant of the LCP whose feasible complementary cones are specified by an additional input vector. Then we naturally define the dual problem of the LCP with orientation and total dual integrality of the LCP. We show that if the LCP is totally dual integral, then all basic solutions are integral. If the input matrix is sufficient or rank-symmetric, and the LCP is totally dual integral, then our result implies that the LCP always has an integral solution whenever it has a solution. We also introduce a class of matrices such that any LCP instance having the matrix as a coefficient matrix is totally dual integral. We investigate relationships between matrix classes in the LCP literature such as principally unimodular matrices. Principally unimodular matrices are known that all basic solutions to the LCP are integral for any integral input vector. In addition, we show that it is coNP-hard to decide whether a given LCP instance is totally dual integral.

display all >>

Page Top ▲

Reviews, Commentaries, etc. 【 Display / hide 】

  • Combinatorial Optimization for Network Analysis

    垣村 尚徳

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

    Other article, Single Work

  • Shortest Reconfiguration of Perfect Matchings via Alternating Cycles

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

     2019.07

    　View Summary

    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

    　View Summary

    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.

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

    KAKIMURA Naonori

    数理科学    45 - 51 2016.08

    Introduction and explanation (commerce magazine), Single Work

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

    垣村 尚徳

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

    Other article, Single Work,  ISSN  0386-2240

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 】

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

    2020.07
    -
    2022.03

    Osaka University, 岡田 随象, 垣村 尚徳, Challenging Research (Exploratory)

    　View Summary

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

  • Large Graphs: Theory and Algorithms

    2018.06
    -
    2023.03

    National Institute of Informatics, 河原林 健一, 垣村 尚徳, 小林 佑輔, 吉田 悠一, Avis David, Grant-in-Aid for Scientific Research (S)

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

    2017.04
    -
    2021.03

    MEXT,JSPS, Grant-in-Aid for Scientific Research, 垣村　尚徳, Grant-in-Aid for Scientific Research (C), Principal Investigator

    　View Summary

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

Page Top ▲

Awards 【 Display / hide 】

  • 若手優秀講演賞

    2011, 日本応用数理学会

  • 第4回文献賞奨励賞

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

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

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

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

    2008, 情報処理学会

  • 第23回学生論文賞

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

Page Top ▲
 

Courses Taught 【 Display / hide 】

  • MATHEMATICS 1A

    2020

  • INFORMATICS 1

    2020

  • INDEPENDENT STUDY ON FUNDAMENTAL SCIENCE AND TECHNOLOGY

    2020

  • GRADUATE RESEARCH ON FUNDAMENTAL SCIENCE AND TECHNOLOGY 2

    2020

  • GRADUATE RESEARCH ON FUNDAMENTAL SCIENCE AND TECHNOLOGY 1

    2020

display all >>

Page Top ▲

Courses Previously Taught 【 Display / hide 】

  • 数学2A

    Keio University, 2017, Spring Semester

  • 計算機科学同実習

    Keio University, 2017, Autumn Semester

  • 数学1B

    Keio University, 2017, Autumn Semester

  • 計算数学特論

    Keio University, 2017, Spring Semester

Page Top ▲
 

Memberships in Academic Societies 【 Display / hide 】

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

    　

  • 情報処理学会

    　

  • The Japan Society for Industrial and Applied Mathematics

    　
Page Top ▲