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:
 A combinatorial formula for principal minors of a matrix with treemetric exponents and its applications, 2013 (with A. Yabe)
[pdf].
 Discrete convexity and polynomial solvability in minimum 0extension problems, METR 201218, 2012.
 On halfintegrality of network synthesis problem,
METR 201215, 2012
(with T. N. Hau and N. Tsuchimura).

Tree metrics and edgedisjoint Spaths,
Mathematical Programming, Series A, to appear, (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, to appear.
[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 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:

T_xapproaches to multiflows and metrics,
In: S. Iwata(ed.),
Combinatorial Optimization and Discrete Algorithms,
RIMS Kokyuroku Bessatsu, B23 (2010), pp 107130.
[pdf]
Talks:

"Discrete convexity and polynomial solvability in minimum 0extension problems",
4th Cargese Workshop on Combinatorial Optimization,
Institut d'Etudes Scientifiques de Cargese, Corsica, France, September 30October 5, 2013.

"Discrete convexity for multiflows and 0extensions",
8th JapaneseHungarian Symposium on
Discrete Mathematics and Its Applications,
Veszprem, Hungary, June 47, 2013.
[slide]

"Discrete convexity and polynomial solvability
in minimum 0extension problems",
Combinatorial Geometries:
matroids, oriented matroids and applications (CG13),
MarseilleLuminy, France, April 26, 2013.
[slide]

"Discrete convexity and polynomial solvability
in minimum 0extension problems",
SODA 2013,
New Orleans, USA, January 68, 2013.

"Discrete convexity and polynomial solvability
in minimum 0extension problems",
Discrete Convexity and Optimization, Kyoto, October 1518, 2012.

"Discrete convexity and polynomial solvability
in minimum 0extension problems",
Discrete Geometric Analysis, Kyoto, August 2731, 2012.

"On Tractability of Minimum 0Extension Problems",
Graph Theory@Georgia Tech, Atlanta, USA, May 711, 2012.

"Weight classication in multiflow problems", Combinatorial Optimization, Oberwolfach, Germany, November 1319, 2011.

"Weighted Multiflows", 7th HungarianJapanese Symposium on Discrete Mathematics and Its Applications, Kyoto, May 31June 3, 2011.

"Tree metrics and edgedisjoint Spaths",
NII Shonan Meeting: Graph Algorithm and Combinatorial Optimization
Shonan Village Center, February 1318, 2011.

"Tree metrics and edgedisjoint Spaths",
Kyoto Prize Satellite Workshop in Tokyo, Tokyo, November 1618, 2010.
[slide]

"The maximum multiflow problems with bounded fractionality", STOC 2010, Cambridge, USA, June 58, 2010.
[slide]

"Bounded Fractionality of Multiflow Feasibility Problem for K3+K3 and Other Maximization Problems",
20th International Symposium on Mathematical Programming
(ISMP 2009), Chicago, USA, August 2328, 2009.
[slide]

"Multiflow feasibility problem for demand graph K3+K3",
6th JapaneseHungarian Symposium on Discrete Mathematics and Its Applications,
Budapest, Hungary, May 1619, 2009.
[slide]

"Tight spans, metric labeling, and multicommodity flows",
Workshop: Discovering Patterns in Biology,
CyeongJu, Korea, March 2122, 2009.
[slide]

"Txapproaches to multiflows and metrics",
Workshop: Combinatorial Optimization and Discrete Algorithms,
Kyoto, June 913, 2008.
[slide]
Some slides:

"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]
Japanese writings
Links (in Japanese)