Yutaro YAMAGUCHI

Assistant Professor

Department of Information and Physical Sciences,

Graduate School of Information Science and Technology,

Osaka University

Information Science and Technology Building C, Room C501,

1-5 Yamadaoka, Suita, Osaka 565-0871, Japan

Tel: +81-6-6879-7872

Email: yutaro_yamaguchi [at] ist.osaka-u.ac.jp

(old: ymgc [at] kurims.kyoto-u.ac.jp, yutaro_yamaguchi [at] mist.i.u-tokyo.ac.jp)

C.V.

March 2008: Graduation from Tennoji High School attached to Osaka Kyoiku University, Japan.

March 2011: Withdrawal from Undergraduate School of Informatics and Mathematical Science,

Faculty of Engineering, Kyoto University, Japan. (Due to proceeding to master's course.)

March 2013: **Master of Science** from Department of Mathematical Sciences,

Graduate School of Science, Kyoto University, Japan.

March 2016: **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.

Feb. 2013 – Mar. 2013: Project Assistant of JST ERATO Kawarabayashi Large Graph Project (Link)

"The Network Graph Theories and Optimization" Group.

Apr. 2013 – Mar. 2016: Research Fellow of the Japan Society for the Promotion of Science (DC1).

Apr. 2016 – Today: Assistant Professor at Osaka University.

Aug. 2017 – Today: Visiting Researcher at Discrete Optimization Unit, RIKEN Center for Advanced Intelligence Project.

Apr. 2013 – Mar. 2018: Research Collaborator of JST ERATO Kawarabayashi Large Graph Project (Link)

"The Network Graph Theories and Optimization" Group.

Aug. 2013 – Sep. 2013: Visit to NEC Laboratories at Kawasaki, Kanagawa, Japan.

Feb. 2014 – Mar. 2014: Visit to NEC Laboratories America at Cupertino, California, U.S.

Oct. 2014 – Today: Research Collaborator of "Developing Optimal Modeling Methods for Large-Scale Complex Systems" Team (Link)

in JST CREST "Modeling Methods allied with Modern Mathematics" Area.

Aug. 2017 – Sep. 2017: Visit to Minato Discrete Structure Manipulation System Project at Hokkaido University, Japan.

Sep. 2019 – Nov. 2019: Visit to Egerváry Research Group on Combinatorial Optimization (EGRES) in Eötvös Loránd University, Hungary.

Oct. 2013 – Mar. 2014: Teaching Assistant of the class "Algorithm Design" at Department of Mathematical Informatics,

Graduate School of Information Science and Technology, University of Tokyo.

Oct. 2014 – Mar. 2015: Teaching Assistant of the class "Algorithm Design" at Department of Mathematical Informatics,

Graduate School of Information Science and Technology, University of Tokyo.

Apr. 2015 – Aug. 2015: Teaching Assistant of "First-Year Seminar for Natural Sciences Students"

(Theme: Introduction to Operations Research) at College of Arts and Sciences, University of Tokyo.

1st Semester in 2017: "Information Literacy A" at Division of Applied Science, School of Engineering, Osaka University.

2nd Semester in 2017: "Exercises in Information Physics and Sciences I" at Department of Applied Physics, School of Engineering, Osaka University.

1st Semester in 2018: "Information Literacy A" at Division of Applied Science, School of Engineering, Osaka University.

2nd Semester in 2018: "Exercises in Information Physics and Sciences I" at Department of Applied Physics, School of Engineering, Osaka University.

Apr. 2013 – Mar. 2016: Grant-in-Aid for JSPS Research Fellow (No. 13J02522).

Aug. 2016 – Mar. 2018: JSPS KAKENHI, Grant-in-Aid for Research Activity Start-up (No. 16H06931).

Dec. 2016 – Mar. 2018: JST ACT-I "Information and Future" (No. JPMJPR16UR).

Apr. 2013 – Mar. 2016: A student member of the Operations Research Society of Japan (No. 05000219).

During 2015: A student member of the Institute of Electrical and Electronics Engineers (IEEE) (No. 93303728).

Apr. 2016 – Today: A member of the Operations Research Society of Japan (No. 05000219).

Apr. 2018 – Today: A member of the Japan Society for Industrial and Applied Mathematics (No. 164-596-5504).

Research Interests

Combinatorial Optimization, Graph Theory, Matroid Theory, Discrete Algorithms, Game Theory, Quantum Computing, Machine Learning, etc.

Pubilications

9. Yasushi Kawase, Yusuke Kobayashi, __Yutaro Yamaguchi__: **Finding a Path with Two Labels Forbidden in Group-Labeled Graphs**.

*Journal of Combintorial Theory, Series B*, accepted.

8. Yasushi Kawase, __Yutaro Yamaguchi__, Yu Yokoi: **Subgame Perfect Equilibria of Sequential Matching Games**.

*ACM Transactions on Economics and Computation*, accepted.

7. Takanori Maehara, __Yutaro Yamaguchi__: **Stochastic Packing Integer Programs with Few Queries**.

*Mathematical Programming* (*Series A*), in press (available online).

6. Yasushi Kawase, __Yutaro Yamaguchi__: **Antimatroids Induced by Matchings**.

*Discrete Applied Mathematics*, **257** (2019), pp. 342–349.

5. Kristóf Bérczi, Satoru Iwata, Jun Kato, __Yutaro Yamaguchi__: **Making Bipartite Graphs DM-irreducible**.

*SIAM Journal on Discrete Mathematics*, **32**:1 (2018), pp. 560–590.

4. Shin-ichi Tanigawa, __Yutaro Yamaguchi__: **Packing Non-zero A-paths via Matroid Matching**.

3. __Yutaro Yamaguchi__: **Realizing Symmetric Set Functions as Hypergraph Cut Capacity**.

*Discrete Mathematics*, **339**:8 (2016), pp. 2007–2017.

2. __Yutaro Yamaguchi__: **Packing A-paths in Group-Labelled Graphs via Linear Matroid Parity**.

1. __Yutaro Yamaguchi__, Anna Ogawa, Akiko Takeda, Satoru Iwata: **Cyber Security Analysis of Power Networks by Hypergraph Cut Algorithms**.

*IEEE Transactions on Smart Grid*, **6**:5 (2015), pp. 2189–2199.

9. __Yutaro Yamaguchi__: **A Strongly Polynomial Algorithm for Finding a Shortest Non-zero Path in Group-Labeled Graphs**.

*Proceedings of the 31st Annual ACM-SIAM Symposium on Discrete Algorithms* (*SODA 2020*), to appear.

8. Yoichi Iwata, __Yutaro Yamaguchi__, Yuichi Yoshida: **0/1/all CSPs, Half-Integral A-path Packing, and Linear-Time FPT Algorithms**.

7. Yasushi Kawase, __Yutaro Yamaguchi__, Yu Yokoi: **Computing a Subgame Perfect Equilibrium of a Sequential Matching Game**.

*Proceedings of the 19th ACM Conference on Economics and Computation* (*EC 2018*), pp. 131–148, 2018.

6. Takanori Maehara, __Yutaro Yamaguchi__: **Stochastic Packing Integer Programs with Few Queries**.

*Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms* (*SODA 2018*), pp. 293–310, 2018.

5. __Yutaro Yamaguchi__: **Shortest Disjoint S-paths via Weighted Linear Matroid Parity**.

4. Naoto Ohsaka, __Yutaro Yamaguchi__, Naonori Kakimura, Ken-ichi Kawarabayashi: **Maximizing Time-decaying Influence in Social Networks**.

*Proceedings of European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases*

(*ECML-PKDD 2016*), pp. 132–147, 2016.

3. Yasushi Kawase, Yusuke Kobayashi, __Yutaro Yamaguchi__: **Finding a Path in Group-Labeled Graphs with Two Labels Forbidden**.

*Proceedings of the 42nd International Colloquium on Automata, Languages, and Programming* (*ICALP 2015*), pp. 797–809, 2015.

* The full version is available here.

2. __Yutaro Yamaguchi__, Anna Ogawa, Akiko Takeda, Satoru Iwata: **Cyber Security Analysis of Power Networks by Hypergraph Cut Algorithms**.

*Proceedings of the 5th IEEE International Conference on Smart Grid Communications* (*SmartGridComm 2014*), pp. 830–835, 2014.

1. __Yutaro Yamaguchi__: **Packing A-paths in Group-Labelled Graphs via Linear Matroid Parity**.

17. Kristóf Bérczi, Tamás Schwarcz, __Yutaro Yamaguchi__: **List Colouring of Two Matroids through Reduction to Partition Matroids**.

*arXiv preprints*, arXiv:1911.10485 (Link), 2019.

16. Takanori Maehara, So Nakashima, __Yutaro Yamaguchi__:

**Multiple Knapsack-Constrained Monotone DR-Submodular Maximization on Distributive Lattice — Continuous Greedy Algorithm on Median Complex —**.

*arXiv preprints*, arXiv:1907.04279 (Link), 2019.

15. Takanori Maehara, __Yutaro Yamaguchi__: **Stochastic Monotone Submodular Maximization with Queries**.

*arXiv preprints*, arXiv:1907.04083 (Link), 2019.

14. __Yutaro Yamaguchi__: **A Strongly Polynomial Algorithm for Finding a Shortest Non-zero Path in Group-Labeled Graphs**.

*arXiv preprints*, arXiv:1906.04062 (Link), 2019.

13. Yasushi Kawase, Yusuke Kobayashi, __Yutaro Yamaguchi__: **Tight Approximation for Unconstrained XOS Maximization**.

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

12. Yasushi Kawase, __Yutaro Yamaguchi__, Yu Yokoi: **Subgame Perfect Equilibria of Sequential Matching Games**.

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

* A preliminary version was entitled **Computing a Subgame Perfect Equilibrium of a Sequential Matching Game**.

11. Takanori Maehara, __Yutaro Yamaguchi__: **Stochastic Packing Integer Programs with Few Queries**.

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

10. Yasushi Kawase, __Yutaro Yamaguchi__: **Antimatroids Induced by Matchings**.

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

9. Yoichi Iwata, __Yutaro Yamaguchi__, Yuichi Yoshida: **0/1/all CSPs, Half-Integral A-path Packing, and Linear-Time FPT Algorithms**.

* A preliminary version was entitled

8. Kristóf Bérczi, Satoru Iwata, Jun Kato, __Yutaro Yamaguchi__: **Making Bipartite Graphs DM-irreducible**.

*arXiv preprints*, arXiv:1612.08828 (Link), 2016.

* A preliminary version had appeared as a Mathematical Engineering Technical Report, METR 2016-14 (Link).

7. Yoshinobu Kawahara, __Yutaro Yamaguchi__:

**Parametric Maxflows for Structured Sparse Learning with Convex Relaxations of Submodular Functions**.

*arXiv preprints*, arXiv:1509.03946 (Link), 2015.

6. __Yutaro Yamaguchi__: **Shortest Disjoint Non-zero A-paths via Weighted Matroid Matching**.

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

5. Yasushi Kawase, Yusuke Kobayashi, __Yutaro Yamaguchi__: **Finding a Path with Two Labels Forbidden in Group-Labeled Graphs**.

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

* A preliminary version had appeared in 2014 as a Mathematical Engineering Technical Report, METR 2014-41 (Link),

entitled **Finding a Path in Group-Labeled Graphs with Two Labels Forbidden**.

4. __Yutaro Yamaguchi__: **Realizing Symmetric Set Functions as Hypergraph Cut Capacity**.

*Mathematical Engineering Technical Reports*, METR 2014-28 (Link),

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

3. __Yutaro Yamaguchi__, Anna Ogawa, Akiko Takeda, Satoru Iwata: **Cyber Security Analysis of Power Networks by Hypergraph Cut Algorithms**.

*Mathematical Engineering Technical Reports*, METR 2014-12 (Link),

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

2. __Yutaro Yamaguchi__: **Packing A-paths in Group-Labelled Graphs via Linear Matroid Parity**.

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

1. Shin-ichi Tanigawa, __Yutaro Yamaguchi__: **Packing Non-zero A-paths via Matroid Matching**.

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

[Ph.D. Thesis] *Combinatorial Optimization on Group-Labeled Graphs*. (Supervised by Prof. Satoru Iwata)

Department of Mathematical Informatics, Graduate School of Information Science and Technology, University of Tokyo, Japan, March 2016.

[Master's Thesis] *Structures and Algorithms for Path-Packing Problems*. (Supervised by Prof. Satoru Iwata)

Department of Mathematical Sciences, Graduate School of Science, Kyoto University, Japan, January 2013.

9. Takanori Maehara, __Yutaro Yamaguchi__: **A Unified Framework for Combinatorial Optimization with Queries**.

*Bulletin of the Japan Society for Industrial and Applied Mathematics*, **29**:2, pp. 2–9, 2019.

* This article is written in Japanese except for the abstract, and the English title is informal.

8. __Yutaro Yamaguchi__: **An Efficient Dijkstra-Like Algorithm for Finding a Shortest Non-zero Path in Group-Labeled Graphs**.

*Proceedings of the 11th Hungarian-Japanese Symposium on Discrete Mathematics and Its Applications*, pp. 479–485, 2019.

7. Takanori Maehara, __Yutaro Yamaguchi__: **Stochastic Monotone Submodular Maximization with Queries**.

*Proceedings of the 11th Hungarian-Japanese Symposium on Discrete Mathematics and Its Applications*, pp. 46–56, 2019.

6. Yusuke Kobayashi, __Yutaro Yamaguchi__: **On Applications of Weighted Linear Matroid Parity**.

*Proceedings of the 10th Japanese-Hungarian Symposium on Discrete Mathematics and Its Applications*, pp. 363–372, 2017.

5. Ryohei Fujimaki, __Yutaro Yamaguchi__, Riki Eto: **Piecewise Sparse Linear Classification via Factorized Asymptotic Bayesian Inference**.

*Transactions of the Japanese Society for Artificial Intelligence*, **31**:6 (2016), No. AI30-I_1-9 (Link).

* This article is written in Japanese except for the title and abstract.

4. __Yutaro Yamaguchi__: **Realizing Symmetric Set Functions as Hypergraph Cut Capacity**.

*Proceedings of the 9th Hungarian-Japanese Symposium on Discrete Mathematics and Its Applications*, pp. 137–146, 2015.

3. Yasushi Kawase, Yusuke Kobayashi, __Yutaro Yamaguchi__: **Finding a Zero Path in Z _{3}-Labeled Graphs**.

Research Institute for Mathematical Sciences (RIMS), Kyoto University, Japan, 2015.

* This is a resume of the technical report METR 2014-41.

2. __Yutaro Yamaguchi__: **Packing A-paths in Group-Labelled Graphs via Linear Matroid Parity**.

Research Institute for Mathematical Sciences (RIMS), Kyoto University, Japan, 2014.

* This is a resume of the same-title paper in SODA 2014.

1. __Yutaro Yamaguchi__: **Packing A-paths in Group-Labelled Graphs via Matroid Matching**.

International Talks

15. __Yutaro Yamaguchi__: **A Strongly Polynomial Algorithm for Finding a Shortest Non-zero Path in Group-Labeled Graphs**.

The 31st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2020), Salt Lake City, Utah, U.S., January 2020.

14. __Yutaro Yamaguchi__: **An Efficient Dijkstra-Like Algorithm for Finding a Shortest Non-zero Path in Group-Labeled Graphs**.

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

13. Kristóf Bérczi, Satoru Iwata, Jun Kato, __Yutaro Yamaguchi__: **Making Bipartite Graphs DM-irreducible**.

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

12. Yusuke Kobayashi, __Yutaro Yamaguchi__: **On Applications of Weighted Linear Matroid Parity**.

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

11. __Yutaro Yamaguchi__: **Shortest Disjoint S-paths via Weighted Linear Matroid Parity**.

The 27th International Symposium on Algorithms and Computation (ISAAC 2016), Sydney, Australia, December 2016. (Slide)

10. Satoru Iwata, Jun Kato, __Yutaro Yamaguchi__: **How to Make a Bipartite Graph DM-irreducible by Adding Edges**.

The Japanese Conference on Combinatorics and its Applications (JCCA 2016), Kyoto, Japan, May 2016. (Slide)

9. Satoru Iwata, Jun Kato, __Yutaro Yamaguchi__: **How to Make a Bipartite Graph DM-irreducible by Adding Edges**.

NII Shonan Meeting Seminar 071 "Current Trend in Combinatorial Optimization," Kanagawa, Japan, April 2016. (Slide)

8. __Yutaro Yamaguchi__: **Packing Non-zero A-paths via Linear Matroid Parity**.

The 6th Cargèse Workshop on Combinatorial Optimization, Cargèse, Corsica, France, September 2015. (Slide)

7. Shin-ichi Tanigawa, __Yutaro Yamaguchi__: **Packing Non-zero A-paths via Matroid Matching**.

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

6. Yasushi Kawase, Yusuke Kobayashi, __Yutaro Yamaguchi__: **Finding a Path in Group-Labeled Graphs with Two Labels Forbidden**.

The 42nd International Colloquium on Automata, Languages, and Programming (ICALP 2015), Kyoto, Japan, July 2015. (Slide)

5. __Yutaro Yamaguchi__: **Realizing Symmetric Set Functions as Hypergraph Cut Capacity**.

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

4. __Yutaro Yamaguchi__: **Packing A-paths in Group-Labeled Graphs via Linear Matroid Parity**.

IMA Annual Program Year Workshop "Convexity and Optimization: Theory and Applications,"

Minneapolis, Minnesota, U.S., February 2015. (Poster, Summary)

3. __Yutaro Yamaguchi__, Anna Ogawa, Akiko Takeda, Satoru Iwata: **Cyber Security Analysis of Power Networks by Hypergraph Cut Algorithms**.

The 5th IEEE International Conference on Smart Grid Communications (SmartGridComm 2014), Venice, Italy, November 2014. (Slide)

2. __Yutaro Yamaguchi__: **Packing A-paths in Group-Labelled Graphs via Linear Matroid Parity**.

The 25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2014), Portland, Oregon, U.S., January 2014. (Slide)

