Research activity information

• Sep. 2022 日本オペレーションズ・リサーチ学会, 第12回 研究賞奨励賞

  岩政 勇仁


• Jun. 2022 日本応用数理学会, 第18回 若手優秀講演賞

  岩政 勇仁


• Jun. 2018 日本オペレーションズ・リサーチ学会 研究部会「最適化とその応用—未来を担う若手研究者の集い2018—」, 優秀発表賞

  岩政 勇仁


• Mar. 2016 日本オペレーションズ・リサーチ学会, 学生論文賞

  岩政 勇仁


• Mar. 2016 日本オペレーションズ・リサーチ学会 2016年春季研究発表会, 学生優秀発表賞

  岩政 勇仁


• May 2015 日本オペレーションズ・リサーチ学会 研究部会「最適化の基盤とフロンティア—未来を担う若手研究者の集い2015—」, 最優秀発表賞

  岩政 勇仁


• May 2014 日本オペレーションズ・リサーチ学会 研究部会「最適化の理論と応用—未来を担う若手研究者の集い2014—」, 優秀発表賞

  岩政 勇仁

• Finding a maximum restricted t-matching via Boolean edge-CSP

  Yuni Iwamasa, Yusuke Kobayashi, Kenjiro Takazawa

  Society for Industrial & Applied Mathematics (SIAM), 2026, SIAM Journal on Discrete Mathematics, 40(2) (2), 816 - 835

  [Refereed]

  Scientific journal


• Reconfiguration of time-respecting arborescences

  Takehiro Ito, Yuni Iwamasa, Naoyuki Kamiyama, Yasuaki Kobayashi, Yusuke Kobayashi, Shun-ichi Maezawa, Akira Suzuki

  Springer Science and Business Media LLC, 2026, Algorithmica, 88(1) (1)

  [Refereed]

  Scientific journal


• On the sizes of BDDs and ZDDs representing matroids

  Hiromi Emoto, Yuni Iwamasa, Shin-ichi Minato

  Elsevier BV, 2026, Theoretical Computer Science, 1059, 115591

  [Refereed]

  Scientific journal


• Independent set reconfiguration on directed graphs

  Takehiro Ito, Yuni Iwamasa, Yasuaki Kobayashi, Yu Nakahata, Yota Otachi, Masahiro Takahashi, Kunihiro Wasa

  Society for Industrial & Applied Mathematics (SIAM), 2026, SIAM Journal on Discrete Mathematics, 40(1) (1), 82 - 101

  [Refereed]

  Scientific journal


• A general framework for finding diverse solutions via network flow and its applications

  Yuni Iwamasa, Tomoki Matsuda, Shunya Morihira, Hanna Sumita

  2025, Proceedings of the 36th International Symposium on Algorithms and Computation (ISAAC 2025), LIPIcs 359, 41:1 - 41:15

  [Refereed]


• Homotopy types of Hom complexes of graph homomorphisms whose codomains are cycles

  Soichiro Fujii, Yuni Iwamasa, Kei Kimura, Yuta Nozaki, Akira Suzuki

  Springer Science and Business Media LLC, 2025, Journal of Applied and Computational Topology, 9(3) (3)

  Scientific journal


• Algorithmic aspects of semistability of quiver representations.

  Yuni Iwamasa, Taihei Oki, Tasuku Soma

  2025, Proceedings of the 52nd EATCS International Colloquium on Automata, Languages and Programming (ICALP 2025), LIPIcs 334, 99:1 - 99:18

  [Refereed]

  International conference proceedings


• Reconfiguration of colorings in triangulations of the sphere

  Takehiro Ito, Yuni Iwamasa, Yusuke Kobayashi, Shun-ichi Maezawa, Yuta Nozaki, Yoshio Okamoto, Kenta Ozeki

  2025, Journal of Computational Geometry, 16(1) (1), 253 - 294

  [Refereed]


• Reforming an envy-free matching

  Takehiro Ito, Yuni Iwamasa, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, Yuta Nozaki, Yoshio Okamoto, Kenta Ozeki

  Springer Science and Business Media LLC, 2025, Algorithmica, 87, 594 - 620

  [Refereed]

  Scientific journal


• Rerouting planar curves and disjoint paths

  Takehiro Ito, Yuni Iwamasa, Naonori Kakimura, Yusuke Kobayashi, Shun-Ichi Maezawa, Yuta Nozaki, Yoshio Okamoto, Kenta Ozeki

  Association for Computing Machinery (ACM), 2025, ACM Transactions on Algorithms, 21(2) (2), 20:1 - 20:37

  [Refereed]

  Scientific journal


