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. 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.
  2. 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.
  3. Naoyuki Kamiyama
    A Note on Robust Subsets of Transversal Matroids
    ▲ Journal of the Operations Research Society of Japan, 67(2):37-45, 2024.
  4. 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.
  5. 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.
  6. Naoyuki Kamiyama
    On Optimization Problems in Acyclic Hypergraphs
    ▲ Information Processing Letters, 182:106390, 2023.
  7. 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.
  8. Takehiro Ito, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, Yoshio Okamoto
    Algorithmic Theory of Qubit Routing
    △ 18th Algorithms and Data Structures Symposium (WADS), LNCS 14079, 533-546, 2023.
  9. 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.
  10. 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.
  11. Naoyuki Kamiyama
    Pareto Efficient Matchings with Pairwise Preferences
    ▲ Theoretical Computer Science, 948:113707, 2023.
  12. 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.
  13. Takehiro Ito, Yuni Iwamasa, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, Yuta Nozaki, Yoshio Okamoto, Kenta Ozeki
    Reforming an Envy-Free Matching
    △ 36th AAAI Conference on Artificial Intelligence (AAAI), 5084-5091, 2022.
  14. Naoyuki Kamiyama
    A Matroid Generalization of the Super-Stable Matching Problem
    ▲ SIAM Journal on Discrete Mathematics, 36(2):1467-1482, 2022.
  15. 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.
  16. 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.
  17. Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, Yoshio Okamoto
    Submodular Reassignment Problem for Reallocating Agents to Tasks with Synergy Effects
    ▲ Discrete Optimization, 44:100631, 2022.
  18. 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.
  19. Naoyuki Kamiyama
    The Envy-Free Matching Problem with Pairwise Preferences
    ▲ Information Processing Letters, 172:106158, 2021.
  20. Naoyuki Kamiyama
    Envy-Free Matchings with One-Sided Preferences and Matroid Constraints
    ▲ Operations Research Letters, 49(5):790-794, 2021.
  21. Naoyuki Kamiyama, Pasin Manurangsi, Warut Suksompong
    On the Complexity of Fair House Allocation
    ▲ Operations Research Letters, 49(4):572-577, 2021.
  22. 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.
  23. 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.
  24. 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.
  25. Naoyuki Kamiyama
    The Distance-Constrained Matroid Median Problem
    ▲ Algorithmica, 82(7):2087-2106, 2020.
  26. Naoyuki Kamiyama
    On Stable Matchings with Pairwise Preferences and Matroid Constraints
    △ 19th International Conference on Autonomous Agents and Multiagent Systems (AAMAS), 584-592, 2020.
  27. Naoyuki Kamiyama
    Popular Matchings with Two-Sided Preference Lists and Matroid Constraints
    ▲ Theoretical Computer Science, 809:265-276, 2020.
  28. Naoyuki Kamiyama
    Lexicographically Optimal Earliest Arrival Flows
    ▲ Networks, 75(1):18-33, 2020.
  29. Naoyuki Kamiyama
    Discrete Newton Methods for the Evacuation Problem
    ▲ Theoretical Computer Science, 795:510-519, 2019.
  30. 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.
  31. 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.
  32. 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.
  33. Naoyuki Kamiyama
    A Note on Balanced Flows in Equality Networks
    ▲ Information Processing Letters, 145:74-76, 2019.
  34. Susumu Kawanaka and Naoyuki Kamiyama
    An Improved Algorithm for Testing Substitutability of Weak Preferences
    ▲ Mathematical Social Sciences, 99:1-4, 2019.
  35. 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.
  36. 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.
  37. Naoyuki Kamiyama
    Pareto Stable Matchings under One-Sided Matroid Constraints
    ▲ SIAM Journal on Discrete Mathematics, 33(3):1431-1451, 2019.
  38. 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.
  39. 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.
  40. Naoyuki Kamiyama
    A Note on Submodular Function Minimization with Covering Type Linear Constraints
    ▲ Algorithmica, 80(10):2957-2971, 2018.
  41. 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.
  42. 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.
  43. Naoyuki Kamiyama
    A Characterization of Weighted Popular Matchings under Matroid Constraints
    ▲ Journal of the Operations Research Society of Japan, 61(1):2-17, 2018.
  44. 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.
  45. 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.
  46. Naoyuki Kamiyama
    Strategic Issues in College Admissions with Score-Limits
    ▲ Operations Research Letters, 45:105-108, 2017.
  47. Naoyuki Kamiyama
    A Note on the Submodular Vertex Cover Problem with Submodular Penalties
    ▲ Theoretical Computer Science, 659:95-97, 2017.
  48. Naoyuki Kamiyama
    Popular Matchings with Ties and Matroid Constraints
    ▲ SIAM Journal on Discrete Mathematics, 31(3):1801-1819, 2017.
  49. 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.
  50. Satoru Iwata, Naoyuki Kamiyama, Naoki Katoh, Shuji Kijima, Yoshio Okamoto
    Extended Formulations for Sparsity Matroids
    ▲ Mathematical Programming, Series A, 158(1):565-574, 2016.
  51. 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.
  52. 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.
  53. 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.
  54. Naoyuki Kamiyama and Yasushi Kawase
    On Packing Arborescences in Temporal Networks
    ▲ Information Processing Letters, 115:321-325, 2015.
  55. Naoyuki Kamiyama
    The Nucleolus of Arborescence Games in Directed Acyclic Graphs
    ▲ Operations Research Letters, 43:89-92, 2015.
  56. 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.
  57. 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.
  58. Naoyuki Kamiyama
    A New Approach to the Pareto Stable Matching Problem
    ▲ Mathematics of Operations Research, 39(3):851-862, 2014.
  59. Naoyuki Kamiyama
    Arborescence Problems: Theorems and Algorithms
    ▲ Interdisciplinary Information Sciences, 20(1):51-70, 2014.
  60. 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.
  61. Naoyuki Kamiyama
    A Note on the Serial Dictatorship with Project Closures
    ▲ Operations Research Letters, 41:559-561, 2013.
  62. Naoyuki Kamiyama
    Matroid Intersection with Priority Constraints
    ▲ Journal of the Operations Research Society of Japan, 56(1):15-25, 2013.
  63. András Frank, Satoru Fujishige, Naoyuki Kamiyama, Naoki Katoh
    Independent Arborescences in Directed Graphs
    ▲ Discrete Mathematics, 313(4):453-459, 2013.
  64. Naoyuki Kamiyama
    A Note on the Quasi-Additive Bound for Boolean Functions
    ▲ Journal of Math-for-Industry, 4-B:119-122, 2012.
  65. 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.
  66. Satoru Fujishige and Naoyuki Kamiyama
    The Root Location Problem for Arc-Disjoint Arborescences
    ▲ Discrete Applied Mathematics, 160(13-14):1964-1970, 2012.
  67. 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.
  68. 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.
  69. 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.
  70. 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.
  71. 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.
  72. 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.
  73. 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.
  74. 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.
  75. 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.
  76. 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.
  77. 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.
  78. 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.
  79. 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.
  80. 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.