Photo

Yu YOKOI
>> Japanese Version

Associate Professor
Department of Mathematical and Computing Science,
School of Computing,
Institute of Science Tokyo (formerly Tokyo Institute of Technology)

E-mail: yokoi [at] c.titech.ac.jp
   (previous: yokoi [at] nii.ac.jp)

Research Interests
Combinatorial Optimization, Matroid Theory, Stable Matching, Game Theory, Mathematical Economics etc.
C.V.
Education
March 2008: Graduation from Aichi Prefectural Asahigaoka High School, Japan.
March 2012: Bachelor of Engineering from Faculty of Engineering Science, Osaka University, Japan.
March 2014: Master of Engineering from Department of Mathematical Informatics, Graduate School of Information Science and Technology, University of Tokyo, Japan.
March 2017: Doctor of Philosophy in the field of Mathematical Informatics from Department of Mathematical Informatics, Graduate School of Information Science and Technology, University of Tokyo, Japan.
Employment
January 2013 - March 2015: JST ERATO ERATO Kawarabayashi Large Graph Project (Link) Research Assistant.
April 2015 - March 2017: JSPS Research Fellowship for Young Scientists (DC2).
April 2017 - March 2023: Assistant Professor at National Institute of Informatics (NII).
From April 2023: Associate Professor at Tokyo Intitute of Technology.
Pubilications

Refereed Journal Articles
  1. Gergely Csáji, Tamás Király, Yu Yokoi:
    Solving the Maximum Popular Matching Problem with Matroid Constraints.
    SIAM Journal on Discrete Mathematics, 38(3), pp. 2226-2242, 2024.
  2. Hiromichi Goko, Ayumi Igarashi, Yasushi Kawase, Kazuhisa Makino, Hanna Sumita, Akihisa Tamura, Yu Yokoi, Makoto Yokoo:
    A fair and truthful mechanism with limited subsidy.
    Games and Economic Behavior, 144, pp. 49-70, 2024.
  3. Kohei Morita, Shinya Shiroshita, Yutaro Yamaguchi, Yu Yokoi:
    Fast Primal-Dual Update against Local Weight Update in Linear Assignment Problem and Its Application.
    Information Processing Letters, 183, No. 106432, 7pp, 2024.
  4. Satoru Iwata, Yu Yokoi:
    Finding Maximum Edge-Disjoint Paths Between Multiple Terminals.
    SIAM Journal on Computing, 52(5), pp. 1230-1268, 2023.
  5. Kristóf Bérczi, Tamás Király, Yutaro Yamaguchi, Yu Yokoi:
    Matroid Intersection under Restricted Oracles.
    SIAM Journal on Discrete Mathematics, 37(2), pp. 1311-1330, 2023
  6. Kristóf Bérczi, Tamás Király, Tamás Schwarcz, Yutaro Yamaguchi, Yu Yokoi:
    Hypergraph Characterization of Split Matroids.
    Journal of Combinatorial Theory, Series A, 194, No. 105697, 2023.
  7. Kristóf Bérczi, Tamás Király, Yutaro Yamaguchi, Yu Yokoi:
    Approximation by Lexicographically Maximal Solutions in Matching and Matroid Intersection Problems.
    Theoretical Computer Science, 910, pp. 48-53, 2022.
  8. Tamás Király, Yu Yokoi: Equitable Partitions into Matchings and Coverings in Mixed Graphs.
    Discrete Mathematics, 345(1), 112651, 2022.
  9. Satoru Fujishige, Kenjiro Takazawa, Yu Yokoi: A Note on a Nearly Uniform Partition into Common Independent Sets of Two Matroids.
    Journal of the Operations Research Society of Japan, 63(3), pp. 71-77, 2020.
  10. Yu Yokoi: Envy-Free Matchings with Lower Quotas.
    Algorithmica, 82(2), pp. 188-211, 2020.
  11. Satoru Iwata, Yu Yokoi: Finding a Stable Allocation in Polymatroid Intersection.
    Mathematics of Operations Research, 45(1), pp. 63-85, 2020.
  12. Yasushi Kawase, Yutaro Yamaguchi, Yu Yokoi: Subgame Perfect Equilibria of Sequential Matching Games.
    ACM Transactions on Economics and Computation, 7(4), No. 21, 30pp., 2020.
  13. Yu Yokoi: Matroidal Choice Functions.
    SIAM Journal on Discrete Mathematics, 33(3), pp. 1712-1724, 2019.
  14. Yu Yokoi: List Supermodular Coloring with Shorter Lists.
    Combinatorica, 39(2), pp. 459-475, 2019.
  15. Kenjiro Takazawa, Yu Yokoi: A Generalized-Polymatroid Approach to Disjoint Common Independent Sets in Two Matroids.
    Discrete Mathematics, 342(7), pp. 2002–2011, 2019.
  16. Satoru Iwata, Yu Yokoi: List Supermodular Coloring.
    Combinatorica, 38(6), pp. 1437–1456, 2018.
  17. Than Nguyen Hau, Naonori Kakimura, Ken-ichi Kawarabayashi, Yusuke Kobayashi, Tatsuya Matsuoka, Yu Yokoi:
    Optimal Cache Placement for an Academic Backbone Network.
    Journal of the Operations Research Society of Japan, 61(2), pp. 197–216, 2018.
  18. Yu Yokoi: A Generalized Polymatroid Approach to Stable Matchings with Lower Quotas.
    Mathematics of Operations Research, 42(1), pp. 238-255, 2017.
  19. Kazuo Murota, Yu Yokoi: On the Lattice Structure of Stable Allocations in Two-Sided Discrete-Concave Market.
    Mathematics of Operations Research, 40(2), pp. 460-473, 2015.

