Hiroshi Hirai

CV/research map --- teaching --- papers --- slides --- Japanese writings --- list of talks --- links

Research interests: Algorithm, Optimization, Discrete Mathematics (introduction in Japanese)

• Interior-point methods on manifolds: theory and applications, 2023 (with H. Nieuwboer and M. Walter). [pdf]

• Polyhedral clinching auctions for indivisible goods, 2023 (with R. Sato). [pdf]

• On a manifold formulation of self-concordant functions, 2022 [pdf]

• Finding Hall blockers by matrix scaling, Mathematics of Operations Research, to appear (with K. Hayashi and K. Sakabe). [pdf]

• Two flags in a semimodular lattice generate an antimatroid, Order, to appear, (with K. Hayashi). [pdf]

• Convex analysis on Hadamard spaces and scaling problems, Foundations of Computational Mathematics, to appear [pdf]

• Computing the nc-rank via discrete convex optimization on CAT(0) spaces, SIAM Journal on Applied Algebra and Geometry 5 (2021), 455--478 (with M. Hamada).[pdf]

• A cost-scaling algorithm for computing the degree of determinants, Computational Complexity 31 (2022) Article number: 10 (with M. Ikeda) [pdf]

• Node-connectivity terminal backup, separately-capacitated multiflow, and discrete convexity, SIAM Journal on Discrete Mathematics37 (2023),351--378 (with M. Ikeda). [pdf]

• Minimum 0-extension problems on directed metrics, Discrete Optimization 40 (2021), 100642 (with R. Mizutani) [pdf]

• Compression of M$^\natural$-convex Functions -- Flag Matroids and Valuated Permutohedra, Journal of Combinatorial Theory, Series A 185 (2022), 105525 (with S. Fujishige) [pdf]

• A combinatorial algorithm for computing the rank of a generic partitioned matrix with 2x2 submatrices, Mathematical Programming, Series A 195 (2022), 1--37 (with Y. Iwamasa). [pdf]

• Helly groups, Geometry & Topology, to appear (with J. Chalopin, V. Chepoi, A. Genevois, and D. Osajda) [pdf]

• A cost-scaling algorithm for minimum-cost node-capacitated multiflow problem, Mathematical Programming, Series A 195 (2022),149--181 (with M. Ikeda). [pdf]

• On a weighted linear matroid intersection algorithm by deg-det computation, Japan Journal of Industrial and Applied Mathematics 37 (2020), 677--696 (with H. Furue) [pdf]

• A nonpositive curvature property of modular semilattices, Geometriae Dedicata 214 (2021), 427--463. [pdf]

• Reconstructing phylogenetic tree from multipartite quartet system, Algorithmica 84 (2022),1875--1896 (with Y. Iwamasa) [pdf]

• Counting integral points in polytopes via numerical analysis of contour integration, Mathematics of Operations Research 45 (2020) 455--464 (with R. Oshiro and K. Tanaka) [pdf]

• Computing the degree of determinants via discrete convex optimization on Euclidean buildings, SIAM Journal on Applied Algebra and Geometry 3 (2019), 523--557. [pdf]

• Uniform semimodular lattices and valuated matroids, Journal of Combinatorial Theory, Series A 165 (2019), 325-359. [pdf]

• A tractable class of binary VCSPs via M-convex intersection, ACM Transactions on Algorithms 15 (2019), Article 44.(with Y. Iwamasa, K. Murota, and S. Zivny) [pdf]

• Uniform modular lattices and affine buildings, Advances in Geometry 20 (2020), 375--390. [pdf]

• Polyhedral clinching auctions for two-sided markets, Mathematics of Operations Research 47 (2022), 259--285 (with R. Sato). [pdf]

• Discrete Convex Functions on Graphs and Their Algorithmic Applications, In: T. Fukunaga and K. Kawarabayashi (eds.) Combinatorial Optimization and Graph Algorithms, Communications of NII Shonan Meetings, Springer Nature, Singapore, (2017), pp. 67--101. [pdf]

• On integer network synthesis problem with tree-metric cost, JSIAM Letters 9 (2017), 73--76. (with M. Nitta) [pdf]

• A compact representation for modular semilattices and its applications, Order 37 (2020),479--507 (with S. Nakashima). [pdf]

• Maximum vanishing subspace problem, CAT(0)-space relaxation, and block-triangularization of partitioned matrix (with M. Hamada), 2017 [pdf]

