顔写真

PHOTO

Yutaro YAMAGUCHI
山口 勇太郎
Yutaro YAMAGUCHI
山口 勇太郎
Institutional repository
Graduate School of Information Science and Technology　Department of Information and Physical Sciences, Associate Professor
Institutional repository

Research History 5

  1. 2021/09 - Present
    Osaka University　Department of Information and Physical Sciences, Graduate School of Information Science and Technology　Associate Professor

  2. 2020/03 - 2021/08
    Kyushu University　Department of Informatics, Faculty of Information Science and Electrical Engineering　Associate Professor

  3. 2020/06 - 2020/10
    RIKEN　Discrete Optimization Unit, RIKEN Center for Advanced Intelligence Project　Visiting Researcher

  4. 2017/08 - 2020/02
    RIKEN　Discrete Optimization Unit, RIKEN Center for Advanced Intelligence Project　Visiting Researcher

  5. 2016/04 - 2020/02
    Osaka University　Department of Information and Physical Sciences, Graduate School of Information Science and Technology　Assistant Professor

Education 4

  1. The University of Tokyo　The Graduate School of Information Science and Technology　Department of Mathematical Informatics

    2013/04 - 2016/03

  2. Kyoto University　Graduate School of Science　Division of Mathematics (Department of Mathematical Sciences)

    2011/04 - 2013/03

  3. Kyoto University　Faculty of Engineering　School of Informatics & Mathematical Science

    2008/04 - 2011/03

  4. Tennoji High School attached to Osaka Kyoiku University

    2005/04 - 2008/03

Committee Memberships 12

  1. 日本オペレーションズ・リサーチ学会 関西支部　運営委員　Academic society

    2022/02 - Present

  2. 日本オペレーションズ・リサーチ学会　2024年度関西支部若手研究発表会 実行委員長　Academic society

    2024/11 - 2024/11

  3. The 34th International Symposium on Algorithms and Computation (ISAAC 2023) Local Organizer　Other

    2023/12 - 2023/12

  4. LAシンポジウム　事務局　Academic society

    2021/04 - 2022/03

  5. 日本オペレーションズ・リサーチ学会 「超スマート社会のシステムデザインのための理論と応用」研究部会　幹事　Academic society

    2019/03 - 2022/02

  6. The 32nd International Symposium on Algorithms and Computation (ISAAC 2021) Local Organizer　Other

    2021/12 - 2021/12

  7. 日本オペレーションズ・リサーチ学会　2020年春季研究発表会 実行委員　Academic society

    2020/03 - 2020/03

  8. 日本オペレーションズ・リサーチ学会 関西支部　運営委員　Academic society

    2018/03 - 2020/02

  9. 京都大学 数理解析研究所 (RIMS)　RIMS共同研究 "International Workshop on Combinatorial Optimization and Algorithmic Game Theory" Organizer　Other

    2020/01 - 2020/01

  10. 日本オペレーションズ・リサーチ学会　関西支部シンポジウム 「ビッグデータ研究とは何か」 実行委員　Academic society

    2018/11 - 2018/11

  11. JST　第2回 JST 数学領域 未解決問題ワークショップ 運営代表　Government

    2018/09 - 2018/09

  12. 日本応用数理学会　2018年 研究部会連合発表会 実行委員　Academic society

    2018/03 - 2018/03

Research Areas 3

  1. Informatics / Information theory /

  2. Natural sciences / Applied mathematics and statistics /

  3. Informatics / Mathematical informatics /

Awards 1

  1. 人工知能学会創立30周年記念論文賞（優秀論文）

    藤巻 遼平, 山口 勇太郎, 江藤 力　The Japanese Society for Artificial Intelligence (JSAI)　2016/11