Refereed Conference Proceedings
  1. Telikepalli Kavitha, Kazuhisa Makino, Ildikó Schlotter, Yu Yokoi:
    Arborescences, Colorful Forests, and Popularity.
    Proceedings of the 35th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2024), pp.3724–3746, 2024.
  2. Yasushi Kawase, Hanna Sumita, Yu Yokoi:
    Random Assignment of Indivisible Goods under Constraints.
    Proceedings of the 32nd International Joint Conference on Artificial Intelligence (IJCAI-23), pp.2792–2799, 2023.
  3. Gergely Csáji, Tamás Király, Yu Yokoi:
    Approximation Algorithms for Matroidal and Cardinal Generalizations of Stable Matching.
    Proceedings of the Sixth SIAM Symposium on Simplicity of Algorithms (SOSA 2023), pp.103-113, 2023.
  4. Kazuhisa Makino, Shuichi Miyazaki, Yu Yokoi:
    Incomplete List Setting of the Hospitals/Residents Problem with Maximally Satisfying Lower Quotas.
    Proceedings of the 15th International Symposium on Algorithmic Game Theory (SAGT 2022), pp.544-561, 2022.
  5. Hiromichi Goko, Kazuhisa Makino, Shuichi Miyazaki, Yu Yokoi:
    Maximally Satisfying Lower Quotas in the Hospitals/Residents Problem with Ties.
    Proceedings of the 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022), No. 31, 20pages, 2022.
  6. Hiromichi Goko, Ayumi Igarashi, Yasushi Kawase, Kazuhisa Makino, Hanna Sumita, Akihisa Tamura, Yu Yokoi, Makoto Yokoo:
    Fair and Truthful Mechanism with Limited Subsidy.
    Proceedings of the International Conference on Autonomous Agents and Multi-Agent Systems 2022 (AAMAS2022), pp. 534-542, 2022.
  7. Yu Yokoi: An Approximation Algorithm for Maximum Stable Matching with Ties and Constraints.
    Proceedings of the 32nd International Symposium on Algorithms and Computation (ISAAC 2021), No. 71, 16pages, 2021.
  8. Satoru Iwata, Yu Yokoi: A Blossom Algorithm for Maximum Edge-Disjoint T-Paths.
    Proceedings of the 31st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2020), pp. 1933-1944, 2020.
  9. Yasushi Kawase, Yutaro Yamaguchi, and Yu Yokoi: Computing a Subgame Perfect Equilibrium of a Sequential Matching Game.
    Proceedings of the 19th ACM Conference on Economics and Computation (EC2018), pp. 131-148, 2018.
  10. Yu Yokoi: Envy-free Matchings with Lower Quotas.
    Proceedings of the 28th International Symposium on Algorithms and Computation (ISAAC 2017), No. 67, 12pages, 2017.
  11. Satoru Iwata, Yu Yokoi: Finding a Stable Allocation in Polymatroid Intersection.
    Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2016), pp. 1034-1047, 2016.

