Naonori Kakimura

Profile Information

Affiliation: 理工学部数理科学科, 慶應義塾大学

J-GLOBAL ID: 201101075193410550
researchmap Member ID: B000000370

External link: https://opt.math.keio.ac.jp/kakimura/

Research Interests

Research Areas

Informatics / Mathematical informatics /

Papers

105

Bandit Task Assignment with Unknown Processing Time.

Shinji Ito, Daisuke Hatano, Hanna Sumita, Kei Takemura, Takuro Fukunaga, Naonori Kakimura, Ken-ichi Kawarabayashi

NeurIPS, 2023
Algorithmic Theory of Qubit Routing.

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

WADS, 533-546, 2023
Algorithmic Theory of Qubit Routing.

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

CoRR, abs/2305.02059, 2023
Hardness of Finding Combinatorial Shortest Paths on Graph Associahedra.

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

CoRR, abs/2304.14782, 2023
Hardness of Finding Combinatorial Shortest Paths on Graph Associahedra.

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

ICALP, 82-17, 2023
Rerouting Planar Curves and Disjoint Paths.

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

ICALP, 81-19, 2023
On Reachable Assignments Under Dichotomous Preferences

Takehiro Ito, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, Yuta Nozaki, Yoshio Okamoto, Kenta Ozeki

PRIMA 2022: Principles and Practice of Multi-Agent Systems, abs/2209.10262 650-658, 2023
Reforming an Envy-Free Matching

Takehiro Ito, Yuni Iwamasa, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, Yuta Nozaki, Yoshio Okamoto, Kenta Ozeki

Proceedings of the AAAI Conference on Artificial Intelligence, 36(5) 5084-5091, Jun 28, 2022
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) 1102-1123, Jun, 2022
A Parameterized View to the Robust Recoverable Base Problem of Matroids Under Structural Uncertainty

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

Operations Research Letters, 50(3) 370-375, May, 2022
On Reachable Assignments under Dichotomous Preferences.

Takehiro Ito, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi 0001, Yuta Nozaki, Yoshio Okamoto, Kenta Ozeki

CoRR, abs/2209.10262 650-658, 2022
Reforming an Envy-Free Matching.

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

CoRR, abs/2207.02641, 2022
Rerouting Planar Curves and Disjoint Paths.

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

CoRR, abs/2210.11778, 2022
Approximability of Monotone Submodular Function Maximization under Cardinality and Matroid Constraints in the Streaming Model.

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

SIAM J. Discret. Math., 36(1) 355-382, 2022
Online Task Assignment Problems with Reusable Resources.

Hanna Sumita, Shinji Ito, Kei Takemura, Daisuke Hatano, Takuro Fukunaga, Naonori Kakimura, Ken-ichi Kawarabayashi

AAAI, 5199-5207, 2022
Online Task Assignment Problems with Reusable Resources.

Hanna Sumita, Shinji Ito, Kei Takemura, Daisuke Hatano, Takuro Fukunaga, Naonori Kakimura, Ken-ichi Kawarabayashi

CoRR, abs/2203.07605, 2022
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

SODA, 1342-1355, 2022
Multi-Pass Streaming Algorithms for Monotone Submodular Function Maximization.

Chien-Chung Huang, Naonori Kakimura

Theory Comput. Syst., 66(1) 354-394, 2022
Submodular reassignment problem for reallocating agents to tasks with synergy effects

Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, Yoshio Okamoto

Discrete Optimization, 44(Part) 100631-100631, Feb, 2021
Dynamic Bipartite Matching Market with Arrivals and Departures.

Naonori Kakimura, Donghao Zhu

WINE, 544-544, 2021

Misc.

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

垣村尚徳

数理科学, 59(12) 22-29, Dec, 2021
Combinatorial Optimization for Network Analysis

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

垣村尚徳

数理科学, 54(8) 45-51, Aug, 2016
ネットワーク型交渉ゲームの安定化アルゴリズム

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

情報処理学会研究報告(Web), 2016(AL-157) VOL.2016‐AL‐157,NO.3 (WEB ONLY), Feb 28, 2016
イマージョンを含まないグラフに対する彩色アルゴリズム

垣村尚徳, 河原林健一, 河原林健一

日本応用数理学会年会講演予稿集(CD-ROM), 2016 ROMBUNNO.9GATSU13NICHI,11:00,3E,3, 2016
広告予算配分に対する閾値影響モデル

宮内敦史, 岩政勇仁, 福永拓郎, 垣村尚徳

日本オペレーションズ・リサーチ学会秋季研究発表会アブストラクト集, 2015 24-25, Sep 10, 2015
重み付きマトロイド交わり問題に対する厳密解法と近似解法

HUANG Chien‐Chung, 垣村尚徳, 神山直之

日本オペレーションズ・リサーチ学会秋季研究発表会アブストラクト集, 2015 174-175, Sep 10, 2015
1-A-10 広告予算配分に対する閾値影響モデル(離散最適化(2))

宮内敦史, 岩政勇仁, 福永拓郎, 垣村尚徳

日本オペレーションズ・リサーチ学会秋季研究発表会アブストラクト集, 2015 24-25, Sep 10, 2015
2-A-4 重み付きマトロイド交わり問題に対する厳密解法と近似解法(離散最適化(3))

黄建中, 垣村尚徳, 神山直之

日本オペレーションズ・リサーチ学会秋季研究発表会アブストラクト集, 2015 174-175, Sep 10, 2015
学術情報ネットワークにおける最適キャッシュ配置

横井優, NGUYEN Hau Than, 松岡達也, 小林佑輔, 垣村尚徳, 河原林健一

日本応用数理学会年会講演予稿集(CD-ROM), 2015 ROMBUNNO.9GATSU9NICHI,09:30,A,2, Sep 2, 2015
木における最小費用b‐辺支配集合問題

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