• L-convexity on graph structures, Journal of the Operations Research Society of Japan 61 (2018), 71--109. [pdf]

• A compact representation for minimizers of k-submodular functions, Journal of Combinatorial Optimization, 36 (2018) 709 -- 741 (with T. Oki). [pdf]

• Computing DM-decomposition of a partitioned matrix with rank-1 blocks, Linear Algebra and Its Applications 547 (2018), 105--123. [pdf]

• Shortest (A+B)-path packing via hafnian, Algorithmica 80 (2018), 2478-2491 (with H. Namba). [pdf]

• On uncrossing games for skew-supermodular functions, Journal of the Operations Research Society of Japan 59 (2016), 218--223. [pdf]

• A dual descent algorithm for node-capacitated multiflow problems and its applications, ACM Transactions on Algorithms 15 (2018), 15:1--15:24. [pdf]

• A representation of antimatroids by Horn rules and its application to educational systems, Journal of Mathematical Psychology, 77 (2017), 82--93 (with H. Yoshikawa and K. Makino). [pdf]

• On k-submodular relaxation, SIAM Journal on Discrete Mathematics, 30 (2016), 1726--1736 (with Y. Iwamasa). [pdf]

• L-extendable functions and a proximity scaling algorithm for minimum cost multiflow problem, Discrete Optimization, 18 (2015), 1-37 [pdf]

• Weakly modular graphs and nonpositive curvature, Memoirs of the AMS, 268, no.1309, (2020), (with J. Chalopin, V. Chepoi, and D. Osajda). [pdf]

• A combinatorial formula for principal minors of a matrix with tree-metric exponents and its applications, Journal of Combinatorial Theory, Series A, 133 (2015), 261-279 (with A. Yabe). [pdf]

• Discrete convexity and polynomial solvability in minimum 0-extension problems, Mathematical Programming, Series A, 155 (2016), 1-55. [pdf]

• On half-integrality of network synthesis problem, Journal of the Operations Research Society of Japan, 57 (2014), 63-73 (with T. N. Hau and N. Tsuchimura). [pdf]

• Tree metrics and edge-disjoint S-paths, Mathematical Programming, Series A 147 (2014), 81-123, (with G. Pap). [pdf]

• On duality and fractionality of multicommodity flows in directed networks, Discrete Optimization 8 (2011), 428-445 (with S. Koichi). [pdf]

• On tight spans for directed distances, Annals of Combinatorics 16 (2012), 543-569 (with S. Koichi). [pdf]

• Half-integrality of node-capacitated multiflows and tree-shaped facility locations on trees, Mathematical Programming, Series A 137 (2013), 503-530. [pdf]

• A note on multiflow locking theorem, Journal of the Operations Research Society of Japan 53 (2010), 149-156. [pdf]

• The maximum multiflow problems with bounded fractionality, Mathematics of Operations Research 39 (2014), 60-104. [pdf]

• Folder complexes and multiflow combinatorial dualities, SIAM Journal on Discrete Mathematics 25 (2011), 1119-1143. [pdf]

• Bounded fractionality of the multiflow feasibility problem for demand graph K_3 + K_3 and related maximization problems, Journal of Combinatorial Theory, Series B, 102 (2012), 875-899. [pdf]

• Metric packing for K_3 + K_3, Combinatorica 30 (2010), 295-326. [pdf]

• Tight spans of distances and the dual fractionality of undirected multiflow problems, Journal of Combinatorial Theory, Series B 99 (2009), 843-868. [pdf]

• Electric network classifiers for semi-supervised learning on graphs, Journal of the Operations Research Society of Japan 50 (2007), 219-232 (with K. Murota and M. Rikitoku).

• Characterization of the distance between subtrees of a tree by the associated tight span, Annals of Combinatorics 10 (2006), 111-128. [pdf]

• A geometric study of the split decomposition, Discrete and Computational Geometry 36 (2006), 331-361. [pdf]

• Greedy fans: A geometric approach to dual greedy algorithms, RIMS Preprint-1508, 2005.

• SVM kernel by electric network, Pacific Journal of Optimization. 1 (2005), 509-526 (with K. Murota and M. Rikitoku).

• M-convex functions and tree metrics, Japan Journal of Industrial and Applied Mathematics, 21 (2004), 391-401 (with K. Murota).

• Minimum 0-extension problems on directed metrics, 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020), LIPIcs 170, 2020, 46:1--46:13.(with R. Mizutani)