Papers 47

  1. Towards the Proximity Conjecture on Group-Labeled Matroids

    Dániel Garamvölgyi, Ryuhei Mizutani, Taihei Oki, Tamás Schwarcz, Yutaro Yamaguchi

    ICALP 2025　Vol. accepted　2025/07　Research paper (international conference proceedings)

  2. Finding Spanning Trees with Perfect Matchings

    Kristóf Bérczi, Tamás Király, Yusuke Kobayashi, Yutaro Yamaguchi, Yu Yokoi

    Discrete Applied Mathematics　Vol. 371　p. 137-147　2025/04　Research paper (scientific journal)

  3. An FPT Algorithm for the Exact Matching Problem and NP-hardness of Related Problems

    Hitoshi Murakami, Yutaro Yamaguchi

    IEICE Transactions on Information and Systems　Vol. E108.D　No. 3　p. 214-220　2025/03　Research paper (scientific journal)

  4. Fast Enumeration of All Cost-Bounded Solutions for Combinatorial Problems using ZDDs

    Shin-ichi Minato, Jun Kawahara, Mutsunori Banbara, Takashi Horiyama, Ichigaku Takigawa, Yutaro Yamaguchi

    Discrete Applied Mathematics　Vol. 360　p. 467-486　2025/01　Research paper (scientific journal)

  5. Rainbow Arborescence Conjecture

    Kristóf Bérczi, Tamás Király, Yutaro Yamaguchi, Yu Yokoi

    arXiv　2024/12　Research paper (bulletin of university, research institution)

  6. Shortest Odd Paths in Undirected Graphs with Conservative Weight Functions

    Alpár Jüttner, Csaba Király, Lydia Mirabel Mendoza-Cadena, Gyula Pap, Ildikó Schlotter, Yutaro Yamaguchi

    Discrete Applied Mathematics　Vol. 357　p. 34-50　2024/11　Research paper (scientific journal)

  7. Matroid Intersection under Minimum Rank Oracle

    Mihály Bárász, Kristóf Bérczi, Tamás Király, Yutaro Yamaguchi, Yu Yokoi

    arXiv　2024/07　Research paper (bulletin of university, research institution)

  8. Approximation and FPT Algorithms for Finding DM-Irreducible Spanning Subgraphs

    Ryoma Norose, Yutaro Yamaguchi

    arXiv　2024/04　Research paper (bulletin of university, research institution)

  9. 文字検査可能・区分検査可能・一般化有限確定言語における可測性の計算量解析

    稲葉 一浩, 新屋 良磨, 中村 誠希, 山口 勇太郎

    第26回プログラミングおよびプログラミング言語ワークショップ (PPL 2024) 論文集　2024/03　Research paper (conference, symposium, etc.)

  10. A Nearly Linear-Time Distributed Algorithm for Exact Maximum Matching

    Taisuke Izumi, Naoki Kitamura, Yutaro Yamaguchi

    SODA 2024　2024/01　Research paper (international conference proceedings)

  11. 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　Vol. 183　No. 106432　2024/01　Research paper (scientific journal)

  12. Matroid Intersection under Restricted Oracles

    Kristóf Bérczi, Tamás Király, Yutaro Yamaguchi, Yu Yokoi

    SIAM Journal on Discrete Mathematics　Vol. 37　No. 2　p. 1311-1330　2023/06　Research paper (scientific journal)

  13. 部分語の出現情報の検査のみで近似できる正規言語について

    新屋 良磨, 山口 勇太郎, 中村 誠希

    コンピュータソフトウェア　Vol. 40　No. 2　p. 49-60　2023/04　Research paper (scientific journal)

  14. 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　Vol. 194　No. 105697　2023/02　Research paper (scientific journal)

  15. Finding a Shortest Non-zero Path in Group-Labeled Graphs

    Yoichi Iwata, Yutaro Yamaguchi

    Combinatorica　Vol. 42　No. Suppl 2　p. 1253-1282　2022/09　Research paper (scientific journal)

  16. 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　Vol. 910　p. 48-53　2022/04　Research paper (scientific journal)

  17. An $O(n^2)$-Time Algorithm for Computing a Max-Min 3-Dispersion on a Convex Polygon

    Yasuaki Kobayashi, Shin-ichi Nakano, Kei Uchizawa, Takeaki Uno, Yutaro Yamaguchi, Katsuhisa Yamanaka

    IEICE Transactions on Information and Systems　Vol. E105.D　No. 3　p. 503-507　2022/03　Research paper (scientific journal)

  18. Interval-Memoized Backtracking on ZDDs for Fast Enumeration of All Lower Cost Solutions

    Shin-ichi Minato, Mutsunori Banbara, Takashi Horiyama, Jun Kawahara, Ichigaku Takigawa, Yutaro Yamaguchi

    arXiv preprints　2022/01　Research paper (bulletin of university, research institution)

  19. List Coloring of Two Matroids through Reduction to Partition Matroids

    Kristóf Bérczi, Tamás Schwarcz, Yutaro Yamaguchi

    SIAM Journal on Discrete Mathematics　Vol. 35　No. 3　p. 2192-2209　2021/12　Research paper (scientific journal)

  20. Dynamic Programming Approach to the Generalized Minimum Manhattan Network Problem

    Yuya Masumura, Taihei Oki, Yutaro Yamaguchi

    Algorithmica　Vol. 83　p. 3681-3714　2021/09　Research paper (scientific journal)

  21. Max-Min 3-dispersion on a Convex Polygon

    Yasuaki Kobayashi, Shin-ichi Nakano, Kei Uchizawa, Takeaki Uno, Yutaro Yamaguchi, Katsuhisa Yamanaka

    EuroCG 2021　2021/04　Research paper (international conference proceedings)

  22. Tight Approximation for Unconstrained XOS Maximization

    Yuval Filmus, Yasushi Kawase, Yusuke Kobayashi, Yutaro Yamaguchi

    Mathematics of Operations Research　Vol. 46　No. 4　p. 1599-1610　2021/03　Research paper (scientific journal)

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

    Takanori Maehara, So Nakashima, Yutaro Yamaguchi

    Mathematical Programming (Series A)　2021/02　Research paper (scientific journal)

  24. Stochastic Packing Integer Programs with Few Queries

    Takanori Maehara, Yutaro Yamaguchi

    Mathematical Programming (Series A)　Vol. 182　p. 141-174　2020/07　Research paper (scientific journal)

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

    Yasushi Kawase, Yusuke Kobayashi, Yutaro Yamaguchi

    Journal of Combintorial Theory, Series B　Vol. 143　p. 65-122　2020/07　Research paper (scientific journal)

  26. Dynamic Programming Approach to the Generalized Minimum Manhattan Network Problem

    Yuya Masumura, Taihei Oki, Yutaro Yamaguchi

    ISCO 2020　p. 237-248　2020/05　Research paper (international conference proceedings)

  27. A Strongly Polynomial Algorithm for Finding a Shortest Non-zero Path in Group-Labeled Graphs

    Yutaro Yamaguchi

    SODA 2020　p. 1923-1932　2020/01　Research paper (international conference proceedings)

  28. Subgame Perfect Equilibria of Sequential Matching Games

    Yasushi Kawase, Yutaro Yamaguchi, Yu Yokoi

    ACM Transactions on Economics and Computation　Vol. 7　No. 4　2020/01　Research paper (scientific journal)

  29. A Unified Framework for Combinatorial Optimization with Queries

    Takanori Maehara, Yutaro Yamaguchi

    Bulletin of the Japan Society for Industrial and Applied Mathematics　Vol. 29　No. 2　p. 2-9　2019/07　Research paper (conference, symposium, etc.)

  30. Stochastic Monotone Submodular Maximization with Queries

    Takanori Maehara, Yutaro Yamaguchi

    arXiv preprints　2019/07　Research paper (bulletin of university, research institution)

  31. Antimatroids Induced by Matchings

    Yasushi Kawase, Yutaro Yamaguchi

    Discrete Applied Mathematics　Vol. 257　p. 342-349　2019/03　Research paper (scientific journal)

  32. 0/1/all CSPs, Half-Integral $A$-path Packing, and Linear-Time FPT Algorithms

    Yoichi Iwata, Yutaro Yamaguchi, Yuichi Yoshida

    FOCS 2018　p. 462-473　2018/10　Research paper (international conference proceedings)

  33. Computing a Subgame Perfect Equilibrium of a Sequential Matching Game

    Yasushi Kawase, Yutaro Yamaguchi, Yu Yokoi

    EC 2018　p. 131-148　2018/06　Research paper (international conference proceedings)

  34. Making Bipartite Graphs DM-irreducible

    Kristóf Bérczi, Satoru Iwata, Jun Kato, Yutaro Yamaguchi

    SIAM Journal on Discrete Mathematics　Vol. 32　No. 1　p. 560-590　2018/02　Research paper (scientific journal)

  35. Stochastic Packing Integer Programs with Few Queries

    Takanori Maehara, Yutaro Yamaguchi

    SODA 2018　p. 293-310　2018/01　Research paper (international conference proceedings)

  36. On Applications of Weighted Linear Matroid Parity

    Yusuke Kobayashi, Yutaro Yamaguchi

    The 10th Japanese-Hungarian Symposium on Discrete Mathematics and Its Applications　2017/05　Research paper (conference, symposium, etc.)

  37. Shortest Disjoint ${\cal S}$-paths via Weighted Linear Matroid Parity

    Yutaro Yamaguchi

    ISAAC 2016　2016/12　Research paper (international conference proceedings)

  38. Packing Non-zero $A$-paths via Matroid Matching

    Shin-ichi Tanigawa, Yutaro Yamaguchi

    Discrete Applied Mathematics　Vol. 214　No. 11　p. 169-178　2016/12　Research paper (scientific journal)

  39. Piecewise Sparse Linear Classification via Factorized Asymptotic Bayesian Inference

    Ryohei Fujimaki, Yutaro Yamaguchi, Riki Eto

    Transactions of the Japanese Society for Artificial Intelligence　Vol. 31　No. 6　2016/11　Research paper (scientific journal)

  40. Maximizing Time-decaying Influence in Social Networks

    Naoto Ohsaka, Yutaro Yamaguchi, Naonori Kakimura, Ken-ichi Kawarabayashi

    ECML-PKDD 2016　p. 132-147　2016/09　Research paper (international conference proceedings)

  41. Realizing Symmetric Set Functions as Hypergraph Cut Capacity

    Yutaro Yamaguchi

    Discrete Mathematics　Vol. 339　No. 8　p. 2007-2017　2016/08　Research paper (scientific journal)

  42. Packing $A$-paths in Group-Labelled Graphs via Linear Matroid Parity

    Yutaro Yamaguchi

    SIAM Journal on Discrete Mathematics　Vol. 30　No. 1　p. 474-492　2016/03　Research paper (scientific journal)

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

    Yoshinobu Kawahara, Yutaro Yamaguchi

    arXiv preprints　2015/09　Research paper (bulletin of university, research institution)

  44. Cyber Security Analysis of Power Networks by Hypergraph Cut Algorithms

    Yutaro Yamaguchi, Anna Ogawa, Akiko Takeda, Satoru Iwata

    IEEE Transactions on Smart Grid　Vol. 6　No. 5　p. 2189-2199　2015/09　Research paper (scientific journal)

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

    Yasushi Kawase, Yusuke Kobayashi, Yutaro Yamaguchi

    ICALP 2015　p. 797-809　2015/07　Research paper (international conference proceedings)

  46. Cyber Security Analysis of Power Networks by Hypergraph Cut Algorithms

    Yutaro Yamaguchi, Anna Ogawa, Akiko Takeda, Satoru Iwata

    SmartGridComm 2014　p. 830-835　2014/11　Research paper (international conference proceedings)

  47. Packing $A$-paths in Group-Labelled Graphs via Linear Matroid Parity

    Yutaro Yamaguchi

    SODA 2014　p. 562-569　2014/01　Research paper (international conference proceedings)