• Algebraic combinatorial optimization on the degree of determinants of noncommutative symbolic matrices

  Hiroshi Hirai, Yuni Iwamasa, Taihei Oki, Tasuku Soma

  Abstract We address the computation of the degrees of minors of a noncommutative symbolic matrix of form $$ A[c] :=\sum _{k=1}^m A_k t^{c_k} x_k, $$where $$A_k$$ are matrices over a field $$\mathbb {K}$$, $$x_k$$ are noncommutative variables, $$c_k$$ are integer weights, and t is a commuting variable specifying the degree. This problem extends noncommutative Edmonds’ problem (Ivanyos et al. in Comput Complex 26:717–763, 2017), and can formulate various combinatorial optimization problems. Extending the study by Hirai 2018, and Hirai, Ikeda 2022, we provide novel duality theorems and polyhedral characterization for the maximum degrees of minors of A[c] of all sizes, and develop a strongly polynomial-time algorithm for computing them. This algorithm is viewed as a unified algebraization of the classical Hungarian method for bipartite matching and the weight-splitting algorithm for linear matroid intersection. As applications, we provide polynomial-time algorithms for weighted fractional linear matroid matching and for membership of rank-2 Brascamp–Lieb polytopes.

  Springer Science and Business Media LLC, 2025, Mathematical Programming, Series A, 213, 941 - 984

  [Refereed]

  Scientific journal


• Basis sequence reconfiguration in the union of matroids.

  Tesshu Hanaka, Yuni Iwamasa, Yasuaki Kobayashi, Yuto Okada, Rin Saito

  Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024, Proceedings of the 35th International Symposium on Algorithms and Computation (ISAAC 2024), LIPIcs 322, 38:1 - 38:16

  [Refereed]

  International conference proceedings


• Finding a maximum restricted $t$-matching via Boolean edge-CSP

  Yuni Iwamasa, Yusuke Kobayashi, Kenjiro Takazawa

  2024, Proceedings of the 32nd Annual European Symposium on Algorithms (ESA 2024)

  [Refereed]


• Characterizations of the set of integer points in an integral bisubmodular polyhedron

  Yuni Iwamasa

  Elsevier BV, 2024, Discrete Mathematics, 347(4) (4), 113855

  [Refereed]

  Scientific journal


• A combinatorial algorithm for computing the entire sequence of the maximum degree of minors of a generic partitioned polynomial matrix with $$2 \times 2$$ submatrices

  Yuni Iwamasa

  Springer Science and Business Media LLC, 2024, Mathematical Programming, Series A, 204, 27 - 79

  [Refereed]

  Scientific journal


• Rerouting planar curves and disjoint paths

  Takehiro Ito, Yuni Iwamasa, Naonori Kakimura, Yusuke Kobayashi, Shun-ichi Maezawa, Yuta Nozaki, Yoshio Okamoto, Kenta Ozeki

  2023, Proceedings of the 50th EATCS International Colloquium on Automata, Languages and Programming (ICALP 2023), LIPIcs 261, 81:1 - 81:19

  [Refereed]


• Reconfiguration of time-respecting arborescences

  Takehiro Ito, Yuni Iwamasa, Naoyuki Kamiyama, Yasuaki Kobayashi, Yusuke Kobayashi, Shun-ichi Maezawa, Akira Suzuki

  Springer Nature Switzerland, 2023, Proceedings of the 18th Algorithms and Data Structures Symposium (WADS 2023), LNCS 14079, 521 - 532

  [Refereed]

  International conference proceedings


• Reconfiguration of colorings in triangulations of the sphere

  Takehiro Ito, Yuni Iwamasa, Yusuke Kobayashi, Shun-ichi Maezawa, Yuta Nozaki, Yoshio Okamoto, Kenta Ozeki

  2023, Proceedings of the 39th International Symposium on Computational Geometry (SoCG 2023), LIPIcs 258, 43:1 - 43:16

  [Refereed]

  International conference proceedings


• Reconfiguring (non-spanning) arborescences

  Takehiro Ito, Yuni Iwamasa, Yasuaki Kobayashi, Yu Nakahata, Yota Otachi, Kunihiro Wasa

  Elsevier BV, 2023, Theoretical Computer Science, 943, 131 - 141

  [Refereed]

  Scientific journal


