Yu YOKOI

>> Japanese Version

Assistant Professor

National Institute of Informatics (NII)

Tel: +81-3-4212-2832

E-mail: yokoi [at] nii.ac.jp

(previous: yu_yokoi [at] mist.i.u-tokyo.ac.jp)

Research Interests

Combinatorial Optimization, Matroid Theory, Stable Matching, Game Theory, Mathematical Economics etc.

C.V.

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.

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.

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).

From April 2017: Assistant Professor at National Institute of Informatics (NII).

April 2015 - March 2017: JSPS Research Fellowship for Young Scientists (DC2).

From April 2017: Assistant Professor at National Institute of Informatics (NII).

Pubilications

12. Tamás Király, __Yu Yokoi__:
**Equitable Partitions into Matchings and Coverings in Mixed Graphs**.

*Discrete Mathematics*, **345**(1), 112651, 2022.

11. Satoru Fujishige, Kenjiro Takazawa, and __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.

9. Satoru Iwata, __Yu Yokoi__:
**Finding a Stable Allocation in Polymatroid Intersection**.

*Mathematics of Operations Research*, **45**(1), pp. 63-85, 2020.

8. Yasushi Kawase, Yutaro Yamaguchi, and __Yu Yokoi__:
**Subgame Perfect Equilibria of Sequential Matching Games**.

*ACM Transactions on Economics and Computation*, **7**(4), No. 21, 30pp., 2020.

7. __Yu Yokoi__:
**Matroidal Choice Functions**.

*SIAM Journal on Discrete Mathematics*, **33**(3), pp. 1712-1724, 2019.

6. __Yu Yokoi__:
**List Supermodular Coloring with Shorter Lists**.

*Combinatorica*, **39**(2), pp. 459-475, 2019.

5. Kenjiro Takazawa, __Yu Yokoi__:
**A Generalized-Polymatroid Approach to Disjoint Common Independent Sets in Two Matroids**.

*Discrete Mathematics*, **342**(7), pp. 2002–2011, 2019.

4. Satoru Iwata, __Yu Yokoi__:
**List Supermodular Coloring**.

*Combinatorica*, **38**(6), pp. 1437–1456, 2018.

3. 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.

2. __Yu Yokoi__:
**A Generalized Polymatroid Approach to Stable Matchings with Lower Quotas**.

*Mathematics of Operations Research*, **42**(1), pp. 238--255, 2017.

1. 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.

5. __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)*, accepted.

4. 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..

3. 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.

2. __Yu Yokoi__:
**Envy-free Matchings with Lower Quotas**.

*Proceedings of the 28th International Symposium on Algorithms and Computation (ISAAC 2017)*, No. 67, 12pages, 2017.

1. 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.

15. 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.

14. __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.

12. 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.

11. Satoru Iwata, __Yu Yokoi__:
**A Blossom Algorithm for Maximum Edge-Disjoint ***T*-Paths.

*Mathematical Engineering Technical Reports No. METR 2019-16* (Link),

Department of Mathematical Engineering and Information Physics, Faculty of Engineering, University of Tokyo, Japan, 2019.

Department of Mathematical Engineering and Information Physics, Faculty of Engineering, University of Tokyo, Japan, 2019.

10. Tamás Király, __Yu Yokoi__:
**Equitable Partitions into Matchings and Coverings in Mixed Graphs**.

*arXiv preprints*, arXiv:1811.07856 (Link), 2018.

9. Kenjiro Takazawa, __Yu Yokoi__:
**A Generalized-Polymatroid Approach to Disjoint Common Independent Sets in Two Matroids**.

*arXiv preprints*, arXiv:1805.05528 (Link), 2018.

8. Yasushi Kawase, Yutaro Yamaguchi, __Yu Yokoi__:
**Computing a Subgame Perfect Equilibrium of a Sequential Matching Game**.

*arXiv preprints*, arXiv:1804.10353 (Link), 2018.

7. __Yu Yokoi__:
**List Supermodular Coloring with Shorter Lists**.

*arXiv preprints*, arXiv:1707.05417 (Link), 2017.

5. 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.

