PEAK Staff Profile

Naonori Kakimura, MS, PhD (U. Tokyo)
Lecturer – Environmental Sciences

Contact : kakimura[at]


Naonori Kakimura Before joining the PEAK team at the University of Tokyo, Prof. Kakimura worked as an assistant professor (jokyo) at Department of Mathematical Informatics, Graduate School of Information Science and Technology, the University of Tokyo, for four years. He holds a B.S. in Engineering (March 2003), a M.S. and a Ph.D. in Information Science and Technology from the University of Tokyo (March 2005; March 2008). Results in his Ph.D. thesis received an award for an outstanding paper by a young researcher (Bunken-sho Shorei-sho) from Operations Research Society of Japan in 2009.

Research Interests

Prof. Kakimura’s research interests center on optimization theory for engineering applications. In particular, he is interested in developing efficient algorithms for solving optimization problems with combinatorial structures such as graphs and networks. His research topics are also related to discrete mathematics, graph algorithms, and combinatorial matrix theory. He is a member of the Operations Research Society of Japan, Japan Society for Industrial and Applied Mathematics, and Information Processing Society of Japan.

Selected Publications

“Erdős-Pósa Property and Its Algorithmic Applications --- Parity Constraints, Subset Feedback Set, and Subset Packing,” N. Kakimura, K. Kawarabayashi, and Y. Kobayashi, Proc. the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2012), pp. 1726-1736, 2012.
“Robust Independence Systems,” N. Kakimura and K. Makino, Proc. the 38th International Colloquium on Automata, Languages and Programming (ICALP 2011), Lecture Notes in Computer Science 6755, pp.367-378, 2011.
“Packing Cycles through Prescribed Vertices,” N. Kakimura, K. Kawarabayashi, and D. Marx, Journal of Combinatorial Theory, Series B, 101, pp.378-381, 2011.
“Matching Structure of Symmetric Bipartite Graphs and a Generalizaiton of Pólya’s Problem,” N. Kakimura, Journal of Combinational Theory, Series B, 100, pp. 650-670, 2010.
“Solving Linear Programs from Sign Patterns,” S. Iwata and N. Kakimura, Mathematical Programming, 114, pp. 393-418, 2008.