• Monotone edge flips to an orientation of maximum edge-connectivity à la Nash-Williams

  Takehiro Ito, Yuni Iwamasa, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, Shun-Ichi Maezawa, Yuta Nozaki, Yoshio Okamoto, Kenta Ozeki

  We initiate the study of k -edge-connected orientations of undirected graphs through edge flips for k ≥ 2. We prove that in every orientation of an undirected 2k -edge-connected graph, there exists a sequence of edges such that flipping their directions one by one does not decrease the edge connectivity, and the final orientation is k -edge connected. This yields an “edge-flip based” new proof of Nash-Williams’ theorem: A undirected graph G has a k -edge-connected orientation if and only if G is 2k -edge connected. As another consequence of the theorem, we prove that the edge-flip graph of k -edge-connected orientations of an undirected graph G is connected if G is (2k+2) -edge connected. This has been known to be true only when k=1 .

  Association for Computing Machinery (ACM), 2023, ACM Transactions on Algorithms, 19(1) (1), 6:1 - 6:22

  [Refereed]

  Scientific journal


• Algorithms for coloring reconfiguration under recolorability digraphs

  Soichiro Fujii, Yuni Iwamasa, Kei Kimura, Akira Suzuki

  2022, Proceedings of the 33rd International Symposium on Algorithms and Computation (ISAAC 2022), LIPIcs 248, 4:1 - 4:19

  [Refereed]

  International conference proceedings


• Independent set reconfiguration on directed graphs

  Takehiro Ito, Yuni Iwamasa, Yasuaki Kobayashi, Yu Nakahata, Yota Otachi, Masahiro Takahashi, Kunihiro Wasa

  2022, Proceedings of the 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022), LIPIcs 241, 58:1 - 58:15

  [Refereed]

  International conference proceedings


• Reconstructing phylogenetic trees from multipartite quartet systems

  Hiroshi Hirai, Yuni Iwamasa

  Springer Science and Business Media LLC, 2022, Algorithmica, 84, 1875 - 1896

  [Refereed]

  Scientific journal


• Reforming an envy-free matching

  Takehiro Ito, Yuni Iwamasa, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, Yuta Nozaki, Yoshio Okamoto, Kenta Ozeki

  2022, Proceedings of the 36th AAAI Conference on Artificial Intelligence (AAAI 2022), 5084 - 5091

  [Refereed]

  International conference proceedings


• Monotone edge flips to an orientation of maximum edge-connectivity à la Nash-Williams

  Takehiro Ito, Yuni Iwamasa, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, Shun-ichi Maezawa, Yuta Nozaki, Yoshio Okamoto, Kenta Ozeki

  2022, Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms (SODA 2022), 1342 - 1355

  [Refereed]

  International conference proceedings


• A combinatorial algorithm for computing the rank of a generic partitioned matrix with $2 \times 2$ submatrices

  Hiroshi Hirai, Yuni Iwamasa

  Springer Science and Business Media LLC, 2022, Mathematical Programming, Series A, 195, 1 - 37

  [Refereed]

  Scientific journal


• Quantaloidal Approach to Constraint Satisfaction

  Soichiro Fujii, Yuni Iwamasa, Kei Kimura

  Open Publishing Association, 2022, Electronic Proceedings in Theoretical Computer Science, 372, 289 - 305

  [Refereed]

  International conference proceedings


• Optimal matroid bases with intersection constraints: valuated matroids, M-convex functions, and their applications

  Yuni Iwamasa, Kenjiro Takazawa

  Springer Science and Business Media LLC, 2022, Mathematical Programming, Series A, 194, 229 - 256

  [Refereed]

  Scientific journal


• Reconfiguring Directed Trees in a Digraph

  Takehiro Ito, Yuni Iwamasa, Yasuaki Kobayashi, Yu Nakahata, Yota Otachi, Kunihiro Wasa

  Springer International Publishing, 2021, Proceedings of the 27th International Computing and Combinatorics Conference (COCOON 2021), LNCS 13025, 343 - 354

  [Refereed]

  In book


• A Combinatorial Algorithm for Computing the Degree of the Determinant of a Generic Partitioned Polynomial Matrix with $2 \times 2$ Submatrices

  Yuni Iwamasa

  Springer International Publishing, 2021, Proceedings of the 22nd Conference on Integer Programming and Combinatorial Optimization (IPCO 2021), LNCS 12707, 119 - 133

  [Refereed]

  International conference proceedings


• Optimal Matroid Bases with Intersection Constraints: Valuated Matroids, M-convex Functions, and Their Applications

  Yuni Iwamasa, Kenjiro Takazawa

  2020, Proceedings of the 16th Annual Conference on Theory and Applications of Models of Computation (TAMC 2020), LNCS 12337, 156 - 167

  [Refereed]

  International conference proceedings


• A Combinatorial Algorithm for Computing the Rank of a Generic Partitioned Matrix with $2 \times 2$ Submatrices

  Hiroshi Hirai, Yuni Iwamasa

  Springer International Publishing, 2020, Proceedings of the 21st Conference on Integer Programming and Combinatorial Optimization (IPCO 2020), LNCS 12125, 196 - 208

  [Refereed]

  International conference proceedings


