2 citations · 7 across the 15 of their papers we have counts for
18 papers
Matroid Intersection under Restricted Oracles
Kristóf Bérczi, Tamás Király, Yutaro Yamaguchi +1
Matroid intersection is one of the most powerful frameworks of matroid theory that generalizes various problems in combinatorial optimization. Edmonds' fundamental theorem provides…
Solving the Maximum Popular Matching Problem with Matroid Constraints
Gergely Csáji, Tamás Király, Yu Yokoi
We consider the problem of finding a maximum popular matching in a many-to-many matching setting with two-sided preferences and matroid constraints. This problem was proposed by Ka…
Fast Primal-Dual Update against Local Weight Update in Linear Assignment Problem and Its Application
Kohei Morita, Shinya Shiroshita, Yutaro Yamaguchi +1
We consider a dynamic situation in the weighted bipartite matching problem: edge weights in the input graph are repeatedly updated and we are asked to maintain an optimal matching…
Maximum Stable Matching with Matroids and Partial Orders
Gergely Csáji, Tamás Király, Yu Yokoi
The Stable Marriage problem (SM), solved by the famous deferred acceptance algorithm of Gale and Shapley (GS), has many natural generalizations. If we allow ties in preferences, th…
Random Assignment of Indivisible Goods under Constraints
Yasushi Kawase, Hanna Sumita, Yu Yokoi
We investigate the problem of random assignment of indivisible goods, in which each agent has an ordinal preference and a constraint. Our goal is to characterize the conditions und…
Incomplete List Setting of the Hospitals/Residents Problem with Maximally Satisfying Lower Quotas
Kazuhisa Makino, Shuichi Miyazaki, Yu Yokoi
To mitigate the imbalance in the number of assignees in the Hospitals/Residents problem, Goko et al. [Goko et al., Maximally Satisfying Lower Quotas in the Hospitals/Residents Prob…
Hypergraph characterization of split matroids
Kristóf Bérczi, Tamás Király, Tamás Schwarcz +2
We provide a combinatorial study of split matroids, a class that was motivated by the study of matroid polytopes from a tropical geometry point of view. A nice feature of split mat…
Approximation by Lexicographically Maximal Solutions in Matching and Matroid Intersection Problems
Kristóf Bérczi, Tamás Király, Yutaro Yamaguchi +1
We study how good a lexicographically maximal solution is in the weighted matching and matroid intersection problems. A solution is lexicographically maximal if it takes as many he…
An Approximation Algorithm for Maximum Stable Matching with Ties and Constraints
Yu Yokoi
We present a polynomial-time -approximation algorithm for the problem of finding a maximum-cardinality stable matching in a many-to-many matching model with ties and l…
Fair and Truthful Mechanism with Limited Subsidy
Hiromichi Goko, Ayumi Igarashi, Yasushi Kawase +5
The notion of \emph{envy-freeness} is a natural and intuitive fairness requirement in resource allocation. With indivisible goods, such fair allocations are unfortunately not guara…
Maximally Satisfying Lower Quotas in the Hospitals/Residents Problem with Ties
Hiromichi Goko, Kazuhisa Makino, Shuichi Miyazaki +1
Motivated by the serious problem that hospitals in rural areas suffer from a shortage of residents, we study the Hospitals/Residents model in which hospitals are associated with lo…
A Note on a Nearly Uniform Partition into Common Independent Sets of Two Matroids
Satoru Fujishige, Kenjiro Takazawa, Yu Yokoi
The present note is a strengthening of a recent paper by K. Takazawa and Y. Yokoi (A generalized-polymatroid approach to disjoint common independent sets in two matroids, Discrete…
Finding Maximum Edge-Disjoint Paths Between Multiple Terminals
Satoru Iwata, Yu Yokoi
Let be a multigraph with a set of terminals. A path in is called a -path if its ends are distinct vertices in and no internal vertices belong to…
Equitable Partitions into Matchings and Coverings in Mixed Graphs
Tamás Király, Yu Yokoi
Matchings and coverings are central topics in graph theory. The close relationship between these two has been key to many fundamental algorithmic and polyhedral results. For mixed…
A Generalized-Polymatroid Approach to Disjoint Common Independent Sets in Two Matroids
Kenjiro Takazawa, Yu Yokoi
In this paper, we investigate the classes of matroid intersection admitting a solution for the problem of partitioning the ground set into common independent sets, where $E…
Subgame Perfect Equilibria of Sequential Matching Games
Yasushi Kawase, Yutaro Yamaguchi, Yu Yokoi
We study a decentralized matching market in which firms sequentially make offers to potential workers. For each offer, the worker can choose "accept" or "reject," but the decision…
List Supermodular Coloring with Shorter Lists
Yu Yokoi
In 1995, Galvin proved that a bipartite graph admits a list edge coloring if every edge is assigned a color list of length , the maximum degree of the graph. This result…
Envy-free Matchings with Lower Quotas
Yu Yokoi
While every instance of the Hospitals/Residents problem admits a stable matching, the problem with lower quotas (HR-LQ) has instances with no stable matching. For such an instance,…