List of Publications


Refereed Journal Papers

  1. Hanna Sumita, Naonori Kakimura, and Kazuhisa Makino,
    Total Dual Integrality of the Linear Complementarity Problem,
    Annals of Operations Research, to appear, 2018.
    DOI:10.1007/s10479-018-2926-8

  2. Takehiro Ito, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi and Yoshio Okamoto,
    Minimum-Cost b-Edge Dominating Sets on Trees,
    Algorithmica, to appear, 2018.
    DOI:10.1007/s00453-018-0448-z

  3. Chien-Chung Huang, Naonori Kakimura and Naoyuki Kamiyama,
    Exact and Approximation Algorithms for Weighted Matroid Intersection,
    Mathematical Programming, Series A, to appear, 2018.
    DOI:10.1007/s10107-018-1260-x

  4. Takehiro Ito, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi and Yoshio Okamoto,
    Reconfiguration of Maximum-Weight b-Matchings in a Graph,
    Journal of Combinatorial Optimization, Special Issue dedicated to selected papers from COCOON2017, to appear, 2018.
    DOI:10.1007/s10878-018-0289-3

  5. Naonori Kakimura and Ken-ichi Kawarabayashi,
    The Erdős-Pósa Property for Edge-Disjoint Immersions in 4-Edge-Connected Graphs,
    Journal of Combinatorial Theory, Series B, Vol.131, pp.138-169, 2018.
    DOI:10.1016/j.jctb.2018.02.003

  6. Norie Fu, Vorapong Suppakitpaisarn, Kei Kimura, and Naonori Kakimura,
    Maximum Lifetime Coverage Problem with Battery Recovery Effect,
    Sustainable Computing, Informatics and Systems, Vol.18, pp.1-13, 2018.
    DOI:10.1016/j.suscom.2018.02.007

  7. 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, Vol.61, No.2, pp.197-216, 2018.
    DOI:10.15807/jorsj.61.197

  8. 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

  9. 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

  10. 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

  11. 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

  12. 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

  13. 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

  14. 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

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

  16. 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

  17. 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

  18. 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

  19. 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

  20. 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

  21. 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

  22. 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

  23. 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

  24. 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

  25. 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

  26. 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. Atsushi Miyauchi and Naonori Kakimura,
    Finding a dense subgraph with sparse cut,
    CIKM 2018 - The 27th ACM International Conference on Information and Knowledge Management, to appear, 2018.

  2. Naonori Kakimura, Naoyuki Kamiyama and Kenjiro Takazawa,
    The b-Branching Problem in Digraphs,
    MFCS2018 - The 43rd International Symposium on Mathematical Foundations of Computer Science, to appear, 2018.

  3. Akihiro Yabe, Daisuke Hatano, Hanna Sumita, Shinji Ito, Naonori Kakimura, Takuro Fukunaga, Ken-ichi Kawarabayashi,
    Causal Bandits with Propagating Inference,
    ICML2018 - The 35th International Conference on Machine Learning, to appear, 2018.

  4. Shinji Ito, Daisuke Hatano, Hanna Sumita, Akihiro Yabe, Takuro Fukunaga, Naonori Kakimura, Ken-ichi Kawarabayashi,
    Online Regression with Partial Information: Generalization and Linear Projection,
    AISTATS2018 - The 21st International Conference on Artificial Intelligence and Statistics, pp.1599-1607, 2018.

  5. Takehiro Ito, Naonori Kakimura and Yusuke Kobayashi,
    Complexity of the Multi-Service Center Problem,
    ISAAC2017 - The 28th International Symposium on Algorithms and Computation,
    Leibniz International Proceedings in Informatics, Vol. 92, pp. 48:1-48:12, 2017.

  6. 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, 4102-4111, 2017.

  7. 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,
    Lecture Notes in Computer Science, Vol. 10739, pp. 41-55, 2018.

  8. 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.

  9. 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.

  10. 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.

  11. 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.

  12. 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.

  13. 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.

  14. 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.

  15. 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

  16. 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

  17. 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.

  18. 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.

  19. 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

  20. 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.

  21. 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

  22. 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.

  23. 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.

  24. 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

  25. 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.

  26. Naonori Kakimura, Ken-ichi Kawarabayashi, and Yusuke Kobayashi,
    Erdős-Pósa 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.

  27. 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

  28. 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

  29. 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.

  30. 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

  31. 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.

  32. 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.

  33. 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.

  34. 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 and N. Kakimura,
    Multi-Pass Streaming Algorithms for Monotone Submodular Function Maximization,
    arXiv:1802.06212

  2. N. Kakimura, N. Kamiyama and K. Takazawa,
    The b-Branching Problem in Digraphs,
    arXiv:1802.02381

  3. 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 ]

  4. 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 ]

  5. 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 ]

  6. 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 ]

  7. 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 ]

  8. 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 ]

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

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

  11. 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 ]

  12. 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 ]

  13. 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 ]

  14. 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 ]

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

  16. 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 ]

  17. 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 ]

  18. 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 ]