• A tractable class of binary VCSPs via M-convex intersection

  Hiroshi Hirai, Yuni Iwamasa, Kazuo Murota, Stanislav Živný

  A binary VCSP is a general framework for the minimization problem of a function represented as the sum of unary and binary cost functions. An important line of VCSP research is to investigate what functions can be solved in polynomial time. Cooper and Živný classified the tractability of binary VCSP instances according to the concept of “triangle,” and showed that the only interesting tractable case is the one induced by the joint winner property (JWP). Recently, Iwamasa, Murota, and Živný made a link between VCSP and discrete convex analysis, showing that a function satisfying the JWP can be transformed into a function represented as the sum of two quadratic M-convex functions, which can be minimized in polynomial time via an M-convex intersection algorithm if the value oracle of each M-convex function is given. In this article, we give an algorithmic answer to a natural question: What binary finite-valued CSP instances can be represented as the sum of two quadratic M-convex functions and can be solved in polynomial time via an M-convex intersection algorithm? We solve this problem by devising a polynomial-time algorithm for obtaining a concrete form of the representation in the representable case. Our result presents a larger tractable class of binary finite-valued CSPs, which properly contains the JWP class.

  Association for Computing Machinery (ACM), 2019, ACM Transactions on Algorithms, 15(3) (3), 44:1 - 44:41

  [Refereed]

  Scientific journal


• Reconstructing Phylogenetic Tree From Multipartite Quartet System

  Hiroshi Hirai, Yuni Iwamasa

  A phylogenetic tree is a graphical representation of an evolutionary history in a set of taxa in which the leaves correspond to taxa and the non-leaves correspond to speciations. One of important problems in phylogenetic analysis is to assemble a global phylogenetic tree from smaller pieces of phylogenetic trees, particularly, quartet trees. Quartet Compatibility is to decide whether there is a phylogenetic tree inducing a given collection of quartet trees, and to construct such a phylogenetic tree if it exists. It is known that Quartet Compatibility is NP-hard but there are only a few results known for polynomial-time solvable subclasses. In this paper, we introduce two novel classes of quartet systems, called complete multipartite quartet system and full multipartite quartet system, and present polynomial time algorithms for Quartet Compatibility for these systems. We also see that complete/full multipartite quartet systems naturally arise from a limited situation of block-restricted measurement.

  2018, Proceedings of the 29th International Symposium on Algorithms and Computation (ISAAC 2018), LIPIcs 123, 57:1 - 57:13, English

  [Refereed]

  International conference proceedings


• Beyond JWP: A Tractable Class of Binary VCSPs via M-Convex Intersection

  Hiroshi Hirai, Yuni Iwamasa, Kazuo Murota, Stanislav Živný

  A binary VCSP is a general framework for the minimization problem of a function represented as the sum of unary and binary cost functions.An important line of VCSP research is to investigate what functions can be solved in polynomial time. Cooper-Zivny classified the tractability of binary VCSP instances according to the concept of "triangle," and showed that the only interesting tractable case is the one induced by the joint winner property (JWP). Recently, Iwamasa-Murota-Zivny made a link between VCSP and discrete convex analysis, showing that a function satisfying the JWP can be transformed into a function represented as the sum of two M-convex functions, which can be minimized in polynomial time via an M-convex intersection algorithm if the value oracle of each M-convex function is given. In this paper, we give an algorithmic answer to a natural question: What binary finite-valued CSP instances can be solved in polynomial time via an M-convex intersection algorithm? We solve this problem by devising a polynomial-time algorithm for obtaining a concrete form of the representation in the representable case. Our result presents a larger tractable class of binary finite-valued CSPs, which properly contains the JWP class.

  2018, Proceedings of the 35th International Symposium on Theoretical Aspects of Computer Science (STACS 2018), LIPIcs 96, Article 39 (14 pages), English

  [Refereed]

  International conference proceedings


• Discrete convexity in joint winner property

  Yuni Iwamasa, Kazuo Murota, Stanislav Živný

  2018, Discrete Optimization, 28, 78 - 88, English

  [Refereed]

  Scientific journal


• The quadratic M-convexity testing problem

  Yuni Iwamasa

  2018, Discrete Applied Mathematics, 238, 106 - 114, English

  [Refereed]

  Scientific journal


• On a general framework for network representability in discrete optimization

  Yuni Iwamasa

  2018, Journal of Combinatorial Optimization, 36(3) (3), 678 - 708, English

  [Refereed]

  Scientific journal


• On a General Framework for Network Representability in Discrete Optimization

  Yuni Iwamasa

  2016, Proceedings of the 4th International Symposium on Combinatorial Optimization (ISCO 2016), LNCS 9849, 369 - 380

  [Refereed]

  International conference proceedings


