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
FAX: +81358417411
Curriculum Vitae
Research Interests: Discrete Mathematics, Combinatorial Optimization
Preprints and Publications:
 Shortest (A+B)path packing via hafnian, 2016 (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, 2015 [pdf]
 A representation of antimatroids by Horn rules and its
application to educational systems, 2015 (with H. Yoshikawa and K. Makino)
[pdf]
 On ksubmodular relaxation, SIAM Journal on Discrete Mathematics, to appear (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, 2014 (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,
Jounal 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:

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]
Japanese writings
Slides:
 "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]
List of talks
Links (in Japanese)