Zobrazeno 1 - 10
of 226
pro vyhledávání: '"Kamiyama, Naoyuki"'
Autor:
Kamiyama, Naoyuki
Super-stability and strong stability are properties of a matching in the stable matching problem with ties. In this paper, we introduce a common generalization of super-stability and strong stability, which we call non-uniform stability. First, we pr
Externí odkaz:
http://arxiv.org/abs/2408.16271
Autor:
Kamiyama, Naoyuki
In this paper, we consider a many-to-one matching market where ties in the preferences of agents are allowed. For this market with capacity constraints, Bonifacio, Juarez, Neme, and Oviedo proved some relationship between the set of stable matchings
Externí odkaz:
http://arxiv.org/abs/2405.00342
Autor:
Kamiyama, Naoyuki
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 super-stable matching can be checked in polynomial time. In this paper, we
Externí odkaz:
http://arxiv.org/abs/2402.11918
Autor:
Kamiyama, Naoyuki
In this paper, we consider one-to-one matchings between two disjoint groups of agents. Each agent has a preference over a subset of the agents in the other group, and these preferences may contain ties. Strong stability is one of the stability concep
Externí odkaz:
http://arxiv.org/abs/2401.02666
In the allocation of indivisible goods, a prominent fairness notion is envy-freeness up to one good (EF1). We initiate the study of reachability problems in fair division by investigating the problem of whether one EF1 allocation can be reached from
Externí odkaz:
http://arxiv.org/abs/2312.07241
Autor:
Ito, Takehiro, Iwamasa, Yuni, Kamiyama, Naoyuki, Kobayashi, Yasuaki, Kobayashi, Yusuke, Maezawa, Shun-ichi, Suzuki, Akira
An arborescence, which is a directed analogue of a spanning tree in an undirected graph, is one of the most fundamental combinatorial objects in a digraph. In this paper, we study arborescences in digraphs from the viewpoint of combinatorial reconfig
Externí odkaz:
http://arxiv.org/abs/2305.07262
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 programs. We study the qubit routing problem from the viewpoint of theoretic
Externí odkaz:
http://arxiv.org/abs/2305.02059
Autor:
Ito, Takehiro, Kakimura, Naonori, Kamiyama, Naoyuki, Kobayashi, Yusuke, Maezawa, Shun-ichi, Nozaki, Yuta, Okamoto, Yoshio
We prove that the computation of a combinatorial shortest path between two vertices of a graph associahedron, introduced by Carr and Devadoss, is NP-hard. This resolves an open problem raised by Cardinal. A graph associahedron is a generalization of
Externí odkaz:
http://arxiv.org/abs/2304.14782
Autor:
Kamiyama, Naoyuki
Robust subsets of matroids were introduced by Huang and Sellier to propose approximate kernels for the matroid-constrained maximum vertex cover problem. In this paper, we prove that the bound for robust subsets of transversal matroids given by Huang
Externí odkaz:
http://arxiv.org/abs/2210.09534
Autor:
Ito, Takehiro, Kakimura, Naonori, Kamiyama, Naoyuki, Kobayashi, Yusuke, Nozaki, Yuta, Okamoto, Yoshio, Ozeki, Kenta
We consider the problem of determining whether a target item assignment can be reached from an initial item assignment by a sequence of pairwise exchanges of items between agents. In particular, we consider the situation where each agent has a dichot
Externí odkaz:
http://arxiv.org/abs/2209.10262