• On $k$-submodular relaxation

  Hiroshi Hirai, Yuni Iwamasa

  2016, SIAM Journal on Discrete Mathematics, 30(3) (3), 1726 - 1736, English

  [Refereed]

  Scientific journal


• Threshold influence model for allocating advertising budgets

  Atsushi Miyauchi, Yuni Iwamasa, Takuro Fukunaga, Naonori Kakimura

  2015, Proceedings of the 32nd International Conference on Machine Learning (ICML 2015), 1395 - 1404

  [Refereed]

  International conference proceedings


• Networks maximizing the consensus time of voter models

  Yuni Iwamasa, Naoki Masuda

  2014, Physical Review E, 90(012816) (012816), English

  [Refereed]

  Scientific journal

• Finding a maximum restricted $t$-matching via Boolean edge-CSP

  Yuni Iwamasa, Yusuke Kobayashi, Kenjiro Takazawa

  The 32nd Annual European Symposium on Algorithms (ESA 2024), Sep. 2024


• 離散凸解析の拡張に向けて

  岩政勇仁

  大阪組合せ論セミナー, Jun. 2024

  [Invited]


• 制限付き$t$-マッチング問題に対する制約充足的アプローチ

  岩政 勇仁, 小林 佑輔, 高澤 兼二郎

  第195回アルゴリズム研究発表会, Nov. 2023


• Reconfiguration of colorings in triangulations of the sphere

  Takehiro Ito, Yuni Iwamasa, Yusuke Kobayashi, Shun-ichi Maezawa, Yuta Nozaki, Yoshio Okamoto, Kenta Ozeki

  The 39th International Symposium on Computational Geometry (SoCG 2023), Jun. 2023


• A combinatorial algorithm for computing the entire sequence of the maximum degree of minors of a generic partitioned polynomial matrix with $2 \times 2$ submatrices

  Yuni Iwamasa

  SIAM Conference on Optimization (OP23), Jun. 2023

  [Invited]


• A combinatorial algorithm for computing the entire sequence of the maximum degree of minors of a generic partitioned polynomial matrix with $2 \times 2$ submatrices

  Yuni Iwamasa

  The 12th Japanese-Hungarian Symposium on Discrete Mathematics and Its Applications (JH 2023), Mar. 2023


• 整数双劣モジュラ多面体の整数点集合の特徴づけ

  岩政 勇仁

  日本応用数理学会 第19回研究部会連合発表会, Mar. 2023


• Algorithms for coloring reconfiguration under recolorability digraphs

  Soichiro Fujii, Yuni Iwamasa, Kei Kimura, Akira Suzuki

  The 33rd International Symposium on Algorithms and Computation (ISAAC 2022), Dec. 2022


• 球面の三角形分割の彩色遷移

  伊藤 健洋, 岩政 勇仁, 小林 佑輔, 前澤 俊一, 野崎 雄太, 岡本 吉央, 小関 健太

  2022年度応用数学合同研究集会, Dec. 2022


• 球面の三角形分割の彩色遷移

  伊藤 健洋, 岩政 勇仁, 小林 佑輔, 前澤 俊一, 野崎 雄太, 岡本 吉央, 小関 健太

  日本オペレーションズ・リサーチ学会 2022年秋季研究発表会, Sep. 2022


• 2部マッチング問題の代数的拡張

  岩政 勇仁

  日本オペレーションズ・リサーチ学会 研究部会「最適化手法とアルゴリズム」, Oct. 2021

  [Invited]


• $2 \times 2$型分割多項式行列の行列式次数を求める組合せ的多項式時間アルゴリズム

  岩政 勇仁

  日本応用数理学会 2021年度年会, Sep. 2021


• A combinatorial algorithm for computing the degree of the determinant of a generic partitioned polynomial matrix with $2 \times 2$ submatrices

  Yuni Iwamasa

  The 22nd Conference on Integer Programming and Combinatorial Optimization (IPCO 2021), May 2021


• 2部マッチング理論の代数的一般化について

  岩政 勇仁

  第32回RAMP数理最適化シンポジウム (RAMP 2020), Oct. 2020

  [Invited]


• Optimal matroid bases with intersection constraints: Valuated matroids, M-convex functions, and their applications

  Yuni Iwamasa, Kenjiro Takazawa

  The 16th Annual Conference on Theory and Applications of Models of Computation (TAMC 2020), Oct. 2020

  Oral presentation


• 交叉制約下でのマトロイドの最適基とその一般化

  岩政 勇仁, 高澤 兼二郎

  京都大学数理解析研究所 共同研究（グループ型） 数理最適化の理論・アルゴリズム・応用, Aug. 2020

  Oral presentation