1. __Yutaro Yamaguchi__: **Packing A-paths in Group-Labelled Graphs via Matroid Matching**.

The 8th Japanese-Hungarian Symposium on Discrete Mathematics and Its Applications, Veszprém, Hungary, June 2013.

Visited Cities

19. **Eger, Tokaj, Visegrad, and Szeged** in **Hungary**,

**Wien (Vienna)** in **Austria**, **Praha (Prague)** in **Czech Republic**, and **Dubrovnik** in **Croatia**:

October – November 2019, Private Visits (Weekend Trips).

18. **Bordeaux** in **France**: July 2018,

Talk in the 23rd International Symposium on Mathematical Programming (ISMP 2018).

17. **Ithaca** in **New York**, **U.S.**: June 2018,

The 19th ACM Conference on Economics and Computation (EC 2018).

16. **New Orleans** in **Louisiana**, **U.S.**: January 2018,

The 29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2018).

15. **Barcelona** in **Spain**: January 2017,

The 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2017).

14. **Sydney** in **Australia**: December 2016,

Talk in the 27th International Symposium on Algorithms and Computation (ISAAC 2016).

13. **Arlington** in **Virginia**, **U.S.**: January 2016,

The 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2016).

12. **Bonn** (+ **Frankfurt**, **Stuttgart**, **München (Munich)**, **Köln**, and **Mainz**) in **Germany**: October 2015,