日本オペレーションズ・リサーチ学会春季研究発表会アブストラクト集, 2015 44-45, Mar 26, 2015
線形相補性問題のパラメータ化計算量

澄田範奈, 垣村尚徳, 牧野和久

日本オペレーションズ・リサーチ学会春季研究発表会アブストラクト集, 2015 38-39, Mar 26, 2015
1-B-13 線形相補性問題のパラメータ化計算量(学生セッション:離散最適化(3))

澄田範奈, 垣村尚徳, 牧野和久

日本オペレーションズ・リサーチ学会春季研究発表会アブストラクト集, 2015 38-39, Mar 26, 2015
1-C-3 木における最小費用b-辺支配集合問題(離散最適化(1))

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

日本オペレーションズ・リサーチ学会春季研究発表会アブストラクト集, 2015 44-45, Mar 26, 2015
Minimum-Cost b-Edge Dominating Sets on Trees

IPSJ SIG Notes, 2015(2) 1-6, Feb 24, 2015
線形相補性問題のパラメータ化計算量

澄田範奈, 垣村尚徳, 牧野和久

電子情報通信学会大会講演論文集(CD-ROM), 2015 ROMBUNNO.DS-1-13, Feb 24, 2015
DS-1-13 Parameterized Complexity of the Linear Complementarity Problem

Sumita Hanna, Kakimura Naonori, Makino Kazuhisa

Proceedings of the IEICE General Conference, 2015(1) "S-25"-"S-26", Feb 24, 2015
方向つき線形相補性問題の計算複雑度

澄田範奈, 垣村尚徳, 牧野和久

日本オペレーションズ・リサーチ学会秋季研究発表会アブストラクト集, 2014 54-55, Aug 28, 2014
1-C-11 方向つき線形相補性問題の計算複雑度(離散最適化(3))

澄田範奈, 垣村尚徳, 牧野和久

日本オペレーションズ・リサーチ学会秋季研究発表会アブストラクト集, 2014 54-55, Aug 28, 2014
1-G-10 線形相補性問題の完全双対整数性(離散最適化(2))

澄田範奈, 垣村尚徳, 牧野和久

日本オペレーションズ・リサーチ学会春季研究発表会アブストラクト集, 2014 132-133, Mar 6, 2014

Research Projects

Graph Algorithms and Optimization: Theory and Scalable Algorithms

Grants-in-Aid for Scientific Research, Grant-in-Aid for Scientific Research (S), Japan Society for the Promotion of Science, Apr, 2022 - Mar, 2027
Theory and algorithms for combinatorial optimization under uncertainty

Grants-in-Aid for Scientific Research Grant-in-Aid for Scientific Research (B), Grant-in-Aid for Scientific Research (B), Japan Society for the Promotion of Science, Apr, 2021 - Mar, 2026
Development of Combinatorial Reconfiguration by Mathematics Approach: From Examples to New Methods

Grants-in-Aid for Scientific Research Grant-in-Aid for Transformative Research Areas (B), Grant-in-Aid for Transformative Research Areas (B), Japan Society for the Promotion of Science, Oct, 2020 - Mar, 2023
Large Graphs: Theory and Algorithms

Grants-in-Aid for Scientific Research Grant-in-Aid for Scientific Research (S), Grant-in-Aid for Scientific Research (S), Japan Society for the Promotion of Science, Jun, 2018 - Mar, 2023
Re-annotation of large-scale human genome data by integration of statistical genetics and operations research

Grants-in-Aid for Scientific Research, Grant-in-Aid for Challenging Research (Exploratory), Japan Society for the Promotion of Science, Jul, 2020 - Mar, 2022

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

科学研究費助成事業基盤研究(C), 基盤研究(C), 日本学術振興会, Apr, 2017 - Mar, 2021

垣村尚徳
Designing Efficient Algorithms for Optimization Problems with Combinatorial Structures

Grants-in-Aid for Scientific Research Grant-in-Aid for Young Scientists (B), Grant-in-Aid for Young Scientists (B), Japan Society for the Promotion of Science, Apr, 2013 - Mar, 2017

KAKIMURA Naonori
Exploring the limits of computation from mathematical logic

Grants-in-Aid for Scientific Research Grant-in-Aid for Scientific Research on Innovative Areas (Research in a proposed research area), Grant-in-Aid for Scientific Research on Innovative Areas (Research in a proposed research area), Japan Society for the Promotion of Science, Jun, 2012 - Mar, 2017

Makino Kazuhisa, COOK Stephen, ZIEGLER Martin, GURVICH Vladimir, BOROS Endre
Unified Optimization Theory by Discrete Convex Paradigm

Grants-in-Aid for Scientific Research Grant-in-Aid for Scientific Research (B), Grant-in-Aid for Scientific Research (B), Japan Society for the Promotion of Science, Apr, 2009 - Mar, 2015

MUROTA Kazuo, TAMURA Akihisa, IWATA Satoru, SHIOURA Akiyoshi, MORIGUCHI Satoko, KAKIMURA Naonori, KOBAYASHI Yusuke, TSUCHIMURA Nobuyuki
Structural Analysis of Mathematical Programming based on CombinatorialMatrix Theory

Grants-in-Aid for Scientific Research Grant-in-Aid for Young Scientists (B), Grant-in-Aid for Young Scientists (B), Japan Society for the Promotion of Science, 2009 - 2011

KAKIMURA Naonori
組合せ的行列理論に基づく最適化手法の設計

科学研究費助成事業特別研究員奨励費, 特別研究員奨励費, 日本学術振興会, 2007 - 2008

垣村尚徳

Profile Information

Research Interests

Research Areas

Papers

Misc.

Research Projects

Menu

Coauthors

Following