• A combinatorial algorithm for computing the rank of a generic partitioned matrix with $2 × 2$ submatrices

  Hiroshi Hirai, Yuni Iwamasa

  The 21st Conference on Integer Programming and Combinatorial Optimization (IPCO 2020), Jun. 2020

  Oral presentation


• $2 \times 2$型分割行列のランクを求める組合せ的多項式時間アルゴリズム

  平井 広志, 岩政 勇仁

  日本応用数理学会 第16回研究部会連合発表会, Mar. 2020

  Oral presentation


• $2 \times 2$型分割行列のランクを求める組合せ的多項式時間アルゴリズム

  平井 広志, 岩政 勇仁

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

  [Invited]

  Invited oral presentation


• Reconstructing phylogenetic tree from multipartite quartet system

  Hirai Hiroshi, Yuni Iwamasa

  The 29th International Symposium on Algorithms and Computation (ISAAC 2018), Dec. 2018

  Oral presentation


• 完全多部四点木システムからの系統樹復元

  平井 広志, 岩政 勇仁

  日本応用数理学会 2018年度年会, Sep. 2018

  Oral presentation


• Discrete convexity in binary VCSPs

  Hiroshi Hirai, Yuni Iwamasa, Kazuo Murota, Stanislav Živný

  The 23rd International Symposium on Mathematical Programming (ISMP 2018), Jul. 2018

  Oral presentation


• Beyond JWP: A tractable class of binary VCSPs via M-convex intersection

  Hiroshi Hirai, Yuni Iwamasa, Kazuo Murota, Stanislav Živný

  The 35th International Symposium on Theoretical Aspects of Computer Science (STACS 2018), Mar. 2018

  Oral presentation


• A tractable class of binary VCSPs via M-convex intersection

  Hiroshi Hirai, Yuni Iwamasa, Kazuo Murota, Stanislav Živný

  電子情報通信学会2018年（平成30年）総合大会 COMP-ELC学生シンポジウム, Mar. 2018

  Oral presentation


• 値付き制約充足問題と離散凸性：2次値付き制約充足問題のM凸交叉による多項式時間可解なクラス

  平井 広志, 岩政 勇仁, 室田 一雄, Stanislav Živný

  日本オペレーションズ･リサーチ学会 研究部会「離散アルゴリズムの応用と理論」, Feb. 2018

  [Invited]

  Invited oral presentation


• Discrete convexity in joint winner property

  Yuni Iwamasa, Kazuo Murota, Stanislav Živný

  日本応用数理学会 2017年度年会, Sep. 2017

  Oral presentation


• Discrete convexity in valued constraint satisfaction problems: M-convexity and joint winner property

  岩政 勇仁, 室田 一雄, Stanislav Živný

  Japanese Conference on Combinatorics and its Applications (JCCA 2017)・離散数学とその応用研究集会2017, Aug. 2017

  [Invited]

  Invited oral presentation


• Discrete convexity in joint winner property

  Yuni Iwamasa, Kazuo Murota, Stanislav Živný

  The 19th Conference on Integer Programming and Combinatorial Optimization (IPCO 2017), Jun. 2017

  Poster presentation


• The quadratic M-convexity testing problem

  Yuni Iwamasa

  The 10th Japanese-Hungarian Symposium on Discrete Mathematics and Its Applications (JH 2017), May 2017

  Oral presentation


• 2次関数のM凸性判定問題

  岩政 勇仁

  日本オペレーションズ・リサーチ学会 2017年春季研究発表会（創立60周年記念大会）, Mar. 2017

  Oral presentation


• On a general framework for network representability in discrete optimization

  Yuni Iwamasa

  The 4th International Symposium on Combinatorial Optimization (ISCO 2016), May 2016

  Oral presentation


• M${}^\natural$-convex completion problem

  岩政 勇仁, 室田 一雄

  日本オペレーションズ・リサーチ学会 研究部会「最適化の基盤とフロンティア—未来を担う若手研究者の集い2016—」, May 2016

  Oral presentation


• 関数のネットワーク表現とその拡張について

  岩政 勇仁

  日本オペレーションズ・リサーチ学会 2016年春季研究発表会, Mar. 2016

  Oral presentation


• On $k$-submodular relaxation

  Hiroshi Hirai, Yuni Iwamasa

  The 9th Hungarian-Japanese Symposium on Discrete Mathematics and Its Applications (HJ 2015), Jun. 2015

  Oral presentation


• On $k$-submodular relaxation

  平井 広志, 岩政 勇仁

  日本オペレーションズ・リサーチ学会 研究部会「最適化の基盤とフロンティア—未来を担う若手研究者の集い2015—」, May 2015

  Oral presentation


