List of Publications


Refereed Journal Papers

  1. Than Nguyen Hau, Naonori Kakimura, Ken-ichi Kawarabayashi, Yusuke Kobayashi, Tatsuya Matsuoka, Yu Yokoi,
    Optimal Cache Placement for an Academic Backbone Network,
    Journal of the Operations Research Society of Japan, to appear, 2017.

  2. Takehiro Ito, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi and Yoshio Okamoto,
    Efficient Stabilization of Cooperative Matching Games,
    Theoretical Computer Science, 677, pp.69-82, May 2017.
    DOI:10.1016/j.tcs.2017.03.020

  3. Naonori Kakimura, Ken-ichi Kawarabayashi, and Yusuke Kobayashi,
    Packing Edge-disjoint Odd Eulerian Subgraphs through Prescribed Vertices in 4-edge-connected Graphs,
    SIAM Journal on Discrete Mathematics, 31(2), pp.766-782, 2017.
    DOI:10.1137/15M1022239

  4. Hanna Sumita, Naonori Kakimura and Kazuhisa Makino,
    Parameterized Complexity of Sparse Linear Complementarity Problems,
    Algorithmica, Special Issue dedicated to selected papers from IPEC2015, 79(1), pp.42-65, 2017.
    DOI:10.1007/s00453-016-0229-5

  5. Naonori Kakimura and Ken-ichi Kawarabayashi,
    Coloring Immersion-Free Graphs,
    Journal of Combinatorial Theory, Series B, special issue celebrating its 50th anniversary, 121, pp.284-307, 2016. DOI:10.1016/j.jctb.2016.07.005

  6. Naonori Kakimura and Ken-ichi Kawarabayashi,
    Fixed-Parameter Tractability for Subset Feedback Set Problems with Parity Constraints,
    Theoretical Computer Science, 576, pp.61-76, 2015.
    DOI:10.1016/j.tcs.2015.02.004

  7. Hanna Sumita, Naonori Kakimura and Kazuhisa Makino,
    The Linear Complementarity Problems with a Few Variables per Constraint,
    Mathematics of Operations Research, 40(4), pp.1015-1026, 2015.
    DOI:10.1287/moor.2014.0708

  8. Naonori Kakimura and Mizuyo Takamatsu,
    Matching Problems with Delta-Matroid Constraints,
    SIAM Journal on Discrete Mathematics, 28(2), pp.942-961, 2014.
    DOI:10.1137/110860070

  9. Naonori Kakimura and Kazuhisa Makino,
    Robust Independence Systems,
    SIAM Journal on Discrete Mathematics, 27(3), pp.1257–1273, 2013.
    DOI:10.1137/120899480

  10. Naonori Kakimura and Ken-ichi Kawarabayashi,
    Half-Integral Packing of Odd Cycles through Prescribed Vertices,
    Combinatorica, 33(5), pp.549-572, 2013.
    DOI:10.1007/s00493-013-2865-6

  11. Daishi Aiura, Naonori Kakimura and Kazuo Murota,
    On the Number of Matrices to Generate a Matrix *-Algebra over the Real Field,
    Linear Algebra and Its Applications, 438, pp.1252-1266, 2013.
    DOI:10.1016/j.laa.2012.08.022

  12. Naonori Kakimura and Ken-ichi Kawarabayashi,
    Packing Directed Circuits through Prescribed Vertices Bounded-Fractionally,
    SIAM Journal on Discrete Mathematics, 26(3), pp.1121-1133, 2012.
    DOI:10.1137/100786423

  13. Naonori Kakimura and Ken-ichi Kawarabayashi,
    Packing Cycles through Prescribed Vertices under Modularity Constraints,
    Advances in Applied Mathematics, 49(2), pp.97-110, 2012.
    DOI:10.1016/j.aam.2012.03.002

  14. Naonori Kakimura, Kazuhisa Makino, and Kento Seimi,
    Computing Knapsack Solutions with Cardinality Robustness,
    Japan Journal of Industrial and Applied Mathematics, 29(3), pp.469-483, 2012.
    DOI:10.1007/s13160-012-0075-z

  15. Naonori Kakimura, Ken-ichi Kawarabayashi, and Daniel Marx,
    Packing Cycles through Prescribed Vertices,
    Journal of Combinatorial Theory, Series B, 101, pp. 378-381, 2011.
    DOI:10.1016/j.jctb.2011.03.004

  16. Naonori Kakimura,
    Matching Structure of Symmetric Bipartite Graphs and a Generalization of Polya's Problem,
    Journal of Combinatorial Theory, Series B, 100, pp. 650-670, 2010.
    DOI:10.1016/j.jctb.2010.06.003

  17. Naonori Kakimura,
    A Direct Proof for the Matrix Decomposition of Chordal-Structured Positive Semidefinite Matrices,
    Linear Algebra and Its Applications, 433, pp. 819-823, 2010.
    DOI:10.1016/j.laa.2010.04.012

  18. Naonori Kakimura,
    Sign-Solvable Linear Complementarity Problems,
    Linear Algebra and Its Applications, 429, pp. 606-616, 2008.
    DOI:10.1016/j.laa.2008.03.022

  19. Satoru Iwata and Naonori Kakimura,
    Solving Linear Programs from Sign Patterns,
    Mathematical Programming, 114, pp. 393-418, 2008.
    DOI:10.1007/s10107-007-0107-7

  20. Naonori Kakimura and Satoru Iwata,
    Computing the Inertia from Sign Patterns,
    Mathematical Programming, 110, pp. 229-244, 2007.
    DOI:10.1007/s10107-006-0056-6

