5 papers
Stable Matchings with Minimum Utility Gap
Yao Sheng, Yu Yokoi
We introduce the Stable Matching Problem with Minimum Utility Gap, which seeks a stable matching in which the utilities received by individual agents are as balanced as possible. O…
Ranking and Rank Aggregation with Matroid Prefix Constraints
Seiei Ando, Yu Yokoi
We study ranking and rank aggregation under the Kendall tau distance, subject to matroid or flag matroid constraints on prefixes of the output ranking. In the matroid case, the top…
Matroid Intersection under Minimum Rank Oracle
Mihály Bárász, Kristóf Bérczi, Tamás Király +3
In this paper, we consider the tractability of the matroid intersection problem under the minimum rank oracle. In this model, we are given an oracle that takes as its input a set o…
The Rainbow Arborescence Problem on Cycles
Kristóf Bérczi, Tamás Király, Yutaro Yamaguchi +1
The rainbow arborescence conjecture posits that if the arcs of a directed graph with vertices are colored by colors such that each color class forms a spanning arborescen…
Rainbow Arborescence Conjecture
Kristóf Bérczi, Tamás Király, Yutaro Yamaguchi +1
The famous Ryser--Brualdi--Stein conjecture asserts that every Latin square contains a partial transversal of size . Since its appearance, the conjecture has attr…