所属
情報理工学院 准教授
職名
准教授
外部リンク
ヨコイ ユウ
横井 優
YOKOI YU
学位
-
博士(情報理工学) （ 東京大学 ）
研究キーワード
-
マッチング理論
-
ゲーム理論
-
離散アルゴリズム
-
組合せ最適化
研究分野
-
自然科学一般 / 応用数学、統計数学
-
情報通信 / 数理情報学
-
自然科学一般 / 数学基礎
学歴
-
東京大学 情報理工学系研究科 数理情報学専攻
2012年4月 - 2017年3月
-
大阪大学 基礎工学部 システム科学科
2008年4月 - 2012年3月
経歴
-
東京工業大学 情報理工学院 准教授
2023年4月 - 現在
-
国立情報学研究所 情報学プリンシプル研究系 助教
2017年4月 - 2023年3月
所属学協会
-
日本応用数理学会
-
日本オペレーションズ・リサーチ学会
委員歴
-
Discrete Optimization Associate Editor
2026年6月 - 現在
-
Mathematics of Operations Research Associate Editor
2026年1月 - 現在
-
The 27th Conference on Integer Programming and Combinatorial Optimization (IPCO 2026) Program Committee member
2025年10月 - 2026年6月
Relevant schedule: paper submission deadline on 2025-10-31; PC meeting during 2026-01-05--2026-01-09; final notification on 2026-02-15; conference dates 2026-06-17--2026-06-19.
-
Workshop on Approximation and Online Algorithms (WAOA 2025) Program Committee member
2025年7月 - 2025年8月
Reviewing schedule: submission deadline and bidding start on 2025-07-06 AoE; bidding deadline on 2025-07-09; paper assignment to PC on 2025-07-10; suggested subreferee deadline on 2025-07-22; review deadline and discussion start on 2025-07-24; discussion ends on 2025-08-03; voting on undecided papers on 2025-08-05; review adjustment deadline on 2025-08-06; author notification on 2025-08-07.
論文
-
Two-Sided Fairness in Many-to-One Matching. 査読 国際共著
Ayumi Igarashi 0001, Naoyuki Kamiyama, Yasushi Kawase, Warut Suksompong, Hanna Sumita, Yu Yokoi
Proceedings of the 21st Conference on Web and Internet Economics (WINE 2025), LNCS 16266 782 - 782 2026年5月
-
Decomposition envy-freeness in random assignment. 査読 国際共著
Yasushi Kawase, Warut Suksompong, Hanna Sumita, Yu Yokoi
Math. Soc. Sci. 141 102532 - 102532 2026年4月
-
A Simple 1.5-Approximation Algorithm for a Wide Range of Maximum-Size Stable Matching Problems 査読 国際共著
Gergely Csáji, Tamás Király, Yu Yokoi
Mathematics of Operations Research 2025年10月
-
Popular Maximum-Utility Matchings with Matroid Constraints 査読 国際共著
Gergely Csáji, Tamás Király, Kenjiro Takazawa, Yu Yokoi
Mathematics of Operations Research 2025年9月
-
Popular Arborescences and Their Matroid Generalization. 査読 国際共著
Telikepalli Kavitha, Kazuhisa Makino, Ildikó Schlotter, Yu Yokoi
ACM Trans. Algorithms 21 ( 2 ) 22 - 35 2025年8月
-
Finding spanning trees with perfect matchings. 査読 国際共著
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 査読
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. 査読 国際共著
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. 査読 国際共著
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 査読
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 査読 国際誌
Kohei Morita, Shinya Shiroshita, Yutaro Yamaguchi, Yu Yokoi
Information Processing Letters 183 ( 106432 ) 2023年8月
-
Matroid Intersection under Restricted Oracles 査読 国際共著 国際誌
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 査読 国際共著 国際誌
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 査読
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 査読
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 査読
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 査読
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 査読
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. 査読
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 査読
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. 査読
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 査読
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 査読
Yu Yokoi
Algorithmica 82 ( 2 ) 188 - 211 2020年2月
-
Subgame Perfect Equilibria of Sequential Matching Games 査読
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 査読
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 査読
Satoru Iwata, Yu Yokoi
Mathematics of Operations Research 45 ( 1 ) 63 - 85 2020年1月
-
Matroidal Choice Functions 査読
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 査読
Kenjiro Takazawa, Yu Yokoi
Discrete Mathematics 342 ( 7 ) 2002 - 2011 2019年7月
-
List Supermodular Coloring with Shorter Lists 査読
Yu Yokoi
Combinatorica 39 ( 2 ) 459 - 475 2019年4月
-
Satoru Iwata, Yu Yokoi
Combinatorica 38 ( 6 ) 1437 - 1456 2018年12月
-
Optimal cache placement for an academic backbone network 査読
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. 査読
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 査読
Yu Yokoi
MATHEMATICS OF OPERATIONS RESEARCH 42 ( 1 ) 238 - 255 2017年2月
-
Finding a Stable Allocation in Polymatroid Intersection. 査読
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 査読
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
横井 優
オペレーションズ・リサーチ : 経営の科学 59 ( 12 ) 766 - 767 2014年12月
-
マトロイド的選択関数
横井 優
日本オペレーションズ・リサーチ学会秋季研究発表会アブストラクト集 2014 202 - 203 2014年8月
-
準M♮凹評価関数を用いた一般化安定結婚モデル
横井 優, 室田 一雄
日本オペレーションズ・リサーチ学会春季研究発表会アブストラクト集 2014 134 - 135 2014年3月
-
整数格子点上の安定結婚問題がもつ束構造
横井 優, 室田 一雄
日本オペレーションズ・リサーチ学会秋季研究発表会アブストラクト集 2013 112 - 113 2013年9月
講演・口頭発表等
-
Popular Arborescences and Their Matroid Generalization 国際共著
Telikepalli Kavitha, Kazuhisa Makino, Ildikó Schlotter, Yu Yokoi
The 13th Hungarian-Japanese Symposium on Discrete Mathematics and Its Applications 2025年5月
-
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 招待
岩田 覚, 横井 優
電子情報通信学会コンピュテーション研究会 2020年12月
-
安定マッチング理論と展開型マッチングゲーム 招待
横井 優
第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
岩田 覚, 横井 優
離散数学とその応用研究集会2019 (JCCA 2019) 2019年8月
-
Finding a Stable Allocation in Polymatroid Intersection
岩田 覚, 横井 優
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, 国際会議
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
横井 優
The Third International Workshop on Matching Under Preferences 2015年4月
-
A Generalized Polymatroid Approach to Stable Allocations with Lower Quotas
横井 優
The 9th Hungarian-Japanese Symposium on Discrete Mathematics and Its Applications 2015年6月
-
A Generalized Polymatroid Approach to Stable Allocations with Lower Quotas
横井 優
The 22nd International Symposium on Mathematical Programming (ISMP 2015) 2015年7月
-
On the Lattice Structure of Stable Allocations in Two-Sided Discrete-Concave Market 招待
横井 優
The First International Workshop on Market Design Technologies for Sustainable Development 2013年11月
-
選好に同順位を含むマッチングモデルでの安定解の最適化 招待
横井優
電気通信大学 第38回情報数理工学セミナー 2021年7月
受賞
-
第11回 研究賞奨励賞
2021年9月 日本オペレーションズ・リサーチ学会
-
第15回 若手優秀講演賞（2018年度）
2019年6月 日本応用数理学会
横井 優
共同研究・競争的資金等の研究課題
-
選好下のマッチングが生みだす構造の解明と活用
研究課題/領域番号：JPMJPR212B 2021年10月 - 2025年3月
国立研究開発法人 科学技術振興機構 さきがけ
横井 優
担当区分：研究代表者
-
選好下のマッチングが生みだす構造の解明と活用
研究課題/領域番号：21460744 2021年 - 2024年
科学技術振興機構 戦略的な研究開発の推進/戦略的創造研究推進事業/さきがけ
横井 優
人と人、もしくは人と組織との間で、参加者の選好にもとづき効率的で公平なマッチングを計算するための理論は、近年大きく発展しています。本研究では、参加者がもつ様々な選好を表せる表現力豊かなモデルを考え、望ましいマッチングの集合がなす構造を解析します。そしてその結果を活かし、人々の戦略的な振る舞いも考慮しながら、公平性や最適性を達成するアルゴリズムの設計に取り組みます。
-
定量的解析に基づく市場メカニズムの評価と最適化
2018年4月 - 2022年3月
日本学術振興会 若手研究
横井 優
担当区分：研究代表者 資金種別：競争的資金
-
組合せ最適化にもとづく安定マッチングの理論と応用
研究課題/領域番号：15J09039 2015年4月 - 2017年3月
日本学術振興会 科学研究費助成事業 特別研究員奨励費
横井 優
配分額：1700000円 （ 直接経費：1700000円 ）
安定マッチングモデルは，研修医配属システムや学校選択制度などに応用をもつ数理モデルであり，経済学や数学，計算機科学といった様々な方面から研究されている．本研究では，組合せ最適化を用いたアプローチにより，安定マッチング理論における以下の成果を得た．
１．多対一の安定マッチング問題では，研修医と病院になぞらえられる二つの集合間で，各主体の選好を考慮した“安定な”マッチングを見つけることを考える．各病院が割当人数に上限しかもたない場合には安定マッチングの存在が保証できるが，下限ももつ場合には保証できない． 安定マッチングをもたない問題例に対しては，その緩和である envy-free マッチングを発見することが，代替策として考えられる．本研究では，下限付き多対一安定マッチングモデルにおける envy-free マッチングの存在性について考察した．そして，基本的な設定および，マトロイド的構造を持った拡張モデルに対し，効率的に envy-free マッチングの存在判定をするアルゴリズムを設計した．また，より一般的なモデルにおける存在性判定の計算困難性(NP困難性)を示した．
２．昨年度の研究では，ポリマトロイドという構造上の安定マッチングを算出する初の強多項式時間アルゴリズムを設計した．本年度の研究では，そのアルゴリズムの出力が単に安定であるだけでなく，多数存在し得る安定解の中で，ある種の最適性を満たすものであるということを示した．
<BR>
また，安定マッチングを数学的に拡張した概念(半順序対のカーネル)を用いて，リスト優モジュラ彩色という組合せ的問題に対して，彩色の存在を保証するリスト長の特徴付けを与えた．