Preprints
  1. Gergely Csáji, Tamás Király, Kenjiro Takazawa, Yu Yokoi:
    Popular Maximum-Utility Matchings with Matroid Constraints.
    arXiv preprints, arXiv:2407.09798 (Link), 2024.
  2. Mihály Bárász, Kristóf Bérczi, Tamás Király, Yutaro Yamaguchi, Yu Yokoi:
    Matroid Intersection under Minimum Rank Oracle.
    arXiv preprints, arXiv:2407.03229 (Link), 2024.
  3. Kristóf Bérczi, Tamás Király, Yusuke Kobayashi, Yutaro Yamaguchi, Yu Yokoi:
    Finding Spanning Trees with Perfect Matchings.
    arXiv preprints, arXiv:2407.02958 (Link), 2024.
  4. Telikepalli Kavitha, Kazuhisa Makino, Ildikó Schlotter, Yu Yokoi:
    Arborescences, Colorful Forests, and Popularity.
    arXiv preprints, arXiv:2310.19455 (Link), 2023.
  5. Gergely Csáji, Tamás Király, Yu Yokoi:
    Solving the Maximum Popular Matching Problem with Matroid Constraints.
    arXiv preprints, arXiv:2209.02195 (Link), 2022.
  6. Gergely Csáji, Tamás Király, Yu Yokoi:
    Approximation Algorithms for Matroidal and Cardinal Generalizations of Stable Matching.
    arXiv preprints, arXiv:2208.09583 (Link), 2022.
  7. Kohei Morita, Shinya Shiroshita, Yutaro Yamaguchi, Yu Yokoi:
    Maintaining Optimality in Assignment Problem against Weight Updates around Vertices.
    arXiv preprints, arXiv:2208.11325 (Link), 2022.
  8. Yasushi Kawase, Hanna Sumita, Yu Yokoi:
    Random Assignment of Indivisible Goods under Constraints.
    arXiv preprints, arXiv:2208.07666 (Link), 2022.
  9. Kazuhisa Makino, Shuichi Miyazaki, Yu Yokoi:
    Incomplete List Setting of the Hospitals/Residents Problem with Maximally Satisfying Lower Quotas.
    arXiv preprints, arXiv:2203.06660 (Link), 2022.
  10. Kristóf Bérczi, Tamás Király, Tamás Schwarcz, Yutaro Yamaguchi, Yu Yokoi:
    Hypergraph Characterization of Split Matroids.
    arXiv preprints, arXiv:2202.0437 (Link), 2022.
  11. Kristóf Bérczi, Tamás Király, Yutaro Yamaguchi, Yu Yokoi:
    Approximation by Lexicographically Maximal Solutions in Matching and Matroid Intersection Problems.
    arXiv preprints, arXiv:2107.09897 (Link), 2021.
  12. Yu Yokoi: An Approximation Algorithm for Maximum Stable Matching with Ties and Constraints.
    arXiv preprints, arXiv:2107.03076 (Link), 2021.
  13. Hiromichi Goko, Kazuhisa Makino, Shuichi Miyazaki, Yu Yokoi:
    Maximally Satisfying Lower Quotas in the Hospitals/Residents Problem with Ties.
    arXiv preprints, arXiv:2105.03093 (Link), 2021.
  14. Hiromichi Goko, Ayumi Igarashi, Yasushi Kawase, Kazuhisa Makino, Hanna Sumita, Akihisa Tamura, Yu Yokoi, Makoto Yokoo:
    Fair and Truthful Mechanism with Limited Subsidy.
    arXiv preprints, arXiv:2105.01801 (Link), 2021.
  15. Satoru Iwata, Yu Yokoi: Finding Maximum Edge-Disjoint Paths Between Multiple Terminals.
    arXiv preprints, arXiv:909.07919 (Link).
    A preliminary version entiled A Blossom Algorithm for Maximum Edge-Disjoint T-Paths appeard at
    Mathematical Engineering Technical Reports No. METR 2019-16 (Link).
  16. Tamás Király, Yu Yokoi: Equitable Partitions into Matchings and Coverings in Mixed Graphs.
    arXiv preprints, arXiv:1811.07856 (Link), 2018.
  17. Kenjiro Takazawa, Yu Yokoi: A Generalized-Polymatroid Approach to Disjoint Common Independent Sets in Two Matroids.
    arXiv preprints, arXiv:1805.05528 (Link), 2018.
  18. Yasushi Kawase, Yutaro Yamaguchi, Yu Yokoi: Computing a Subgame Perfect Equilibrium of a Sequential Matching Game.
    arXiv preprints, arXiv:1804.10353 (Link), 2018.
  19. Yu Yokoi: List Supermodular Coloring with Shorter Lists.
    arXiv preprints, arXiv:1707.05417 (Link), 2017.
  20. Yu Yokoi: Envy-Free Matchings with Lower Quotas.
    arXiv preprints, arXiv:1704.04888 (Link), 2017.
  21. Satoru Iwata, Yu Yokoi: Finding a Stable Allocation in Polymatroid Intersection.
    Mathematical Engineering Technical Reports No. METR 2017-02 (Link),
    Department of Mathematical Engineering and Information Physics, Faculty of Engineering, University of Tokyo, Japan, 2017.
  22. Satoru Iwata, Yu Yokoi: List Supermodular Coloring.
    Mathematical Engineering Technical Reports No. METR 2016-10 (Link),
    Department of Mathematical Engineering and Information Physics, Faculty of Engineering, University of Tokyo, Japan, 2016.
  23. Yu Yokoi: A Generalized Polymatroid Approach to Stable Matchings with Lower Quotas.
    Mathematical Engineering Technical Reports No. METR 2015-21 (Link),
    Department of Mathematical Engineering and Information Physics, Faculty of Engineering, University of Tokyo, Japan, 2015.
  24. Yu Yokoi: Matroidal Choice Functions.
    Mathematical Engineering Technical Reports No. METR 2014-32,
    Department of Mathematical Engineering and Information Physics, Faculty of Engineering, University of Tokyo, Japan, 2014.
    * A revised version is available here.
  25. Kazuo Murota, Yu Yokoi: On the Lattice Structure of Stable Allocations in Two-Sided Discrete-Concave Market.
    Mathematical Engineering Technical Reports No. METR 2013-30 (Link),
    Department of Mathematical Engineering and Information Physics, Faculty of Engineering, University of Tokyo, Japan, 2013.

