Research Papers by Naoyuki Kamiyama

▲ = Peer-reviewed journal papers (they could be the journal versions of conference papers)
△ = Peer-reviewed conference papers (especially, in SODA, AAMAS, AAAI, LNCS, LIPIcs, CRPIT, and CCIS)

  1. Takehiro Ito, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, Yoshio Okamoto
    Algorithmic Theory of Qubit Routing in the Linear Nearest Neighbor Architectures
    ▲ ACM Transactions on Quantum Computing, accepted.
    △ 18th Algorithms and Data Structures Symposium (WADS), LNCS 14079, 533-546, 2023.
  2. Naoyuki Kamiyama
    The Minimum-Cost Dynamic Flow Problem in a Fixed Graph with a Constant Target Flow Value
    ▲ Networks, accepted.
  3. Takehiro Ito, Yuni Iwamasa, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, Yuta Nozaki, Yoshio Okamoto, Kenta Ozeki
    Reforming an Envy-Free Matching
    ▲ Algorithmica, accepted.
    △ 36th AAAI Conference on Artificial Intelligence (AAAI), 5084-5091, 2022.
  4. Naoyuki Kamiyama
    Super-Stable Common Independent Sets of Generalized Matroids
    ▲ Operations Research Letters, 60:107248, 2025.
  5. Naoyuki Kamiyama
    Modifying an Instance of the Super-Stable Matching Problem
    ▲ Information Processing Letters, 189:106549, 2025.
  6. Ayumi Igarashi, Naoyuki Kamiyama, Warut Suksompong, Yuen Sheung Man
    Reachability of Fair Allocations via Sequential Exchanges
    ▲ Algorithmica, 86:3653-3683, 2024.
    △ 38th AAAI Conference on Artificial Intelligence (AAAI), 9773-9780, 2024.
  7. Kristóf Bérczi, Erika Bérczi-Kovács, Endre Boros, Fekadu Tolessa Gedefa, Naoyuki Kamiyama, Telikepalli Kavitha, Yusuke Kobayashi, Kazuhisa Makino
    Envy-free Relaxations for Goods, Chores, and Mixed Items
    ▲ Theoretical Computer Science, 1002:114596, 2024.
  8. Naoyuki Kamiyama
    A Note on Robust Subsets of Transversal Matroids
    ▲ Journal of the Operations Research Society of Japan, 67(2):37-45, 2024.
  9. Takasugu Shigenobu and Naoyuki Kamiyama
    On Connectedness of Solutions to Integer Linear Systems
    △ 16th Annual International Conference on Combinatorial Optimization and Applications (COCOA), LNCS 14461, 421-433, 2023.
  10. Takehiro Ito, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, Yuta Nozaki, Yoshio Okamoto, Kenta Ozeki
    On Reachable Assignments under Dichotomous Preferences
    ▲ Theoretical Computer Science, 979:114196, 2023.
    △ 24th International Conference on Principles and Practice of Multi-Agent Systems (PRIMA), LNCS 13753, 650-658, 2022.
  11. Naoyuki Kamiyama
    On Optimization Problems in Acyclic Hypergraphs
    ▲ Information Processing Letters, 182:106390, 2023.
  12. Takehiro Ito, Yuni Iwamasa, Naoyuki Kamiyama, Yasuaki Kobayashi, Yusuke Kobayashi, Shun-ichi Maezawa, Akira Suzuki
    Reconfiguration of Time-Respecting Arborescences
    △ 18th Algorithms and Data Structures Symposium (WADS), LNCS 14079, 521-532, 2023.
  13. Takehiro Ito, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, Shun-ichi Maezawa, Yuta Nozaki, Yoshio Okamoto
    Hardness of Finding Combinatorial Shortest Paths on Graph Associahedra
    △ 50th EATCS International Colloquium on Automata, Languages and Programming (ICALP), LIPIcs 261, 82:1-82:17, 2023.
  14. Masataka Shirahashi and Naoyuki Kamiyama
    Kernelization Algorithms for a Generalization of the Component Order Connectivity Problem
    ▲ Journal of the Operations Research Society of Japan, 66(2):112-129, 2023.
  15. Naoyuki Kamiyama
    Pareto Efficient Matchings with Pairwise Preferences
    ▲ Theoretical Computer Science, 948:113707, 2023.
  16. 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 à la Nash-Williams
    ▲ ACM Transactions on Algorithms, 19(1):6:1-6:22, 2023.
    △ 2022 Annual ACM/SIAM Symposium on Discrete Algorithms (SODA), 1342-1355, 2022.
  17. Naoyuki Kamiyama
    A Matroid Generalization of the Super-Stable Matching Problem
    ▲ SIAM Journal on Discrete Mathematics, 36(2):1467-1482, 2022.
  18. Takehiro Ito, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, Yoshio Okamoto
    Shortest Reconfiguration of Perfect Matchings via Alternating Cycles
    ▲ SIAM Journal on Discrete Mathematics, 36(2):1102-1123, 2022.
    △ 27th Annual European Symposium on Algorithms (ESA), LIPIcs 144, 61:1-61:15, 2019.
  19. Takehiro Ito, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, Yoshio Okamoto
    A Parameterized View to the Robust Recoverable Base Problem of Matroids under Structural Uncertainty
    ▲ Operations Research Letters, 50:370-375, 2022.
  20. Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, Yoshio Okamoto
    Submodular Reassignment Problem for Reallocating Agents to Tasks with Synergy Effects
    ▲ Discrete Optimization, 44:100631, 2022.
  21. Hiroaki Yamada, Masataka Shirahashi, Naoyuki Kamiyama, Yumeka Nakajima
    MAS Network: Surrogate Neural Network for Multi-Agent Simulation
    △ 22nd International Workshop on Multi-Agent-Based Simulation (MABS), LNCS 13128, 113-124, 2022.
  22. Naoyuki Kamiyama
    The Envy-Free Matching Problem with Pairwise Preferences
    ▲ Information Processing Letters, 172:106158, 2021.
  23. Naoyuki Kamiyama
    Envy-Free Matchings with One-Sided Preferences and Matroid Constraints
    ▲ Operations Research Letters, 49(5):790-794, 2021.
  24. Naoyuki Kamiyama, Pasin Manurangsi, Warut Suksompong
    On the Complexity of Fair House Allocation
    ▲ Operations Research Letters, 49(4):572-577, 2021.
  25. Takehiro Ito, Naoyuki Kamiyama, Yusuke Kobayashi, Yoshio Okamoto
    Algorithms for Gerrymandering over Graphs
    ▲ Theoretical Computer Science, 868(8):30-45, 2021.
    △ 18th International Conference on Autonomous Agents and Multiagent Systems (AAMAS), 1413-1421, 2019.
  26. Hiroaki Yamada and Naoyuki Kamiyama
    Optimal Control of Pedestrian Flows by Congestion Forecasts Satisfying User Equilibrium Conditions
    △ 23rd International Conference on Principles and Practice of Multi-Agent Systems (PRIMA), LNCS 12568, 299-314, 2021.
  27. Naonori Kakimura, Naoyuki Kamiyama, Kenjiro Takazawa
    The b-Branching Problem in Digraphs
    ▲ Discrete Applied Mathematics, 283:565-576, 2020.
    △ 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS), LIPIcs 117, 12:1-12:15, 2018.
  28. Naoyuki Kamiyama
    The Distance-Constrained Matroid Median Problem
    ▲ Algorithmica, 82(7):2087-2106, 2020.
  29. Naoyuki Kamiyama
    On Stable Matchings with Pairwise Preferences and Matroid Constraints
    △ 19th International Conference on Autonomous Agents and Multiagent Systems (AAMAS), 584-592, 2020.
  30. Naoyuki Kamiyama
    Popular Matchings with Two-Sided Preference Lists and Matroid Constraints
    ▲ Theoretical Computer Science, 809:265-276, 2020.
  31. Naoyuki Kamiyama
    Lexicographically Optimal Earliest Arrival Flows
    ▲ Networks, 75(1):18-33, 2020.
  32. Naoyuki Kamiyama
    Discrete Newton Methods for the Evacuation Problem
    ▲ Theoretical Computer Science, 795:510-519, 2019.
  33. Akifumi Kira, Naoyuki Kamiyama, Hirokazu Anai, Hiroaki Iwashita, Kotaro Ohori
    On Dynamic Patrolling Security Games
    ▲ Journal of the Operations Research Society of Japan, 62(4):152-168, 2019.
  34. Chien-Chung Huang, Naonori Kakimura, Naoyuki Kamiyama
    Exact and Approximation Algorithms for Weighted Matroid Intersection
    ▲ Mathematical Programming, Series A, 177(1-2):85-112, 2019.
    △ 27th Annual ACM/SIAM Symposium on Discrete Algorithms (SODA), 430-444, 2016.
  35. Naoyuki Kamiyama
    Many-to-Many Stable Matchings with Ties, Master Preference Lists, and Matroid Constraints
    △ 18th International Conference on Autonomous Agents and Multiagent Systems (AAMAS), 583-591, 2019.
  36. Naoyuki Kamiyama
    A Note on Balanced Flows in Equality Networks
    ▲ Information Processing Letters, 145:74-76, 2019.
  37. Susumu Kawanaka and Naoyuki Kamiyama
    An Improved Algorithm for Testing Substitutability of Weak Preferences
    ▲ Mathematical Social Sciences, 99:1-4, 2019.
  38. Takehiro Ito, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, Yoshio Okamoto
    Reconfiguration of Maximum-Weight b-Matchings in a Graph
    ▲ Journal of Combinatorial Optimization, 37(2):454-464, 2019.
    △ 23rd Annual International Computing and Combinatorics Conference (COCOON), LNCS 10392, 287-296, 2017.
  39. Takehiro Ito, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, Yoshio Okamoto
    Minimum-Cost b-Edge Dominating Sets on Trees
    ▲ Algorithmica, 81(1):343-366, 2019.
    △ 25th International Symposium on Algorithms and Computation (ISAAC), LNCS 8889, 195-207, 2014.
  40. Naoyuki Kamiyama
    Pareto Stable Matchings under One-Sided Matroid Constraints
    ▲ SIAM Journal on Discrete Mathematics, 33(3):1431-1451, 2019.
  41. Takashi Ishizuka and Naoyuki Kamiyama
    On the Complexity of Stable Fractional Hypergraph Matching
    △ 29th International Symposium on Algorithms and Computation (ISAAC), LIPIcs 123, 11:1-11:12, 2018.
  42. Yosuke Hanawa, Yuya Higashikawa, Naoyuki Kamiyama, Naoki Katoh, Atsushi Takizawa
    The Mixed Evacuation Problem
    ▲ Journal of Combinatorial Optimization, 36(4):1299-1314, 2018.
    △ 10th Annual International Conference on Combinatorial Optimization and Applications (COCOA), LNCS 10043, 18-32, 2016.
  43. Naoyuki Kamiyama
    A Note on Submodular Function Minimization with Covering Type Linear Constraints
    ▲ Algorithmica, 80(10):2957-2971, 2018.
  44. Naoyuki Kamiyama
    Submodular Function Minimization with Submodular Set Covering Constraints and Precedence Constraints
    △ 15th Workshop on Approximation and Online Algorithms (WAOA), LNCS 10787, 90-101, 2018.
  45. Takehiro Ito, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, Yoshio Okamoto, Taichi Shiitada
    Tight Approximability of the Server Allocation Problem for Real-Time Applications
    △ 3rd International Workshop on Algorithmic Aspects of Cloud Computing (Algocloud), LNCS 10739, 41-55, 2018.
  46. Naoyuki Kamiyama
    A Characterization of Weighted Popular Matchings under Matroid Constraints
    ▲ Journal of the Operations Research Society of Japan, 61(1):2-17, 2018.
  47. Hiroaki Yamada, Kotaro Ohori, Tadashige Iwao, Akifumi Kira, Naoyuki Kamiyama, Hiroaki Yoshida, Hirokazu Anai
    Modeling and Managing Airport Passenger Flow under Uncertainty: A Case of Fukuoka Airport in Japan
    △ 9th International Conference on Social Informatics (SocInfo), LNCS 10540, 419-430, 2017.
  48. Takehiro Ito, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, Yoshio Okamoto
    Efficient Stabilization of Cooperative Matching Games
    ▲ Theoretical Computer Science, 677:69-82, 2017.
    △ 15th International Joint Conference on Autonomous Agents and Multi-Agent Systems (AAMAS), 41-49, 2016.
  49. Naoyuki Kamiyama
    Strategic Issues in College Admissions with Score-Limits
    ▲ Operations Research Letters, 45:105-108, 2017.
  50. Naoyuki Kamiyama
    A Note on the Submodular Vertex Cover Problem with Submodular Penalties
    ▲ Theoretical Computer Science, 659:95-97, 2017.
  51. Naoyuki Kamiyama
    Popular Matchings with Ties and Matroid Constraints
    ▲ SIAM Journal on Discrete Mathematics, 31(3):1801-1819, 2017.
  52. Naoyuki Kamiyama
    The Popular Matching and Condensation Problems under Matroid Constraints
    ▲ Journal of Combinatorial Optimization, 32(4):1305-1326, 2016.
    △ 8th Annual International Conference on Combinatorial Optimization and Applications (COCOA), LNCS 8881, 713-728, 2014.
  53. Satoru Iwata, Naoyuki Kamiyama, Naoki Katoh, Shuji Kijima, Yoshio Okamoto
    Extended Formulations for Sparsity Matroids
    ▲ Mathematical Programming, Series A, 158(1):565-574, 2016.
  54. Keita Nakamura and Naoyuki Kamiyama
    Many-to-Many Stable Matchings with Ties in Trees
    ▲ Journal of the Operations Research Society of Japan, 59(3):225-240, 2016.
  55. Tamás Fleiner and Naoyuki Kamiyama
    A Matroid Approach to Stable Matchings with Lower Quotas
    ▲ Mathematics of Operations Research, 41(2):734-744, 2016.
    △ 23rd Annual ACM/SIAM Symposium on Discrete Algorithms (SODA), 135-142, 2012.
  56. Naoyuki Kamiyama
    Stable Matchings with Ties, Master Preference Lists, and Matroid Constraints
    △ 8th International Symposium on Algorithmic Game Theory (SAGT), LNCS 9347, 3-14, 2015.
  57. Naoyuki Kamiyama and Yasushi Kawase
    On Packing Arborescences in Temporal Networks
    ▲ Information Processing Letters, 115:321-325, 2015.
  58. Naoyuki Kamiyama
    The Nucleolus of Arborescence Games in Directed Acyclic Graphs
    ▲ Operations Research Letters, 43:89-92, 2015.
  59. Naoyuki Kamiyama and Naoki Katoh
    The Universally Quickest Transshipment Problem in a Certain Class of Dynamic Networks with Uniform Path-Lengths
    ▲ Discrete Applied Mathematics, 178:89-100, 2014.
    △ 20th International Symposium on Algorithms and Computation (ISAAC), LNCS 5878, 802-811, 2009.
  60. Yuya Higashikawa, Naoyuki Kamiyama, Naoki Katoh, Yuki Kobayashi
    An Inductive Construction of Minimally Rigid Body-Hinge Simple Graphs
    ▲ Theoretical Computer Science, 556:2-12, 2014.
    △ 7th Annual International Conference on Combinatorial Optimization and Applications (COCOA), LNCS 8287, 165-177, 2013.
  61. Naoyuki Kamiyama
    A New Approach to the Pareto Stable Matching Problem
    ▲ Mathematics of Operations Research, 39(3):851-862, 2014.
  62. Naoyuki Kamiyama
    Arborescence Problems: Theorems and Algorithms
    ▲ Interdisciplinary Information Sciences, 20(1):51-70, 2014.
  63. Yusuke Matsumoto, Naoyuki Kamiyama, Keiko Imai
    On Total Unimodularity of Edge-Edge Adjacency Matrices
    ▲ Algorithmica, 67(2):277-292, 2013.
    △ 17th Annual International Computing and Combinatorics Conference (COCOON), LNCS 6842, 354-365, 2011.
  64. Naoyuki Kamiyama
    A Note on the Serial Dictatorship with Project Closures
    ▲ Operations Research Letters, 41:559-561, 2013.
  65. Naoyuki Kamiyama
    Matroid Intersection with Priority Constraints
    ▲ Journal of the Operations Research Society of Japan, 56(1):15-25, 2013.
  66. András Frank, Satoru Fujishige, Naoyuki Kamiyama, Naoki Katoh
    Independent Arborescences in Directed Graphs
    ▲ Discrete Mathematics, 313(4):453-459, 2013.
  67. Naoyuki Kamiyama
    A Note on the Quasi-Additive Bound for Boolean Functions
    ▲ Journal of Math-for-Industry, 4-B:119-122, 2012.
  68. Naoyuki Kamiyama
    Robustness of Minimum Cost Arborescences
    ▲ Japan Journal of Industrial and Applied Mathematics, 29(3):485-497, 2012.
    △ 22nd International Symposium on Algorithms and Computation (ISAAC), LNCS 7074, 130-139, 2011.
  69. Satoru Fujishige and Naoyuki Kamiyama
    The Root Location Problem for Arc-Disjoint Arborescences
    ▲ Discrete Applied Mathematics, 160(13-14):1964-1970, 2012.
  70. Yuichiro Yasui, Katsuki Fujisawa, Kazushige Goto, Naoyuki Kamiyama, Mizuyo Takamatsu
    NETAL: High-Performance Implementation of Network Analysis Library Considering Computer Memory Hierarchy
    ▲ Journal of the Operations Research Society of Japan, 54(4):259-280, 2011.
  71. Naoyuki Kamiyama
    Submodular Function Minimization under a Submodular Set Covering Constraint
    △ 8th Annual Conference on Theory and Applications of Models of Computation (TAMC), LNCS 6648, 133-141, 2011.
  72. Yusuke Matsumoto, Naoyuki Kamiyama, Keiko Imai
    An Approximation Algorithm Dependent on Edge-Coloring Number for Minimum Maximal Matching Problem
    ▲ Information Processing Letters, 111(10):465-468, 2011.
  73. Yutaka Iwaikawa, Naoyuki Kamiyama, Tomomi Matsui
    Improved Approximation Algorithms for Firefighter Problem on Trees
    ▲ IEICE Transactions on Information and Systems, E94-D(2):196-199, 2011.
  74. Naoyuki Kamiyama and Tomomi Matsui
    Approximation Algorithms for Data Association Problem Arising from Multitarget Tracking
    △ 17th Computing: the Australasian Theory Symposium (CATS), CRPIT 119, 137-144, 2011.
  75. Naoyuki Kamiyama and Naoki Katoh
    Covering Directed Graphs by In-Trees
    ▲ Journal of Combinatorial Optimization, 21(1):2-18, 2011.
    △ 14th Annual International Computing and Combinatorics Conference (COCOON), LNCS 5092, 444-457, 2008.
  76. Naoyuki Kamiyama
    The Prize-Collecting Edge Dominating Set Problem in Trees
    △ 35th International Symposium on Mathematical Foundations of Computer Science (MFCS), LNCS 6281, 465-476, 2010.
  77. Kristóf Bérczi, Satoru Fujishige, Naoyuki Kamiyama
    A Linear-Time Algorithm to Find a Pair of Arc-Disjoint Spanning In-Arborescence and Out-Arborescence in a Directed Acyclic Graph
    ▲ Information Processing Letters, 109(23-24):1227-1231, 2009.
  78. Naoyuki Kamiyama, Naoki Katoh, Atsushi Takizawa
    An Efficient Algorithm for the Evacuation Problem in a Certain Class of Networks with Uniform Path-lengths
    ▲ Discrete Applied Mathematics, 157(17):3665-3677, 2009.
    △ 3rd International Conference on Algorithmic Aspect in Information and Management (AAIM), LNCS 4508, 178-190, 2007.
  79. Naoyuki Kamiyama, Naoki Katoh, Atsushi Takizawa
    Arc-Disjoint In-Trees in Directed Graphs
    ▲ Combinatorica, 29(2):197-214, 2009.
    △ 19th Annual ACM/SIAM Symposium on Discrete Algorithms (SODA), 518-526, 2008.
  80. Naoyuki Kamiyama, Yuuki Kiyonari, Eiji Miyano, Shuichi Miyazaki, and Katsuhisa Yamanaka
    Computational Complexity of University Interview Timetabling
    ▲ IEICE Transactions on Information and Systems, E92-D(2):130-140, 2009.
  81. Naoyuki Kamiyama and Naoki Katoh
    The Minimum Weight In-Tree Cover Problem
    △ 2nd International Conference on Modelling, Computation and Optimization in Information Systems and Management Sciences (MCO), CCIS 14, 155-164, 2008.
  82. Takenao Taji, Shin-ichi Tanigawa, Naoyuki Kamiyama, Naoki Katoh, Atsushi Takizawa
    Finding an Optimal Location of Line Facility Using Evolutionary Algorithm and Integer Program
    ▲ Journal of Computational Science and Technology, 2(3):362-370, 2008.
  83. Naoyuki Kamiyama, Naoki Katoh, Atsushi Takizawa
    An Efficient Algorithm for Evacuation Problem in Dynamic Network Flows with Uniform Arc Capacity
    ▲ IEICE Transactions on Information and Systems, E89-D(8):2372-2379, 2006.
    △ 2nd International Conference on Algorithmic Aspect in Information and Management (AAIM), LNCS 4041, 231-242, 2006.