Department of Mathematical Engineering and Information Physics, Faculty of Engineering, University of Tokyo, Japan, 2017.

4. 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.

Department of Mathematical Engineering and Information Physics, Faculty of Engineering, University of Tokyo, Japan, 2016.

3. __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.

Department of Mathematical Engineering and Information Physics, Faculty of Engineering, University of Tokyo, Japan, 2015.

2. __Yu Yokoi__:
**Matroidal Choice Functions**.

*Mathematical Engineering Technical Reports No. METR 2014-32* (Link),

Department of Mathematical Engineering and Information Physics, Faculty of Engineering, University of Tokyo, Japan, 2014.

* A revised version is available here.

Department of Mathematical Engineering and Information Physics, Faculty of Engineering, University of Tokyo, Japan, 2014.

* A revised version is available here.

1. 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.

Department of Mathematical Engineering and Information Physics, Faculty of Engineering, University of Tokyo, Japan, 2013.

[Ph.D. Thesis]
**Stable Matchings on Matroidal Structures**,

University of Tokyo, Japan, 2017 (supervised by Satoru Iwata).

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).

University of Tokyo, Japan, 2014 (supervised by Kazuo Murota).

Talks

14. __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.

Dagstuhl Seminar (on Matching Under Preferences: Theory and Practice), Germany hybrid, July 2021.

13. 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.

The 11th Hungarian-Japanese Symposium on Discrete Mathematics and Its Applications, Tokyo, Japan, May 2019.

12. Satoru Iwata, __Yu Yokoi__:
**List Supermodular Coloring**.

MFO Workshop on Combinatorial Optimization, Oberwolfach, Germany, November 2018.

MFO Workshop on Combinatorial Optimization, Oberwolfach, Germany, November 2018.

11. Satoru Iwata, __Yu Yokoi__:
**List Supermodular Coloring**.

The 23rd International Symposium on Mathematical Programming (ISMP2018), Bordeaux, France, July 2018.

The 23rd International Symposium on Mathematical Programming (ISMP2018), Bordeaux, France, July 2018.

10. 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 (EC2018), Ithaca, New York, U.S., June 2018.

The 19th ACM Conference on Economics and Computation (EC2018), Ithaca, New York, U.S., June 2018.

9. __Yu Yokoi__:
**Envy-free Matchings with Lower Quotas,**.

The 28th International Symposium on Algorithms and Computation (ISAAC 2017), Phuket, Thailand, December 2017.

The 28th International Symposium on Algorithms and Computation (ISAAC 2017), Phuket, Thailand, December 2017.

8. Satoru Iwata, __Yu Yokoi__:
**List Supermodular Coloring**.

The 10th Japanese-Hungarian Symposium on Discrete Mathematics and Its Applications, Budapest, Hungary, May 2017.

The 10th Japanese-Hungarian Symposium on Discrete Mathematics and Its Applications, Budapest, Hungary, May 2017.

7. __ 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.

The Fourth International Workshop on Matching Under Preferences, Cambridge, Massachusetts, U.S., April 2017.

6. 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.

The 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2016), Arlington, Virginia, U.S., January 2016.

5. Satoru Iwata, __Yu Yokoi__:
**Finding a Stable Allocation in Polymatroid Intersection**.

HIM Trimester Program "Combinatorial Optimization," Rigidity Workshop, Bonn, Germany, October 2015.

HIM Trimester Program "Combinatorial Optimization," Rigidity Workshop, Bonn, Germany, October 2015.

4. __ 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.

The 22nd International Symposium on Mathematical Programming (ISMP 2015), Pittsburgh, Pennsylvania, U.S., July 2015.

3. __ 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.

The 9th Hungarian-Japanese Symposium on Discrete Mathematics and Its Applications, Fukuoka, Japan, June 2015.

2. __ Yu Yokoi__:
**Matroidal Choice Functions**.

The Third International Workshop on Matching Under Preferences, Glasgow, U.K., April 2015.

The Third International Workshop on Matching Under Preferences, Glasgow, U.K., April 2015.

1. __ 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.

The First International Workshop on Market Design Technologies for Sustainable Development, Kanagawa, November 2013.