• 投票者モデルにおける平均合意時間が最大のグラフ

  岩政 勇仁, 増田 直紀

  日本オペレーションズ・リサーチ学会 研究部会「最適化の理論と応用—未来を担う若手研究者の集い2014—」, Jun. 2014

  Oral presentation

• The Japan Society for Industrial and Applied Mathematics


• The Operations Research Society of Japan

• 非正曲率空間上の次世代凸最適化

  平井 広志, 相馬 輔, 岩政 勇仁, 大城 泰平, 谷川 眞一, 早水 桃子

  日本学術振興会, 科学研究費助成事業, 挑戦的研究(開拓), 名古屋大学, Jun. 2024 - Mar. 2030


• 多面体的手法と離散構造を用いた組合せ最適化問題の解法

  小林 佑輔, 高澤 兼二郎, 岩政 勇仁

  日本学術振興会, 科学研究費助成事業, 基盤研究(B), 京都大学, 01 Apr. 2024 - 31 Mar. 2029


• 離散凸解析における双対理論の深化

  岩政 勇仁

  日本学術振興会, 科学研究費助成事業, 若手研究, 京都大学, Apr. 2022 - Mar. 2027


• Development of Combinatorial Reconfiguration by Mathematics Approach: From Examples to New Methods

  岡本 吉央, 神山 直之, 垣村 尚徳, 小関 健太, 小林 佑輔, 野崎 雄太, 岩政 勇仁

  Japan Society for the Promotion of Science, Grants-in-Aid for Scientific Research Grant-in-Aid for Transformative Research Areas (B), Grant-in-Aid for Transformative Research Areas (B), The University of Electro-Communications, Oct. 2020 - Mar. 2023

  「組合せ遷移に対する数学理論」の構築を大目標として，主に次の研究を行った． (1) 部分テーマ「組合せ遷移における数学活用事例の体系的収集」において，アルゴリズムゲーム理論における組合せ遷移問題に対して数学活用を行い，その結果を体系的に収集した．特に，無羨望割当に関わる組合せ遷移問題に対して，計算複雑性の解析，多項式時間アルゴリズムの設計，近似不可能性・固定パラメータ困難性の解析を行った．この成果を人工知能分野のトップ会議であるAAAI 2022で発表した． (2) 部分テーマ「組合せ遷移に資する数理手法の開発」において，グラフ理論に関わる問題を組合せ遷移の視点から調査し，離散構造，特に劣モジュラ性を利用した方法論を開発した．それによって，グラフ理論において古くから知られているNash-Williamsの定理を組合せ遷移の手法によって証明する新しい手法を与えた．この成果を離散アルゴリズム分野のトップ会議であるSODA 2022で発表した． (3) 部分テーマ「組合せ遷移に資する数理手法の開発」において，グラフ理論に関わる問題を組合せ遷移の視点から調査し，トポロジー，特に曲線の理論を利用した方法論を開発した．それによって，トポロジー的な障害とグラフ理論的な障害を分離することが可能になり，平面グラフに対する多項式時間アルゴリズムを設計することに成功した．この成果をarXivにおいてプレプリントとして発表した． また，組合せ遷移に関する国際ワークショップ「Combinatorial Reconfiguration in Discrete and Computational Geometry」「Graph Theory for Combinatorial Reconfiguration」「Polytope Diameter and Related Topics」「Combinatorial Reconfiguration and Fixed-Parameter Tractability」を主催し，組合せ遷移研究の国際展開と普及に努めた．


• 値付き制約充足問題と離散凸解析の融合と深化

  岩政 勇仁

  Japan Society for the Promotion of Science, Grants-in-Aid for Scientific Research Grant-in-Aid for JSPS Fellows, Grant-in-Aid for JSPS Fellows, National Institute of Informatics, 25 Apr. 2019 - 31 Mar. 2022

  ・値付き制約充足問題の重要な特殊クラスである2次VCSPにおいて，離散凸解析の理論を適用することで，新たな多項式時間可解なクラスを導いた研究（平井広志准教授，室田一雄教授，Stanislav Zivny准教授との共同研究）が，論文誌ACM Transaction on Algorithmsに採択された． ・2×2型分割行列というシンボリック行列（＝要素に変数が含まれている行列）のランクを求める組合せ的な多項式時間アルゴリズムを構築した．（平井広志准教授との共同研究）この結果は，査読付き国際会議21st Conference on Integer Programming and Combinatorial Optimization (IPCO 2020)に採択された． ・Lendl, Peis, Timmermansが近年導入した「重み付きマトロイド交叉問題のロバスト版」を，離散凸解析の視点で捉え直し，背後に潜む数理構造を明確にした．さらに．線形関数最適化である重み付きマトロイド交叉から，非線形関数最適化である付値マトロイド交叉への拡張が，多項式時間可解性を損なわないことを明らかにした．（高澤兼二郎准教授との共同研究）この結果は，査読付き国際会議16th Annual Conference on Theory and Applications of Models of Computation (TAMC 2020)に採択された．


