Hiroshi Hirai
Associate Professor
Department of Mathematical Informatics,
Graduate School of Information Science and Technology,
University of Tokyo, Tokyo, 1138656, Japan.
Email: hirai (at) mist.i.utokyo.ac.jp
TEL: +81358417411
FAX: +81358416923
CV 
teaching 
papers 
slides 
Japanese writings 
list of talks 
links
Research interests: Algorithm, Optimization, Discrete Mathematics (introduction in Japanese)
Editorial work:
SIAM Journal on Applied Algebra and Geometry (SIAGA) (Associate Editor 2021 )
Preprints and Publications:
 On a manifold formulation of selfconcordant functions, 2022 [pdf]
 Finding Hall blockers by matrix scaling, 2022 [pdf] (with K. Hayashi).
 Two flags in a semimodular lattice generate an antimatroid, 2022 [pdf] (with K. Hayashi).
 Convex analysis on Hadamard spaces and scaling problems, 2022 [pdf]
 Computing the ncrank via discrete convex optimization on CAT(0) spaces, SIAM Journal on Applied Algebra and Geometry 5 (2021), 455478. (with M. Hamada).[pdf]
 A costscaling algorithm for computing the degree of determinants, Computational Complexity 31 (2022) Article number: 10 (with M. Ikeda) [pdf]
 Nodeconnectivity terminal backup, separatelycapacitated multiflow, and discrete convexity,
SIAM Journal on Discrete Mathematics, to appear (with M. Ikeda) [pdf]
 Minimum 0extension 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), 137 (with Y. Iwamasa).
[pdf]
 Helly groups, 2020 (with J. Chalopin, V. Chepoi, A. Genevois, and D. Osajda) [pdf]
 A costscaling algorithm for minimumcost nodecapacitated multiflow problem, Mathematical Programming,
Series A 195 (2022),149181 (with M. Ikeda).
[pdf]
 On a weighted linear matroid intersection algorithm by degdet computation,
Japan Journal of Industrial and Applied Mathematics 37 (2020), 677696 (with H. Furue)
[pdf]
 A nonpositive curvature property of modular semilattices, Geometriae Dedicata 214 (2021), 427463. [pdf]
 Reconstructing phylogenetic tree from multipartite quartet system, Algorithmica 84 (2022),18751896 (with Y. Iwamasa)
[pdf]

Counting integral points in polytopes via numerical analysis of contour integration, Mathematics of Operations Research
45 (2020) 455464 (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), 523557.
[pdf]

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

A tractable class of binary VCSPs via Mconvex 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), 375390.
[pdf]

