Organization
School of Computing Associate Professor
Title
Associate Professor
External link
YOKOI YU
Degree
-
Doctor of Mathematical Informatics ( The University of Tokyo )
Research Interests
-
Matching Theory
-
Game Theory
-
Discrete Algorithm
-
Combinatorial Optimization
Research Areas
-
Natural Science / Applied mathematics and statistics
-
Informatics / Mathematical informatics
-
Natural Science / Basic mathematics
Education
-
The University of Tokyo Graduate School of Information Science and Technology Department of Mathematical Informatics
2012.4 - 2017.3
-
Osaka University Faculty of Engineering Science
2008.4 - 2012.3
Research History
-
Tokyo Institute of Technology School of Computing Associate Professor
2023.4
-
National Institute of Informatics Principles of Informatics Research Division Assistant Professor
2017.4 - 2023.3
Professional Memberships
-
THE JAPAN SOCIETY FOR INDUSTRIAL AND APPLIED MATHEMATICS
-
THE OPERATIONS RESEARCH SOCIETY OF JAPAN
Papers
-
Popular Arborescences and Their Matroid Generalization. Reviewed International coauthorship
Telikepalli Kavitha, Kazuhisa Makino, Ildikó Schlotter, Yu Yokoi
ACM Trans. Algorithms 21 ( 2 ) 22 - 35 2025.8
-
Finding spanning trees with perfect matchings. Reviewed International coauthorship
Kristóf Bérczi, Tamás Király, Yusuke Kobayashi 0001, Yutaro Yamaguchi 0001, Yu Yokoi
Discret. Appl. Math. 371 137 - 147 2025.4
-
A fair and truthful mechanism with limited subsidy Reviewed
Hiromichi Goko, Ayumi Igarashi, Yasushi Kawase, Kazuhisa Makino, Hanna Sumita, Akihisa Tamura, Yu Yokoi, Makoto Yokoo
Games and Economic Behavior 144 49 - 70 2025.1
-
Solving the Maximum Popular Matching Problem with Matroid Constraints. Reviewed International coauthorship
Gergely Kál Csáji, Tamás Király, Yu Yokoi
SIAM Journal on Discrete Mathematics 38 ( 3 ) 2226 - 2242 2024.8
-
Arborescences, Colorful Forests, and Popularity. Reviewed International coauthorship
Telikepalli Kavitha, Kazuhisa Makino, Ildikó Schlotter, Yu Yokoi
Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms(SODA) 3724 - 3746 2024.4
-
Finding Maximum Edge-Disjoint Paths Between Multiple Terminals Reviewed
Satoru Iwata, Yu Yokoi
SIAM Journal on Computing 52 ( 5 ) 1230 - 1268 2023.10
-
Fast Primal-Dual Update against Local Weight Update in Linear Assignment Problem and Its Application Reviewed International journal
Kohei Morita, Shinya Shiroshita, Yutaro Yamaguchi, Yu Yokoi
Information Processing Letters 183 ( 106432 ) 2023.8
-
Matroid Intersection under Restricted Oracles Reviewed International coauthorship International journal
Kristóf Bérczi, Tamás Király, Yutaro Yamaguchi, Yu Yokoi
SIAM Journal on Discrete Mathematics 37 ( 2 ) 1311 - 1330 2023.6
-
Hardness of braided quantum circuit optimization in the surface code Reviewed International coauthorship International journal
Kunihiro Wasa, Shin Nishio, Koki Suetsugu, Michael Hanks, Ashley Stephens, Yu Yokoi, Kae Nemoto
IEEE Transactions on Quantum Engineering 4 1 - 8 2023.3
-
Hypergraph characterization of split matroids Reviewed
Kristóf Bérczi, Tamás Király, Tamás Schwarcz, Yutaro Yamaguchi, Yu Yokoi
Journal of Combinatorial Theory, Series A 194 105697 - 105697 2023.2
-
Approximation Algorithms for Matroidal and Cardinal Generalizations of Stable Matching Reviewed
Gergely Csáji, Tamás Király, Yu Yokoi
Proceedings of the Sixth SIAM Symposium on Simplicity in Algorithms (SOSA 2023) 103 - 113 2023.1
-
Random Assignment of Indivisible Goods under Constraints.
Yasushi Kawase, Hanna Sumita, Yu Yokoi
IJCAI 2792 - 2799 2023
-
Incomplete List Setting of the Hospitals/Residents Problem with Maximally Satisfying Lower Quotas Reviewed
Kazuhisa Makino, Shuichi Miyazaki, Yu Yokoi
Proceedings of the 15th International Symposium on Algorithmic Game Theory (SAGT 2022) 544 - 561 2022.9
-
Fair and Truthful Mechanism with Limited Subsidy Reviewed
Hiromichi Goko, Ayumi Igarashi, Yasushi Kawase, Kazuhisa Makino, Hanna Sumita, Akihisa Tamura, Yu Yokoi, Makoto Yokoo
Proceedings of the 21st International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2022) abs/2105.01801 534 - 542 2022.4
-
Approximation by lexicographically maximal solutions in matching and matroid intersection problems Reviewed
Kristóf Bérczi, Tamás Király, Yutaro Yamaguchi, Yu Yokoi
Theoretical Computer Science 910 48 - 53 2022.4
-
Maximally Satisfying Lower Quotas in the Hospitals/Residents Problem with Ties. Reviewed
Hiromichi Goko, Kazuhisa Makino, Shuichi Miyazaki, Yu Yokoi
Proceedings of the 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022) 31:1 - 31:20 2022.3
-
Equitable partitions into matchings and coverings in mixed graphs Reviewed
Tamás Király, Yu Yokoi
Discrete Mathematics 345 ( 1 ) 112651 - 112651 2022.1
-
An Approximation Algorithm for Maximum Stable Matching with Ties and Constraints. Reviewed
Yu Yokoi
Proceedings of the 32nd International Symposium on Algorithms and Computation (ISAAC 2021) 71:1 - 71:16 2021.12
-
A Note on a Nearly Uniform Partition into Common Independent Sets of Two Matroids Reviewed
Satoru Fujishige, Kenjiro Takazawa, Yu Yokoi
Journal of the Operations Research Society of Japan 63 ( 3 ) 71 - 77 2020.7
-
Envy-Free Matchings with Lower Quotas Reviewed
Yu Yokoi
Algorithmica 82 ( 2 ) 188 - 211 2020.2
-
Subgame Perfect Equilibria of Sequential Matching Games Reviewed
Yasushi Kawase, Yutaro Yamaguchi, Yu Yokoi
ACM Transactions on Economics and Computation 7 ( 4 ) No. 21, 30pp. 2020.1
-
A Blossom Algorithm for Maximum Edge-Disjoint T-Paths Reviewed
Satoru Iwata, Yu Yokoi
Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms (SODA2020) 1933 - 1944 2020.1
-
Finding a Stable Allocation in Polymatroid Intersection Reviewed
Satoru Iwata, Yu Yokoi
Mathematics of Operations Research 45 ( 1 ) 63 - 85 2020.1
-
Matroidal Choice Functions Reviewed
Yu Yokoi
SIAM Journal on Discrete Mathematics 33 ( 3 ) 1712 - 1724 2019.9
-
A Generalized-Polymatroid Approach to Disjoint Common Independent Sets in Two Matroids Reviewed
Kenjiro Takazawa, Yu Yokoi
Discrete Mathematics 342 ( 7 ) 2002 - 2011 2019.7
-
List Supermodular Coloring with Shorter Lists Reviewed
Yu Yokoi
Combinatorica 39 ( 2 ) 459 - 475 2019.4
-
List Supermodular Coloring Reviewed
Satoru Iwata, Yu Yokoi
Combinatorica 38 ( 6 ) 1437 - 1456 2018.12
-
Optimal cache placement for an academic backbone network Reviewed
Than Nguyen Hau, Naonori Kakimura, Ken-Ichi Kawarabayashi, Yusuke Kobayashi, Tatsuya Matsuoka, Yu Yokoi
Journal of the Operations Research Society of Japan 61 ( 2 ) 197 - 216 2018.4
-
Computing a Subgame Perfect Equilibrium of a Sequential Matching Game. Reviewed
Yasushi Kawase, Yutaro Yamaguchi 0001, Yu Yokoi
Proceedings of the 2018 ACM Conference on Economics and Computation (EC 2018) 131 - 148 2018
-
A Generalized Polymatroid Approach to Stable Matchings with Lower Quotas Reviewed
Yu Yokoi
MATHEMATICS OF OPERATIONS RESEARCH 42 ( 1 ) 238 - 255 2017.2
-
Finding a Stable Allocation in Polymatroid Intersection. Reviewed
Satoru Iwata, Yu Yokoi
Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2016) 1034 - 1047 2016
-
On the Lattice Structure of Stable Allocations in a Two-Sided Discrete-Concave Market Reviewed
Kazuo Murota, Yu Yokoi
MATHEMATICS OF OPERATIONS RESEARCH 40 ( 2 ) 460 - 473 2015.5
MISC
-
展開型マッチングゲームにおける部分ゲーム完全均衡
河瀬康志, 山口勇太郎, 横井優
日本応用数理学会年会講演予稿集(CD-ROM) 2018 2018
-
一般化ポリマトロイドによる下限制約付き安定割当問題の拡張
横井 優
日本オペレーションズ・リサーチ学会春季研究発表会アブストラクト集 2015 302 - 303 2015.3
-
Study on Stable Allocations in Two-Sided Discrete-Concave Market
[O]perations research as a management science [r]esearch 59 ( 12 ) 766 - 767 2014.12
-
マトロイド的選択関数
横井 優
日本オペレーションズ・リサーチ学会秋季研究発表会アブストラクト集 2014 202 - 203 2014.8
-
準M♮凹評価関数を用いた一般化安定結婚モデル
横井 優, 室田 一雄
日本オペレーションズ・リサーチ学会春季研究発表会アブストラクト集 2014 134 - 135 2014.3
-
整数格子点上の安定結婚問題がもつ束構造
横井 優, 室田 一雄
日本オペレーションズ・リサーチ学会秋季研究発表会アブストラクト集 2013 112 - 113 2013.9
Presentations
-
Solving the Maximum Popular Matching Problem with Matroid Constraints.
Gergely Csáji, Tamás Király, ○Yu Yokoi
The 12th Japanese-Hungarian Symposium on Discrete Mathematics and Its Applications 2023.3
-
Approximation Algorithms for Matroidal and Cardinal Generalizations of Stable Matching.
Gergely Csáji, Tamás Király, ○Yu Yokoi
The Sixth SIAM Symposium on Simplicity of Algorithms (SOSA 2023) 2023.1
-
Incomplete List Setting of the Hospitals/Residents Problem with Maximally Satisfying Lower Quotas
Kazuhisa Makino, Shuichi Miyazaki, ○Yu Yokoi
The 15th International Symposium on Algorithmic Game Theory (SAGT 2022) 2022.9
-
安定マッチングと組合せ最適化
横井 優
RIMS 共同研究「組合せ最適化セミナー」(第19回) 2022.7
-
Maximally Satisfying Lower Quotas in the Hospitals/Residents Problem with Ties
Hiromichi Goko, Kazuhisa Makino, Shuichi Miyazaki, ○Yu Yoko
The 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022) 2022.3
-
An Approximation Algorithm for Maximum Stable Matching with Ties and Constraints
Yu Yokoi
The 32nd International Symposium on Algorithms and Computation (ISAAC 2021) 2021.12
-
Approximability vs. Strategy-proofness in Stable Matching Problems with Ties
Yu Yokoi
Dagstuhl Seminar (on Matching Under Preferences: Theory and Practice) 2021.7
-
A Blossom Algorithm for Maximum Edge-Disjoint T-Paths Invited
岩田 覚, 横井 優
電子情報通信学会コンピュテーション研究会 2020.12
-
安定マッチング理論と展開型マッチングゲーム Invited
横井 優
第17回情報科学技術フォーラム (FIT2018) 2018.9
-
展開型マッチングゲームにおける部分ゲーム完全均衡
河瀬 康志, 山口 勇太郎, 横井 優
日本応用数理学会 2018年度年会 2018.9
-
Equitable Partitions into Matchings and Coverings in Mixed Graphs
Tamás Király, ○Yu Yokoi
The 11th Hungarian-Japanese Symposium on Discrete Mathematics and Its Applications 2019.5
-
A Blossom Algorithm for Maximum Edge-Disjoint T-Paths
Satoru Iwata, ○Yu Yokoi
Japanese Conference on Combinatorics and its Applications (JCCA 2019) 2019.8
-
Finding a Stable Allocation in Polymatroid Intersection
Satoru Iwata, ○Yu Yokoi
HIM Trimester Program "Combinatorial Optimization," Rigidity Workshop 2015.10
-
Finding a Stable Allocation in Polymatroid Intersection
Satoru Iwata, ○Yu Yokoi
The 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2016) 2016.1
-
A Generalized Polymatroid Approach to Stable Allocations with Lower Quotas
Yu Yokoi
The Fourth International Workshop on Matching Under Preferences 2017.4
-
List Supermodular Coloring
Satoru Iwata, ○Yu Yokoi
The 10th Japanese-Hungarian Symposium on Discrete Mathematics and Its Applications 2017.5
-
Envy-free Matchings with Lower Quotas, International conference
Yu Yokoi
The 28th International Symposium on Algorithms and Computation (ISAAC 2017) 2017.12
-
Computing a Subgame Perfect Equilibrium of a Sequential Matching Game
Yasushi Kawase, Yutaro Yamaguchi, ○Yu Yokoi
The 19th ACM Conference on Economics and Computation (EC2018) 2018.6
-
List Supermodular Coloring
Satoru Iwata, ○Yu Yokoi
The 23rd International Symposium on Mathematical Programming (ISMP2018) 2018.7
-
Matroidal Choice Functions
Yu Yokoi
The Third International Workshop on Matching Under Preferences 2015.4
-
A Generalized Polymatroid Approach to Stable Allocations with Lower Quotas
Yu Yokoi
The 9th Hungarian-Japanese Symposium on Discrete Mathematics and Its Applications 2015.6
-
A Generalized Polymatroid Approach to Stable Allocations with Lower Quotas
Yu Yokoi
The 22nd International Symposium on Mathematical Programming (ISMP 2015) 2015.7
-
On the Lattice Structure of Stable Allocations in Two-Sided Discrete-Concave Market Invited
Yu Yokoi
The First International Workshop on Market Design Technologies for Sustainable Development 2013.11
-
選好に同順位を含むマッチングモデルでの安定解の最適化 Invited
横井優
電気通信大学 第38回情報数理工学セミナー 2021.7
Awards
-
第11回 研究賞奨励賞
2021.9 日本オペレーションズ・リサーチ学会
-
Best Presentation Award for Young Researchers at the 2018 JSIAM Annual Meeting
2019.6 The Japan Society for Industrial and Applied Mathematics
Research Projects
-
Investigating and utilizing the structure of matchings under preferences
Grant number：JPMJPR212B 2021.10 - 2025.3
Japan Science and Technology Agency PRESTO
Authorship：Principal investigator
-
定量的解析に基づく市場メカニズムの評価と最適化
2018.4 - 2022.3
日本学術振興会 若手研究
横井 優
Authorship：Principal investigator Grant type：Competitive
-
組合せ最適化にもとづく安定マッチングの理論と応用
Grant number：15J09039 2015.4 - 2017.3
日本学術振興会 科学研究費助成事業 特別研究員奨励費
横井 優
Grant amount：\1700000 （ Direct Cost: \1700000 ）
安定マッチングモデルは，研修医配属システムや学校選択制度などに応用をもつ数理モデルであり，経済学や数学，計算機科学といった様々な方面から研究されている．本研究では，組合せ最適化を用いたアプローチにより，安定マッチング理論における以下の成果を得た．
１．多対一の安定マッチング問題では，研修医と病院になぞらえられる二つの集合間で，各主体の選好を考慮した“安定な”マッチングを見つけることを考える．各病院が割当人数に上限しかもたない場合には安定マッチングの存在が保証できるが，下限ももつ場合には保証できない． 安定マッチングをもたない問題例に対しては，その緩和である envy-free マッチングを発見することが，代替策として考えられる．本研究では，下限付き多対一安定マッチングモデルにおける envy-free マッチングの存在性について考察した．そして，基本的な設定および，マトロイド的構造を持った拡張モデルに対し，効率的に envy-free マッチングの存在判定をするアルゴリズムを設計した．また，より一般的なモデルにおける存在性判定の計算困難性(NP困難性)を示した．
２．昨年度の研究では，ポリマトロイドという構造上の安定マッチングを算出する初の強多項式時間アルゴリズムを設計した．本年度の研究では，そのアルゴリズムの出力が単に安定であるだけでなく，多数存在し得る安定解の中で，ある種の最適性を満たすものであるということを示した．
<BR>
また，安定マッチングを数学的に拡張した概念(半順序対のカーネル)を用いて，リスト優モジュラ彩色という組合せ的問題に対して，彩色の存在を保証するリスト長の特徴付けを与えた．