Proceedings in Refereed Conferences

  1. Shinji Ito, Daisuke Hatano, Hanna Sumita, Akihiro Yabe, Takuro Fukunaga, Naonori Kakimura, Ken-ichi Kawarabayashi,
    Efficient Sublinear-Regret Algorithms for Online Sparse Linear Regression with Limited Observation,
    NIPS2017 - The 31st Annual Conference on Neural Information Processing Systems, to appear, 2017.

  2. Takehiro Ito, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, Yoshio Okamoto, and Taichi Shiitada,
    Tight Approximability of the Server Allocation Problem for Real-Time Applications,
    ALGOCLOUD2017 - The 3rd International Workshop on Algorithmic Aspects of Cloud Computing, to appear, 2017.

  3. Prompong Pakawanwong, Vorapong Suppakitpaisarn, Liwen Xu, Naonori Kakimura,
    Reducing Recovery Error in Compressive Sensing with Limited Number of Base Stations,
    GLOBECOM 2017 - IEEE Global Communications Conference, to appear, 2017.

  4. Chien-Chung Huang, Naonori Kakimura, and Yuichi Yoshida,
    Streaming Algorithms for Maximizing Monotone Submodular Functions under a Knapsack Constraint,
    APPROX 2017 - The 20th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, 11:1-14, 2017.

  5. Takehiro Ito, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi and Yoshio Okamoto,
    Reconfiguration of Maximum-Weight b-Matchings in a Graph,
    COCOON 2017 - The 23rd Annual International Computing and Combinatorics Conference, Lecture Notes in Computer Science, Vol. 10392, pp.287-296, 2017.

  6. Hanna Sumita, Yuuma Yonebayashi, Naonori Kakimura, Ken-ichi Kawarabayashi,
    An Improved Approximation Algorithm for the Subpath Planning Problem and Its Generalization,
    IJCAI 2017 - The 26th International Joint Conference on Artificial Intelligence, pp.4412-4418, 2017.

  7. Naoto Ohsaka, Yutaro Yamaguchi, Naonori Kakimura, and Ken-ichi Kawarabayashi,
    Maximizing Time-decaying Influence in Social Networks,
    ECML-PKDD 2016 - The European Conference on Machine Learning and Principles and Practice of Knowledge Discovery, pp.132-147, 2016.

  8. Takehiro Ito, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi and Yoshio Okamoto,
    Efficient Stabilization of Cooperative Matching Games,
    AAMAS 2016 - International Conference on Autonomous Agents and Multiagent Systems, pp.41-49, 2016.

  9. Chien-Chung Huang, Naonori Kakimura and Naoyuki Kamiyama,
    Exact and Approximation Algorithms for Weighted Matroid Intersection,
    SODA 2016 - The 27th Annual ACM-SIAM Symposium on Discrete Algorithms, pp.430-444, 2016.

  10. Hanna Sumita, Naonori Kakimura, and Kazuhisa Makino,
    Parameterized Complexity of Sparse Linear Complementarity Problems,
    IPEC 2015 - The 10th International Symposium on Parameterized and Exact Computation, pp.355-364, 2015.
    DOI:10.4230/LIPIcs.IPEC.2015.355

  11. Atsushi Miyauchi, Yuni Iwamasa, Takuro Fukunaga, and Naonori Kakimura,
    Threshold Influence Model for Allocating Advertising Budgets,
    ICML 2015 - The 32nd International Conference on Machine Learning, pp.1395-1404, 2015.
    Proceedings

  12. Chien-Chung Huang, Naonori Kakimura, and Naoyuki Kamiyama,
    Weighted Matroid Intersection Algorithms via Weight Decomposition,
    Proceedings of the 9th Hungarian-Japanese Symposium on Discrete Mathematics and Its Applications, pp.168-176, 2015.

  13. Hanna Sumita, Naonori Kakimura, and Kazuhisa Makino,
    Total Dual Integrality of the Linear Complementarity Problem,
    Proceedings of the 9th Hungarian-Japanese Symposium on Discrete Mathematics and Its Applications, pp.342-351, 2015.

  14. Takehiro Ito, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi and Yoshio Okamoto,
    Minimum-Cost b-Edge Dominating Sets on Trees,
    ISAAC 2014 - The 25th Annual International Symposium on Algorithms and Computation,
    Lecture Notes in Computer Science, 8889, pp.195-207, 2014.
    DOI: 10.1007/978-3-319-13075-0_16

  15. Norie Fu, Vorapong Suppakitpaisarn, Kei Kimura, and Naonori Kakimura,
    Maximum Lifetime Coverage Problems with Battery Recovery Effects,
    GLOBECOM 2014 - IEEE Global Communications Conference, pp.118-124, IEEE Xplore, 2014.

  16. Tasuku Soma, Naonori Kakimura, Kazuhiro Inaba, Ken-ichi Kawarabayashi,
    Optimal Budget Allocation: Theoretical Guarantee and Efficient Algorithm,
    ICML 2014 - The 31st International Conference on Machine Learning, pp.351-359, 2014.
    Proceedings

  17. Hanna Sumita, Naonori Kakimura, and Kazuhisa Makino,
    Sparse Linear Complementarity Problems,
    Proceedings of the 8th Japanese-Hungarian Symposium on Discrete Mathematics and Its Applications, pp.453-462, 2013.

  18. Naonori Kakimura and Ken-ichi Kawarabayashi,
    Packing Edge-Disjoint $K_5$-Immersions in 4-Edge-Connected Graphs,
    Proceedings of the 8th Japanese-Hungarian Symposium on Discrete Mathematics and Its Applications, pp.291-299, 2013.

  19. Hanna Sumita, Naonori Kakimura, and Kazuhisa Makino,
    Sparse Linear Complementarity Problems,
    CIAC 2013 - The 8th International Conference on Algorithms and Complexity,
    Lecture Notes in Computer Science 7878, pp.358-369, 2013.
    DOI: 10.1007/978-3-642-38233-8_30

  20. Naonori Kakimura and Mizuyo Takamatsu,
    Matching Problems with Delta-Matroid Constraints
    CATS 2012 - The 18th CATS symposium (Computing: the Australasian Theory Symposium),
    CRPIT, 128, Mestre, J. Eds., ACS. 83-92, 2012.

  21. Naonori Kakimura, Ken-ichi Kawarabayashi, and Yusuke Kobayashi,
    Erd\H{o}s-P\'osa Property and Its Algorithmic Applications --- Parity Constraints, Subset Feedback Set, and Subset Packing
    SODA 2012 - The 23rd Annual ACM-SIAM Symposium on Discrete Algorithms, pp.1726-1736, 2012.

  22. Naonori Kakimura, Kazuhisa Makino, and Kento Seimi,
    Computing Knapsack Solutions with Cardinality Robustness,
    ISAAC 2011 - The 22nd International Symposium on Algorithms and Computation,
    Lecture Notes in Computer Science 7074, pp.693-702, 2011.
    DOI: 10.1007/978-3-642-25591-5_71

  23. Naonori Kakimura and Kazuhisa Makino,
    Robust Independence Systems,
    ICALP 2011 - The 38th International Colloquium on Automata, Languages and Programming, Track A,
    Lecture Notes in Computer Science 6755, pp.367-378, 2011.
    DOI: 10.1007/978-3-642-22006-7_31

  24. Naonori Kakimura and Ken-ichi Kawarabayashi,
    Packing Cycles of Length 0 Modulo p through Prescribed Vertices
    Proceedings of the 7th Hungarian-Japanese Symposium on Discrete Mathematics and Its Applications, pp.161-169, 2011.

  25. Friedrich Eisenbrand, Naonori Kakimura, Thomas Rothvoss and Laura Sanita,
    Set Covering with Ordered Replacement --- Additive and Multiplicative Gaps.
    IPCO 2011 - The 15th International Conference on Integer Programming and Combinatorial Optimization,
    Lecture Notes in Computer Science 6655, pp.170-182, 2011.
    DOI: 10.1007/978-3-642-20807-2_14

  26. Naonori Kakimura,
    Matching Structure of Symmetric Bipartite Graphs and a Generalization of Polya's Problem.
    Proceedings of the 6th Japanese-Hungarian Symposium on Discrete Mathematics and Its Applications, pp.141-150, 2009.

  27. Naonori Kakimura,
    Sign-Solvable Linear Complementarity Problems.
    IPCO 2007 - The 12th International Conference on Integer Programming and Combinatorial Optimization,
    Lecture Notes in Computer Science (LNCS), Springer-Verlag, 4513, pp.397-409, 2007.

  28. Naonori Kakimura and Satoru Iwata,
    Sign-Solvable Linear Programs.
    Proceedings of the 4th Japanese-Hungarian Symposium on Discrete Mathematics and Its Applications, pp.69-75, 2005.

  29. Naonori Kakimura and Satoru Iwata,
    Computing the Inertia from Sign Patterns.
    IPCO 2005 - The 11th International Conference on Integer Programming and Combinatorial Optimization,
    Lecture Notes in Computer Science (LNCS), Springer-Verlag, 3509, pp.236-248, 2005.