• マッチング問題の代数的拡張に対する組合せ的アプローチ

  岩政 勇仁

  日本学術振興会, 科学研究費助成事業 研究活動スタート支援, 研究活動スタート支援, 京都大学, Sep. 2020 - Mar. 2022

  ・2×2型分割行列のランクを求める組合せ的多項式時間アルゴリズムを設計した研究（平井広志准教授との共同研究）が論文誌Mathematical Programmingに採択された. ・2×2型分割多項式行列の小行列式最大次数列を求める組合せ的強多項式時間アルゴリズムを設計した.さらにサイズkの小行列式最大次数とベクトル空間上に定義されるポテンシャル関数の間の最大最小定理の存在を示した.これは最大重み2部マッチング問題に対する古典的な多項式時間アルゴリズム（ハンガリアン法）や最大最小定理（Egervaryの定理）の代数的拡張であり，昨年度の成果「2×2型分割多項式行列の行列式次数を求める組合せ的強多項式時間アルゴリズムの構築」をさらに進展させたものである．この結果をまとめた論文"A combinatorial algorithm for computing the entire sequence of the maximum degree of minors of a generic partitioned polynomial matrix with $2 \times 2$ submatrices"を査読付き論文誌に投稿中である． ・系統樹復元問題にマトロイド交叉の理論を応用した論文（平井広志准教授との共同研究）"Reconstructing phylogenetic trees from multipartite quartet systems"が論文誌Algorithmicaに採択された． ・招待講演を一件，国内学会での講演を一件行い，多数の有用なフィードバックを得た.


• Exploring novel discrete convexity in discrete optimization and designing high performance algorithms based on it

  Hirai Hiroshi

  Japan Society for the Promotion of Science, Grants-in-Aid for Scientific Research, Grant-in-Aid for Scientific Research (C), The University of Tokyo, Apr. 2017 - Mar. 2021

  In this research project, we explored new types of discrete convexity, which will be useful for discrete optimization, and designed algorithms based on it. We introduced the problem of computing the Dieudonne determinant of a matrix having noncommutative variables, and showed that it generalizes fundamental combinatorial optimization problems and can be efficiently solved by discrete convex optimization on a Euclidean building. We introduced a new class of lattices, called uniform semimodular lattices, and showed that it is equivalent to valuated matroids, which is an important class of discrete convex functions. We studied systematically a class of graphs, called weakly modular graphs, which is expected as ground structures of discrete convex functions, and clarified its relationships to nonpositively curved spaces.


• 関数のグラフ表現性に関する研究

  岩政 勇仁

  Japan Society for the Promotion of Science, Grants-in-Aid for Scientific Research Grant-in-Aid for JSPS Fellows, Grant-in-Aid for JSPS Fellows, The University of Tokyo, 22 Apr. 2016 - 31 Mar. 2019

  系統樹構築問題とは，与えられた四点木（=葉の数が4の系統樹）の集合に対して，その全てに整合する系統樹を構築する問題である．これは，計算生物学の分野だけでなく，理論計算機科学の分野でも盛んに研究されている問題である．系統樹構築問題は一般的にはNP困難であり，高速なヒューリスティクスアルゴリズム，近似アルゴリズム，FPTアルゴリズムの研究が数多く存在する．一方，「どの四点木システム（＝四点木の集合）に対しては系統樹構築問題が多項式時間で解けるか」という自然な疑問に対しては，ほとんど研究がなされていなかった． 本研究の成果として，実社会で現れうる四点木システムを二つ（complete multipartite quartet system, full multipartite quartet system）導入し，それらに対して系統樹構築問題が多項式時間で解けることを示した．これは，新しい多項式時間可解なクラスを明らかにした重要な研究であると言える．この結果は，12月に行われた査読付き国際会議 International Symposium on Algorithms and Computation (ISAAC'18)に採択され，発表を行った． 本研究で提案したアルゴリズムは，前年度の成果である「2次M2凸表現可能性判定問題」に対する多項式時間アルゴリズムの亜種であるとみなせる．つまりこれは，関数のグラフ表現性に関する今までの研究を，計算生物学に応用して得られた成果である．

• The 34th International Symposium on Algorithms and Computation (ISAAC 2023), Local Organizer

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

  03 Dec. 2023 - 06 Dec. 2023

  Academic society etc