1 citations · 2 across the 5 of their papers we have counts for
5 papers
Modifying an Instance of the Super-Stable Matching Problem
Naoyuki Kamiyama
Super-stability is one of the stability concepts in the stable matching problem with ties. It is known that there may not exist a super-stable matching, and the existence of a supe…
Algorithmic Theory of Qubit Routing
Takehiro Ito, Naonori Kakimura, Naoyuki Kamiyama +2
The qubit routing problem, also known as the swap minimization problem, is a (classical) combinatorial optimization problem that arises in the design of compilers of quantum progra…
Reforming an Envy-Free Matching
Takehiro Ito, Yuni Iwamasa, Naonori Kakimura +5
We consider the problem of reforming an envy-free matching when each agent is assigned a single item. Given an envy-free matching, we consider an operation to exchange the item of…
On Finding Pure Nash Equilibria of Discrete Preference Games and Network Coordination Games
Takashi Ishizuka, Naoyuki Kamiyama
This paper deals with the complexity of the problem of computing a pure Nash equilibrium for discrete preference games and network coordination games beyond -treewidth a…
Extended Formulations for Sparsity Matroids
Satoru Iwata, Naoyuki Kamiyama, Naoki Katoh +2
We show the existence of a polynomial-size extended formulation for the base polytope of a -sparsity matroid. For an undirected graph , the size of the formulati…