Polyhedral clinching auctions for twosided markets, Mathematics of Operations Research 47 (2022), 259285 (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. 67101.
[pdf]
 On integer network synthesis problem with treemetric cost, JSIAM Letters 9 (2017), 7376. (with M. Nitta)
[pdf]

A compact representation for modular semilattices and its applications,
Order 37 (2020),479507 (with S. Nakashima). [pdf]
 Maximum vanishing subspace problem, CAT(0)space relaxation, and
blocktriangularization of partitioned matrix (with M. Hamada), 2017 [pdf]
 Lconvexity on graph structures, Journal of the Operations Research Society of Japan 61 (2018), 71109.
[pdf]
 A compact representation for minimizers of ksubmodular functions,
Journal of Combinatorial Optimization, 36 (2018) 709  741 (with T. Oki).
[pdf]
 Computing DMdecomposition of a partitioned matrix with rank1 blocks,
Linear Algebra and Its Applications 547 (2018), 105123.
[pdf]
 Shortest (A+B)path packing via hafnian, Algorithmica 80 (2018), 24782491 (with H. Namba). [pdf]
 On uncrossing games for skewsupermodular functions, Journal of the Operations Research Society of Japan 59 (2016), 218223.
[pdf]
 A dual descent algorithm for nodecapacitated multiflow problems and its
applications, ACM Transactions on Algorithms 15 (2018), 15:115:24.
[pdf]
 A representation of antimatroids by Horn rules and its
application to educational systems, Journal of Mathematical Psychology,
77 (2017), 8293 (with H. Yoshikawa and K. Makino).
[pdf]
 On ksubmodular relaxation, SIAM Journal on Discrete Mathematics,
30 (2016), 17261736 (with Y. Iwamasa).
[pdf]
 Lextendable functions and a proximity scaling algorithm for minimum cost multiflow problem, Discrete Optimization, 18 (2015), 137 [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 treemetric exponents and its applications, Journal of Combinatorial Theory, Series A, 133 (2015), 261279 (with A. Yabe).
[pdf]
 Discrete convexity and polynomial solvability in minimum 0extension problems,
Mathematical Programming, Series A, 155 (2016), 155. [pdf]
 On halfintegrality of network synthesis problem,
Journal of the Operations Research Society of Japan,
57 (2014), 6373 (with T. N. Hau and N. Tsuchimura). [pdf]

Tree metrics and edgedisjoint Spaths,
Mathematical Programming, Series A 147 (2014), 81123, (with G. Pap).
[pdf]

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

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

Halfintegrality of nodecapacitated multiflows
and treeshaped facility locations on trees,
Mathematical Programming, Series A 137 (2013),
503530.
[pdf]

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

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

Folder complexes and multiflow combinatorial dualities,
SIAM Journal on Discrete Mathematics 25 (2011), 11191143.
[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), 875899.
[pdf]

Metric packing for K_3 + K_3, Combinatorica 30 (2010), 295326.
[pdf]

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

Electric network classifiers for semisupervised learning on graphs,
Journal of the Operations Research Society of Japan 50 (2007), 219232
(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), 111128.
[pdf]
 A geometric study of the split decomposition,
Discrete and Computational Geometry 36 (2006), 331361.
[pdf]

Greedy fans: A geometric approach to dual greedy algorithms,
RIMS Preprint1508, 2005.

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

Mconvex functions and tree metrics,
Japan Journal of Industrial and Applied Mathematics, 21 (2004), 391401 (with K. Murota).
Proceedings:
 Minimum 0extension problems on directed metrics,
45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020), LIPIcs 170, 2020, 46:146:13.(with R. Mizutani)

Nodeconnectivity terminalbackup, separatelycapacitated multiflow, and discrete convexity,
47th International Colloquium on Automata, Languages, and Programming (ICALP 2020),LIPIcs 168, 2020, 65:165: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, 196208. (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:157:13. (with Y. Iwamasa)

Beyond JWP: A tractable class of binary VCSPs via Mconvex intersection,
Proceedings of the 35th International Symposium on Theoretical Aspects of Computer Science (STACS'18), LIPIcs 96, 2018, 39:139: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. 381392. (with T. Oki)
 Discrete convexity and polynomial solvability
in minimum 0extension problems,
Proceedings of the 24th Annual ACMSIAM Symposium on Discrete Algorithms (SODA'13), 2013. pp.17701788.
 The maximum multiflow problems with bounded fractionality,
Proceedings of the 42nd ACM International Symposium on Theory
of Computing (STOC'10), 2010 pp.115120.
Other publications:

A Linear programming formulation for routing asynchronous power systems of the Digital Grid, The European Physical Journal Special Topics 223, 26112620 (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. 574584 (with M. Hasegawa, K. Nagano,
H. Harada, and K. Aihara).

T_xapproaches to multiflows and metrics,
In: S. Iwata(ed.),
Combinatorial Optimization and Discrete Algorithms,
RIMS Kokyuroku Bessatsu, B23 (2010), pp 107130.
[pdf]
Slides:
 "Discrete Convex Optimization for LeftRight Action (ncrank & det)", December 2021
[slide1]
[slide2]
 "Metric Graph Theory in Combinatorial Optimization", December 2021[slide]
 "Computing the ncrank 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^{n}", 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 blocktriangularization of partitioned matrix", May 2017 [slide]
 "A dual descent algorithm for nodecapacitated multiflow problems and its applicactions", June 2016 [slide]
 "Discrete Convex Analysis beyond Z^{n}", 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]

"Lextendable 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 0extensions", June 2013
[slide]

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

"Tree metrics and edgedisjoint Spaths", November 2010
[slide]

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

"Halfintegrality of nodecapacitated multiflows
and treeshaped facility locations on trees", April, 2010.
[slide]

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

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