Presentations 14

  1. マッチング問題に対する高速なアルゴリズム

    山口 勇太郎

    第22回組合せ最適化セミナー (COSS)　2025/07/24

  2. 組合せ最適化におけるマトロイド

    山口 勇太郎

    北海道大学マトロイドセミナー　2024/11/12

  3. Fast Algorithms for Finding a Maximum Matching: Centralized and Distributed

    Yutaro Yamaguchi

    The 6th Workshop on Enumeration Problems and Applications (WEPA 2024)　2024/10/22

  4. 最大マッチング問題に対する高速なアルゴリズム

    山口 勇太郎

    電子情報通信学会 コンピュテーション研究会 (COMP)　2023/12/22

  5. Matroid Intersection under Restricted Oracles

    Kristóf Bérczi, Tamás Király, Yutaro Yamaguchi, Yu Yokoi

    The 12th Japanese-Hungarian Symposium on Discrete Mathematics and Its Applications　2023/03/24

  6. グラフにおける組合せ最適化 ―マッチング・最短経路―

    山口 勇太郎

    第23回情報論的学習理論ワークショップ (IBIS2020)　2020/11/26

  7. 群ラベル付きグラフにおける組合せ最適化

    山口 勇太郎

    第32回RAMP数理最適化シンポジウム　2020/10/26

  8. クエリ可能な確率的組合せ最適化

    山口 勇太郎

    第18回情報科学技術フォーラム (FIT 2019)　2019/09/04

  9. マッチング, パス詰め込みとマトロイド

    山口 勇太郎

    第15回組合せ論若手研究集会　2019/02/22

  10. 配電損失最小化 ―実グラフに潜む性質の活用―

    山口 勇太郎

    第17回情報科学技術フォーラム (FIT 2018)　2018/09/19

  11. クエリ可能な確率的重み付き詰め込み問題

    前原 貴憲, 山口 勇太郎

    電子情報通信学会 コンピュテーション研究会 (COMP)　2018/03/05

  12. クエリ可能な確率的詰め込み問題

    前原 貴憲, 山口 勇太郎

    日本OR学会 「離散アルゴリズムの応用と理論」研究部会 第10回研究会　2018/02/09

  13. マッチングとパス詰め込み

    山口 勇太郎

    日本OR学会 「最適化の基盤とフロンティア」研究部会 (WOO) 第11回研究会　2017/03/14

  14. 代数的マッチングアルゴリズム

    山口 勇太郎

    日本OR学会 関西支部 2016年度 若手研究発表会　2016/10/29