HIM Trimester Program "Combinatorial Optimization," Rigidity Workshop.

11. **Cargèse** in **Corsica** (+ **Paris**), **France**: September 2015,

Talk in the 6th Cargèse Workshop on Combinatorial Optimization.

10. **Seattle** in **Washington**, **U.S.**: August 2015,

Private Visit.

9. **Pittsburgh** in **Pennsylvania**, **U.S.**: July 2015,

Talk in the 22nd International Symposium on Mathematical Programming (ISMP 2015).

8. **Minneapolis** in **Minnesota**, **U.S.**: February 2015,

IMA Annual Program Year Workshop "Convexity and Optimization: Theory and Applications."

7. **Venezia (Venice)** in **Italy**: November 2014,

Talk in the 5th IEEE International Conference on Smart Grid Communications (SmartGridComm 2014).

6. **Budapest** in **Hungary**: June 2014, May 2017, September – November 2019;

Summer School in Mathematics at Institute of Mathematics in Eötvös Loránd University,

Talk in the 10th Japanese-Hungarian Symposium on Discrete Mathematics and Its Applications,

Research Visit to Egerváry Research Group on Combinatorial Optimization (EGRES).

5. **Silicon Valley (San Jose, Mountain View, Cupertino)** and **San Francisco** (+ **Yosemite Park**) in **California**, **U.S.**: February and March 2014,

Joint Research to NEC Laboratories America at Cupertino.

4. **Portland** in **Oregon**, **U.S.**: January 2014,

Talk in the 25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2014).

3. **Veszprém** in **Hungary**: June 2013,

Talk in the 8th Japanese-Hungarian Symposium on Discrete Mathematics and Its Applications.

2. **Zurich** and **Engelberg** in **Switzerland**: March 2012,

The 1st ETH-Japan Symposium for the Promotion of Academic Exchanges and the 1st ETH-Japan Workshop on Science and Computing.

1. **Toronto** and **Waterloo** in **Canada**: September 2011,

Invited to a special program on Quantum Computing at Institute for Quantum Computing (IQC) in University of Waterloo.