• Node-connectivity terminal-backup, separately-capacitated multiflow, and discrete convexity, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020),LIPIcs 168, 2020, 65:1--65:19. (with M. Ikeda)

• A combinatorial algorithm for computing the rank of a generic partitioned matrix with 2 x 2 submatrices, Integer Programming and Combinatorial Optimization - 21st International Conference (IPCO 2020) LNCS 12125, 2020, 196--208. (with Y. Iwamasa)

• Reconstructing phylogenetic tree from multipartite quartet system, Proceedings of the 29th International Symposium on Algorithms and Computation (ISAAC'18), LIPIcs 123, 2018, 57:1--57:13. (with Y. Iwamasa)

• Beyond JWP: A tractable class of binary VCSPs via M-convex intersection, Proceedings of the 35th International Symposium on Theoretical Aspects of Computer Science (STACS'18), LIPIcs 96, 2018, 39:1--39:14. (with Y. Iwamasa, K. Murota, and S. Živný)

• A compact representation for minimizers of $k$-submodular functions, Proceedings of 4th International Symposium on Combinatorial Optimization (ISCO'16), LNCS 9849, 2016, pp. 381--392. (with T. Oki)

• Discrete convexity and polynomial solvability in minimum 0-extension problems, Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'13), 2013. pp.1770-1788.

• The maximum multiflow problems with bounded fractionality, Proceedings of the 42nd ACM International Symposium on Theory of Computing (STOC'10), 2010 pp.115-120.

• A Linear programming formulation for routing asynchronous power systems of the Digital Grid, The European Physical Journal Special Topics 223, 2611-2620 (2014), (with Kyohei Shibano, Reo Kontani, Mikio Hasegawa, Kazuyuki Aihara, Hisao Taoka, David McQuilkin, and Rikiya Abe).

• Optimization for centralized and decentralized cognitive radio networks, Proceedings of the IEEE 102 (2014), pp. 574--584 (with M. Hasegawa, K. Nagano, H. Harada, and K. Aihara).

• T_x-approaches to multiflows and metrics, In: S. Iwata(ed.), Combinatorial Optimization and Discrete Algorithms, RIMS Kokyuroku Bessatsu, B23 (2010), pp 107-130. [pdf]

• "Finding Hall blockers by matrix scaling", August, 2023 [slide]

• "Algebraic combinatorial optimization for noncommutative rank & determinant", March 2023 [slide]

• "Discrete Convex Optimization for Left-Right Action (nc-rank & det)", December 2021 [slide1] [slide2]

• "Metric Graph Theory in Combinatorial Optimization", December 2021[slide]

• "Computing the nc-rank via discrete convex optimization on CAT(0) spaces", August 2021[slide]

• "Algorithmic and combinatorial aspects on CAT(0) complexes", November 2019 [slide]

• "Euclidean buildings in combinatorial optimization", November 2019 [slide]

• "A nonpositive curvature property of modular semilattices", May 2019 [slide]

• "Discrete Convex Analysis beyond Zⁿ", November 2018 [slide]

• "Computing degree of determinant via discrete convex optimization on Euclidean building", October 2018 [slide]

• "Uniform semimodular lattice, valuated matroid, and Euclidean building", September 2018 [slide]

• "Maximum vanishing subspace problem, CAT(0)-space relaxation, and block-triangularization of partitioned matrix", May 2017 [slide]

• "A dual descent algorithm for node-capacitated multiflow problems and its applicactions", June 2016 [slide]

• "Discrete Convex Analysis beyond Zⁿ", May 2016 [slide]

• "Combinatorial algorithms for some multiflow problems and related network designs", September 2015 [slide]

• "Some combinatorial optimization problems related to metric spaces of nonpositive curvature", September 2015 [slide]

• "L-extendable functions and a proximity scaling algorithm for minimum cost multiflow problem", March 2015 [slide]

• "Weakly modular graphs and nonpositive curvature", November 2014 [slide]

• "Discrete convexity for multiflows and 0-extensions", June 2013 [slide]

• "Discrete convexity and polynomial solvability in minimum 0-extension problems", April 2013 [slide]

• "Tree metrics and edge-disjoint S-paths", November 2010 [slide]

• "Multiflow Theory in Combinatorial Optimization", July, 2010. [slide]

• "Half-integrality of node-capacitated multiflows and tree-shaped facility locations on trees", April, 2010. [slide]

• "Multiflows and metrics", February, 2009. [slide]

• "Metric packing for K3 + K3", September, 2008. [slide]