Social Activities 4

  • 情報科学の達人 メンター

    国立情報学研究所　グローバルサイエンスキャンパス (GSC)

    2020/03 - Present

  • International Collegiate Programming Contest (ICPC) Asia Yokohama Regionals 審判長 (Chief Judge)

    2024/04 - 2025/03

  • International Collegiate Programming Contest (ICPC) Asia Yokohama Regionals 審判団 (Judge)

    2021/07 - 2025/03

  • アルゴリズムと計算量 ～情報科学を支える数学の力～

    兵庫「咲いテク」推進委員会　五国 SSH 連携プログラム「数学トレセン兵庫」

    2022/11/13 - 2022/11/13

Academic Activities 8

  1. 日本オペレーションズ・リサーチ学会 2024年度関西支部若手研究発表会 実行委員長

    2024/11/20 - 2024/11/20

  2. The 34th International Symposium on Algorithms and Computation (ISAAC 2023) Local Organizer

    2023/12/03 - 2023/12/06

  3. The 32nd International Symposium on Algorithms and Computation (ISAAC 2021) Local Organizer

    2021/12/06 - 2021/12/08

  4. 日本オペレーションズ・リサーチ学会 2020年春季研究発表会 実行委員

    日本オペレーションズ・リサーチ学会

    2020/03/11 - 2020/03/13

  5. "International Workshop on Combinatorial Optimization and Algorithmic Game Theory" Organizer

    2020/01/13 - 2020/01/14

  6. 日本オペレーションズ・リサーチ学会 関西支部シンポジウム 「ビッグデータ研究とは何か」 実行委員

    日本オペレーションズ・リサーチ学会

    2018/11/17 - 2018/11/17

  7. 第2回 JST 数学領域 未解決問題ワークショップ 運営代表

    2018/09/07 - 2018/09/09

  8. 日本応用数理学会 2018年 研究部会連合発表会 実行委員

    日本応用数理学会

    2018/03/15 - 2018/03/16

Institutional Repository 1

Content Published in the University of Osaka Institutional Repository (OUKA)

  1. Finding spanning trees with perfect matchings

    Bérczi Kristóf, Király Tamás, Kobayashi Yusuke, Yamaguchi Yutaro, Yokoi Yu

    Discrete Applied Mathematics　Vol. 371　p. 137-147　2025/04/11