List of Publications


Refereed Journal Papers

  1. Takehiro Ito, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, and Yoshio Okamoto,
    Shortest Reconfiguration of Perfect Matchings via Alternating Cycles,
    SIAM Journal on Discrete Mathematics, to appear, 2021.

  2. Kristof Berczi, Naonori Kakimura, and Yusuke Kobayashi,
    Market Pricing for Matroid Rank Valuations,
    SIAM Journal on Discrete Mathematics, 35(4), 2662–2678, 2021.
    DOI:10.1137/20M1386335

  3. Chien-Chung Huang and Naonori Kakimura,
    Multi-Pass Streaming Algorithms for Monotone Submodular Function Maximization,
    Theory of Computing Systems, 66(1), 354–394, 2022.
    DOI:10.1007/s00224-021-10065-6

  4. Chien-Chung Huang, Naonori Kakimura, Simon Mauras, and Yuichi Yoshida,
    Approximability of Monotone Submodular Function Maximization under Cardinality and Matroid Constraints in the Streaming Model,
    SIAM Journal on Discrete Mathematics, to appear, 2021.

  5. Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi and Yoshio Okamoto,
    Submodular Reassignment Problem for Reallocating Agents to Tasks with Synergy Effects,
    Discrete Optimization, to appear, 2021.
    DOI:10.1016/j.disopt.2021.100631

  6. Chien-Chung Huang and Naonori Kakimura,
    Improved Streaming Algorithms for Maximizing Monotone Submodular Functions under a Knapsack Constraint,
    Algorithmica, Volume 83, 879–902, 2021.
    DOI:10.1007/s00453-020-00786-4

  7. Takehiro Ito, Naonori Kakimura and Yusuke Kobayashi,
    Complexity of the Multi-Service Center Problem,
    Theoretical Computer Science, Volume 842, 24, 18-27, 2020.
    DOI:10.1016/j.tcs.2020.07.021

  8. Charles Carlson, Karthekeyan Chandrasekaran, Hsien-Chih Chang, Naonori Kakimura, Alexandra Kolla,
    Spectral Aspects of Symmetric Matrix Signings,
    Discrete Optimization, 37, 100582, 2020.
    DOI:10.1016/j.disopt.2020.100582

  9. Naonori Kakimura, Naoyuki Kamiyama and Kenjiro Takazawa,
    The b-branching problem in digraphs,
    Discrete Applied Mathematics, 283, 565-576, 2020.
    DOI:10.1016/j.dam.2020.02.005

  10. Chien-Chung Huang, Naonori Kakimura, and Yuichi Yoshida,
    Streaming Algorithms for Maximizing Monotone Submodular Functions under a Knapsack Constraint,
    Algorithmica, 82(4), 1006-1032, 2020.
    DOI: 10.1007/s00453-019-00628-y

  11. Hanna Sumita, Naonori Kakimura, and Kazuhisa Makino,
    Total Dual Integrality of the Linear Complementarity Problem,
    Annals of Operations Research, Volume 274, Issue 1-2, pp.531-553, March 2019.
    DOI:10.1007/s10479-018-2926-8

  12. Takehiro Ito, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi and Yoshio Okamoto,
    Minimum-Cost b-Edge Dominating Sets on Trees,
    Algorithmica, Vol.81, Issue 1, pp.343-366, 2019.
    DOI:10.1007/s00453-018-0448-z

  13. Chien-Chung Huang, Naonori Kakimura and Naoyuki Kamiyama,
    Exact and Approximation Algorithms for Weighted Matroid Intersection,
    Mathematical Programming, Series A, Vol.177, Issue 1--2, pp.85-112, 2019.
    DOI:10.1007/s10107-018-1260-x

  14. 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, Vol. 37, Issue 2, pp.454-464, February 2019.
    DOI:10.1007/s10878-018-0289-3

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

  36. 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. Hanna Sumita, Shinji Ito, Kei Takemura, Daisuke Hatano, Takuro Fukunaga, Naonori Kakimura, Ken-ichi Kawarabayashi,
    Online Task Assignment Problems with Reusable Resources,
    AAAI 2022 - the 36th AAAI Conference on Artificial Intelligence, to appear, 2022.

  2. Takehiro Ito, Yuni Iwamasa, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, Yuta Nozaki, Yoshio Okamoto and Kenta Ozeki,
    Reforming an Envy-Free Matching,
    AAAI 2022 - the 36th AAAI Conference on Artificial Intelligence, to appear, 2022.

  3. Takehiro Ito, Yuni Iwamasa, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, Shun-ichi Maezawa, Yuta Nozaki, Yoshio Okamoto, Kenta Ozeki,
    Monotone Edge Flips to an Orientation of Maximum Edge-connectivity \`a la Nash-Williams,
    SODA 2022 - the ACM-SIAM Symposium on Discrete Algorithms, to appear, 2022.

  4. Naonori Kakimura and Donghao Zhu,
    Dynamic Bipartite Matching Market with Arrivals and Departures,
    WINE 2021 - The 17th Conference on Web and Internet Economics, to appear, 2021.

  5. Kei Takemura, Shinji Ito, Daisuke Hatano, Hanna Sumita, Takuro Fukunaga, Naonori Kakimura, Ken-ichi Kawarabayashi,
    A Parameter-Free Algorithm for Misspecified Linear Contextual Bandits,
    AISTATS 2021 - The 24th International Conference on Artificial Intelligence and Statistics, to appear, 2021.

  6. Kei Takemura, Shinji Ito, Daisuke Hatano, Hanna Sumita, Takuro Fukunaga, Naonori Kakimura, Ken-ichi Kawarabayashi,
    Near-Optimal Regret Bounds for Contextual Combinatorial Semi-Bandits with Linear Payoff Functions,
    AAAI 2021 - The 35th AAAI Conference on Artificial Intelligence, to appear, 2021.

  7. Shinji Ito, Daisuke Hatano, Hanna Sumita, Kei Takemura, Takuro Fukunaga, Naonori Kakimura, Ken-ichi Kawarabayashi,
    Delay and Cooperation in Nonstochastic Linear Bandits,
    NeurIPS 2020 - The 34th Conference on Neural Information Processing Systems, 4872-4883, 2020.

  8. Kristóf Bérczi, Naonori Kakimura and Yusuke Kobayashi,
    Market Pricing for Matroid Rank Valuations,
    ISAAC2020 - The 31st International Symposium on Algorithms and Computation, 39:1-39:15, 2020.

  9. Shinji Ito, Daisuke Hatano, Hanna Sumita, Kei Takemura, Takuro Fukunaga, Naonori Kakimura, Ken-ichi Kawarabayashi,
    Oracle-Efficient Algorithms for Online Linear Optimization with Bandit Feedback,
    NeurIPS 2019 - The 33rd Conference on Neural Information Processing Systems, pp.10589-10598, 2019.

  10. Shinji Ito, Daisuke Hatano, Hanna Sumita, Kei Takemura, Takuro Fukunaga, Naonori Kakimura, Ken-ichi Kawarabayashi,
    Improved Regret Bounds for Bandit Combinatorial Optimization,
    NeurIPS 2019 - The 33rd Conference on Neural Information Processing Systems, pp.12027-12036, 2019.

  11. Takehiro Ito, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, Yoshio Okamoto,
    Shortest Reconfiguration of Perfect Matchings via Alternating Cycles,
    ESA 2019 - The 27th Annual European Symposium on Algorithms, 61:1-15, 2019.

  12. Charlie Carlson, Karthekeyan Chandrasekaran, Hsien-Chih Chang, Naonori Kakimura and Alexandra Kolla,
    Spectral Aspects of Symmetric Matrix Signings,
    MFCS 2019 - The 44th International Symposium on Mathematical Foundations of Computer Science, 81:1-13, 2019.

  13. Charalampos E. Tsourakakis, Tianyi Chen, Naonori Kakimura,and Jakub Pachocki,
    Novel Dense Subgraph Discovery Primitives: Risk Aversion and Exclusion Queries,
    ECML-PKDD 2019 - The European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases, accepted, 2019.

  14. Daisuke Hatano, Yuko Kuroki, Yasushi Kawase, Hanna Sumita, Naonori Kakimura and Ken-ichi Kawarabayashi,
    Non-Zero-Sum Stackelberg Budget Allocation Game for Computational Advertising,
    PRICAI2019 - The 16th Pacific Rim International Conference on Artificial Intelligence, LNCS, vol. 11670, pp.568-582, 2019.

  15. Chien-Chung Huang and Naonori Kakimura,
    Improved Streaming Algorithms for Maximizing Monotone Submodular Functions under a Knapsack Constraint,
    WADS 2019 - The Algorithms and Data Structures Symposium, LNCS, vol.11646, pp.438-451, 2019.

  16. Shinji Ito, Daisuke Hatano, Hanna Sumita, Akihiro Yabe, Takuro Fukunaga, Naonori Kakimura, Ken-ichi Kawarabayashi,
    Regret Bounds for Online Portfolio Selection with a Cardinality Constraint,
    NeurIPS 2018 - The 32nd Conference on Neural Information Processing Systems, pp.10588-10597, 2018.

  17. Atsushi Miyauchi and Naonori Kakimura,
    Finding a dense subgraph with sparse cut,
    CIKM 2018 - The 27th ACM International Conference on Information and Knowledge Management, pp.547-556, 2018. DOI:10.1145/3269206.3271720

  18. Naoto Ohsaka, Tomohiro Sonobe, Naonori Kakimura, Takuro Fukunaga, Sumio Fujita, Ken-ichi Kawarabayashi,
    Boosting PageRank Scores by Optimizing Internal Link Structure,
    DEXA2018 - The 29th International Conference on Database and Expert Systems Applications, pp.424-439, 2018.

  19. Naonori Kakimura, Naoyuki Kamiyama and Kenjiro Takazawa,
    The b-Branching Problem in Digraphs,
    MFCS2018 - The 43rd International Symposium on Mathematical Foundations of Computer Science, 117, pp.12:1-12:15, 2018.

  20. 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, pp.5508-5516, 2018.

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

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

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

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

  25. 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, IEEE Xplore, 1-17, 2017.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

  51. 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. 離散数学入門 --- グラフ,マトロイドから離散凸解析まで ---, 数理科学,2021年12月号特集「離散数学に親しむ」,2021年.

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

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

  4. 数理計画と組合せ的行列理論,オペレーションズ・リサーチ, 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 ]