Thesis
[Ph.D. Thesis] Stable Matchings on Matroidal Structures,
University of Tokyo, Japan, 2017 (supervised by Satoru Iwata).
[Master's Thesis] Study on Stable Allocations in Two-Sided Discrete-Concave Market,
University of Tokyo, Japan, 2014 (supervised by Kazuo Murota).

Talks

  1. Telikepalli Kavitha, Kazuhisa Makino, Ildikó Schlotter, Yu Yokoi:
    Arborescences, Colorful Forests, and Popularity.
    The 35th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2024), Alexandria, Virginia, U.S., 2024.
  2. Yasushi Kawase, Hanna Sumita, Yu Yokoi:
    Random Assignment of Indivisible Goods under Constraints.
    The 32nd International Joint Conference on Artificial Intelligence (IJCAI-23), Macao, August 2023.
  3. Gergely Csáji, Tamás Király, Yu Yokoi:
    Solving the Maximum Popular Matching Problem with Matroid Constraints.
    The 12th Japanese-Hungarian Symposium on Discrete Mathematics and Its Applications, Budapest, Hungary, March 2023.
  4. Gergely Csáji, Tamás Király, Yu Yokoi:
    Approximation Algorithms for Matroidal and Cardinal Generalizations of Stable Matching.
    The Sixth SIAM Symposium on Simplicity of Algorithms (SOSA 2023), Florence, Italy, January 2023.
  5. Kazuhisa Makino, Shuichi Miyazaki, Yu Yokoi:
    Incomplete List Setting of the Hospitals/Residents Problem with Maximally Satisfying Lower Quotas.
    The 15th International Symposium on Algorithmic Game Theory (SAGT 2022), Colchester, U.K., September 2022.
  6. Yu Yokoi: Introduction to the theory of matching under preferences.
    Google APAC Research Talk, online, June 2022.
  7. Hiromichi Goko, Kazuhisa Makino, Shuichi Miyazaki, Yu Yokoi:
    Maximally Satisfying Lower Quotas in the Hospitals/Residents Problem with Ties.
    The 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022), online, March 2022.
  8. Yu Yokoi: An Approximation Algorithm for Maximum Stable Matching with Ties and Constraints.
    The 32nd International Symposium on Algorithms and Computation (ISAAC 2021), Fukuoka, Japan (hybrid), December 2021.
  9. Yu Yokoi: Approximability vs. Strategy-proofness in Stable Matching Problems with Ties.
    Dagstuhl Seminar (on Matching Under Preferences: Theory and Practice), Germany (hybrid), July 2021.
  10. Tamás Király, Yu Yokoi: Equitable Partitions into Matchings and Coverings in Mixed Graphs.
    The 11th Hungarian-Japanese Symposium on Discrete Mathematics and Its Applications, Tokyo, Japan, May 2019.
  11. Satoru Iwata, Yu Yokoi: List Supermodular Coloring.
    MFO Workshop on Combinatorial Optimization, Oberwolfach, Germany, November 2018.
  12. Satoru Iwata, Yu Yokoi: List Supermodular Coloring.
    The 23rd International Symposium on Mathematical Programming (ISMP 2018), Bordeaux, France, July 2018.
  13. Yasushi Kawase, Yutaro Yamaguchi, and Yu Yokoi: Computing a Subgame Perfect Equilibrium of a Sequential Matching Game,.
    The 19th ACM Conference on Economics and Computation (EC 2018), Ithaca, New York, U.S., June 2018.
  14. Yu Yokoi: Envy-free Matchings with Lower Quotas,.
    The 28th International Symposium on Algorithms and Computation (ISAAC 2017), Phuket, Thailand, December 2017.
  15. Satoru Iwata, Yu Yokoi: List Supermodular Coloring.
    The 10th Japanese-Hungarian Symposium on Discrete Mathematics and Its Applications, Budapest, Hungary, May 2017.
  16. Yu Yokoi: A Generalized Polymatroid Approach to Stable Allocations with Lower Quotas.
    The Fourth International Workshop on Matching Under Preferences, Cambridge, Massachusetts, U.S., April 2017.
  17. Satoru Iwata, Yu Yokoi: Finding a Stable Allocation in Polymatroid Intersection.
    The 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2016), Arlington, Virginia, U.S., January 2016.
  18. Satoru Iwata, Yu Yokoi: Finding a Stable Allocation in Polymatroid Intersection.
    HIM Trimester Program "Combinatorial Optimization," Rigidity Workshop, Bonn, Germany, October 2015.
  19. Yu Yokoi: A Generalized Polymatroid Approach to Stable Allocations with Lower Quotas.
    The 22nd International Symposium on Mathematical Programming (ISMP 2015), Pittsburgh, Pennsylvania, U.S., July 2015.
  20. Yu Yokoi: A Generalized Polymatroid Approach to Stable Allocations with Lower Quotas.
    The 9th Hungarian-Japanese Symposium on Discrete Mathematics and Its Applications, Fukuoka, Japan, June 2015.
  21. Yu Yokoi: Matroidal Choice Functions.
    The Third International Workshop on Matching Under Preferences, Glasgow, U.K., April 2015.
  22. Yu Yokoi: On the Lattice Structure of Stable Allocations in Two-Sided Discrete-Concave Market.
    The First International Workshop on Market Design Technologies for Sustainable Development, Kanagawa, November 2013.