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, LNCS, LIPIcs, CRPIT, and CCIS)

  1. Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, and Yoshio Okamoto,
    Submodular Reassignment Problem for Reallocating Agents to Tasks with Synergy Effects,
    ▲ Discrete Optimization, accepted.
  2. Naoyuki Kamiyama,
    The Envy-Free Matching Problem with Pairwise Preferences,
    ▲ Information Processing Letters, 172:106158, 2021.
  3. Naoyuki Kamiyama, Pasin Manurangsi, and Warut Suksompong,
    On the Complexity of Fair House Allocation,
    ▲ Operations Research Letters, 49(4):572-577, 2021.
  4. Takehiro Ito, Naoyuki Kamiyama, Yusuke Kobayashi, and 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.
  5. 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, 2020.
  6. Naonori Kakimura, Naoyuki Kamiyama, and 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.
  7. Naoyuki Kamiyama,
    The Distance-Constrained Matroid Median Problem,
    ▲ Algorithmica, 82(7):2087-2106, 2020.
  8. Naoyuki Kamiyama,
    On Stable Matchings with Pairwise Preferences and Matroid Constraints,
    △ 19th International Conference on Autonomous Agents and Multiagent Systems (AAMAS), 584-592, 2020.
  9. Naoyuki Kamiyama,
    Popular Matchings with Two-Sided Preference Lists and Matroid Constraints,
    ▲ Theoretical Computer Science, 809:265-276, 2020.
  10. Naoyuki Kamiyama,
    Lexicographically Optimal Earliest Arrival Flows,
    ▲ Networks, 75(1):18-33, 2020.
  11. Naoyuki Kamiyama,
    Discrete Newton Methods for the Evacuation Problem,
    ▲ Theoretical Computer Science, 795:510-519, 2019.
  12. Akifumi Kira, Naoyuki Kamiyama, Hirokazu Anai, Hiroaki Iwashita, and Kotaro Ohori,
    On Dynamic Patrolling Security Games,
    ▲ Journal of the Operations Research Society of Japan, 62(4):152-168, 2019.
  13. Chien-Chung Huang, Naonori Kakimura, and 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.
  14. Takehiro Ito, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, and Yoshio Okamoto,
    Shortest Reconfiguration of Perfect Matchings via Alternating Cycles,
    △ 27th Annual European Symposium on Algorithms (ESA), LIPIcs 144, 61:1-61:15, 2019.
  15. Naoyuki Kamiyama,
    Pareto Stable Matchings under One-Sided Matroid Constraints,
    ▲ SIAM Journal on Discrete Mathematics, 33(3):1431-1451, 2019.
  16. Naoyuki Kamiyama,
    A Note on Balanced Flows in Equality Networks,
    ▲ Information Processing Letters, 145:74-76, 2019.
  17. 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.
  18. Susumu Kawanaka and Naoyuki Kamiyama,
    An Improved Algorithm for Testing Substitutability of Weak Preferences,
    ▲ Mathematical Social Sciences, 99:1-4, 2019.
  19. Takehiro Ito, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, and 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.
  20. Takehiro Ito, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, and 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.
  21. 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.
  22. Yosuke Hanawa, Yuya Higashikawa, Naoyuki Kamiyama, Naoki Katoh, and 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.
  23. Naoyuki Kamiyama,
    A Note on Submodular Function Minimization with Covering Type Linear Constraints,
    ▲ Algorithmica, 80(10):2957-2971, 2018.
  24. Naoyuki Kamiyama,
    A Characterization of Weighted Popular Matchings under Matroid Constraints,
    ▲ Journal of the Operations Research Society of Japan, 61(1):2-17, 2018.
  25. Hiroaki Yamada, Kotaro Ohori, Tadashige Iwao, Akifumi Kira, Naoyuki Kamiyama, Hiroaki Yoshida, and 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.
  26. Takehiro Ito, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, Yoshio Okamoto, and 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, 2017.
  27. 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, 2017.
  28. Naoyuki Kamiyama,
    Popular Matchings with Ties and Matroid Constraints,
    ▲ SIAM Journal on Discrete Mathematics, 31(3):1801-1819, 2017.
  29. Takehiro Ito, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, and 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.
  30. Naoyuki Kamiyama,
    Strategic Issues in College Admissions with Score-Limits,
    ▲ Operations Research Letters, 45:105-108, 2017.
  31. Naoyuki Kamiyama,
    A Note on the Submodular Vertex Cover Problem with Submodular Penalties,
    ▲ Theoretical Computer Science, 659:95-97, 2017.
  32. 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.
  33. Satoru Iwata, Naoyuki Kamiyama, Naoki Katoh, Shuji Kijima, and Yoshio Okamoto,
    Extended Formulations for Sparsity Matroids,
    ▲ Mathematical Programming, Series A, 158(1):565-574, 2016.
  34. 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.
  35. 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.
  36. 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.
  37. Naoyuki Kamiyama and Yasushi Kawase,
    On Packing Arborescences in Temporal Networks,
    ▲ Information Processing Letters, 115:321-325, 2015.
  38. Naoyuki Kamiyama,
    The Nucleolus of Arborescence Games in Directed Acyclic Graphs,
    ▲ Operations Research Letters, 43:89-92, 2015.
  39. 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.
  40. Yuya Higashikawa, Naoyuki Kamiyama, Naoki Katoh, and 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.
  41. Naoyuki Kamiyama,
    A New Approach to the Pareto Stable Matching Problem,
    ▲ Mathematics of Operations Research, 39(3):851-862, 2014.
  42. Naoyuki Kamiyama,
    Arborescence Problems: Theorems and Algorithms,
    ▲ Interdisciplinary Information Sciences, 20(1):51-70, 2014.
  43. Yusuke Matsumoto, Naoyuki Kamiyama, and 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.
  44. Naoyuki Kamiyama,
    A Note on the Serial Dictatorship with Project Closures,
    ▲ Operations Research Letters, 41:559-561, 2013.
  45. Naoyuki Kamiyama,
    Matroid Intersection with Priority Constraints,
    ▲ Journal of the Operations Research Society of Japan, 56(1):15-25, 2013.
  46. András Frank, Satoru Fujishige, Naoyuki Kamiyama, and Naoki Katoh,
    Independent Arborescences in Directed Graphs,
    ▲ Discrete Mathematics, 313(4):453-459, 2013.
  47. 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.
  48. Satoru Fujishige and Naoyuki Kamiyama,
    The Root Location Problem for Arc-disjoint Arborescences,
    ▲ Discrete Applied Mathematics, 160(13-14):1964-1970, 2012.
  49. Naoyuki Kamiyama,
    A Note on the Quasi-additive Bound for Boolean Functions,
    ▲ Journal of Math-for-Industry, 4-B:119-122, 2012.
  50. Yuichiro Yasui, Katsuki Fujisawa, Kazushige Goto, Naoyuki Kamiyama, and 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.
  51. 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.
  52. Yusuke Matsumoto, Naoyuki Kamiyama, and Keiko Imai,
    An Approximation Algorithm Dependent on Edge-coloring Number for Minimum Maximal Matching Problem,
    ▲ Information Processing Letters, 111(10):465-468, 2011.
  53. Yutaka Iwaikawa, Naoyuki Kamiyama, and Tomomi Matsui,
    Improved Approximation Algorithms for Firefighter Problem on Trees,
    ▲ IEICE Transactions on Information and Systems, E94-D(2):196-199, 2011.
  54. 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.
  55. 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.
  56. 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.
  57. Kristóf Bérczi, Satoru Fujishige, and 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.
  58. Naoyuki Kamiyama, Naoki Katoh, and 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.
  59. Naoyuki Kamiyama, Naoki Katoh, and 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.
  60. 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.
  61. 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.
  62. Takenao Taji, Shin-ichi Tanigawa, Naoyuki Kamiyama, Naoki Katoh, and 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.
  63. Naoyuki Kamiyama, Naoki Katoh, and 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.