解説記事など

  1. 情報科学と線形代数 --- ネットワーク解析と行列固有値 ---,数理科学,2016年8月号特集「線形代数の探究---様々な問題を通してみるその姿」,pp.45-51,2016年.

  2. 詰め込み問題とグラフマイナー理論,数学セミナー,通巻 627号(53(1)), pp.25-29, 2014-01.

  3. 数理計画と組合せ的行列理論,オペレーションズ・リサーチ, 56, No. 1,pp.21-26,2011年.

Technical Reports

  1. C.-C. Huang, N. Kakimura and N. Kamiyama,
    Exact and approximation algorithms for weighted matroid intersection,
    MI Preprint Series, Mathematics for Industry, Kyushu University, November 2014. [ PDF file ]

  2. H. Sumita, N. Kakimura and K. Makino,
    Total Dual Integrality of the Linear Complementarity Problem,
    Mathematical Engineering Technical Reports METR 2014-25, University of Tokyo, 23pp., September 2014.[ PDF file ]

  3. H. Sumita, N. Kakimura and K. Makino,
    Sparse Linear Complementarity Problems,
    Mathematical Engineering Technical Reports METR 2013-02, University of Tokyo, 20pp., January 2013.[ PDF file ]

  4. D. Aiura, N. Kakimura and K. Murota,
    On the Number of Matrices to Generate a Matrix *-Algebra over the Real Field
    Mathematical Engineering Technical Reports METR 2012-06, University of Tokyo, 15pp., 2012. [ PDF file ]

  5. N. Kakimura and M. Takamatsu,
    Matching Problems with Delta-Matroid Constraints
    Mathematical Engineering Technical Reports METR 2011-41, University of Tokyo, 19pp., 2011. [ PDF file ]

  6. N. Kakimura, K. Makino, and K. Seimi,
    Computing Knapsack Solutions with Cardinality Robustness
    Mathematical Engineering Technical Reports METR 2011-31, University of Tokyo, 12pp., 2011. [ PDF file ]

  7. N. Kakimura and K. Makino
    Robust Independence Systems
    Mathematical Engineering Technical Reports METR 2011-14, University of Tokyo, 19pp., 2011. [ PDF file ]

  8. F. Eisenbrand, N. Kakimura, T. Rothvoss, and L. Sanita
    Set Covering with Ordered Replacement -- Additive and Multiplicative Gaps
    arXiv:1012.3295

  9. N. Kakimura and K. Kawarabayashi
    Packing Directed Circuits through Prescribed Vertices Bounded-Fractionally
    Mathematical Engineering Technical Reports METR 2010-17, University of Tokyo, 12pp., 2010. [ PDF file ]

  10. N. Kakimura, K. Kawarabayashi, and D. Marx
    Packing Cycles through Prescribed Vertices
    Mathematical Engineering Technical Reports METR 2010-16, University of Tokyo, 8pp., 2010. [ PDF file ]

  11. N. Kakimura,
    A Direct Proof for the Matrix Decomposition of Chordal-Structured Positive Semidefinite Matrices by Kim et al.
    Mathematical Engineering Technical Reports METR 2009-13, University of Tokyo, 5pp., 2009. [ PDF file ]

  12. N. Kakimura,
    Matching Structure of Symmetric Bipartite Graphs and a Generalization of Polya's Problem.
    Mathematical Engineering Technical Reports METR 2008-41, University of Tokyo, 27pp., 2008. [ PDF file ]

  13. N. Kakimura,
    Sign-Solvable Linear Complementarity Problems.
    Mathematical Engineering Technical Reports METR 2006-60, University of Tokyo, 11pp., 2006. [ PDF file (revised version) ]

  14. S. Iwata and N. Kakimura,
    Solving Linear Programs from Sign Patterns.
    Mathematical Engineering Technical Reports METR 2006-27, University of Tokyo, 21pp., 2006. [ PDF file ]

  15. N. Kakimura and S. Iwata,
    Computing the Inertia from Sign Patterns.
    Mathematical Engineering Technical Reports METR 2004-42, University of Tokyo, 11pp., 2004. [ PDF file ]

  16. N. Kakimura and Y. Kobayashi,
    On Odd-Cycle-Symmetry of Digraphs.
    Mathematical Engineering Technical Reports METR 2005-36, University of Tokyo, 6pp., 2005. [ PDF file ]