Hiroshi Hirai

Curriculum Vitae

Research Interests: Discrete Mathematics, Combinatorial Optimization

• Discrete convexity and polynomial solvability in minimum 0-extension problems, METR 2012-18, 2012.

• On half-integrality of network synthesis problem, METR 2012-15, 2012 (with T. N. Hau and N. Tsuchimura).

• Tree metrics and edge-disjoint S-paths, EGRES Technical Reports, TR-2010-13, 2011 (with G. Pap).

• 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, Jounal of the Operations Research Society of Japan 53 (2010), 149-156. [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), 1119--1143. [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), 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).

• 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.

• 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]

• "Discrete convexity and polynomial solvability in minimum 0-extension problems", Combinatorial Geometries: matroids, oriented matroids and applications (CG13), Marseille-Luminy, France, April 2-6, 2013. [slide]

• "Discrete convexity and polynomial solvability in minimum 0-extension problems", SODA 2013, New Orleans, USA, January 6-8, 2013.

• "Discrete convexity and polynomial solvability in minimum 0-extension problems", Discrete Convexity and Optimization, Kyoto, October 15-18, 2012.

• "Discrete convexity and polynomial solvability in minimum 0-extension problems", Discrete Geometric Analysis, Kyoto, August 27-31, 2012.

• "On Tractability of Minimum 0-Extension Problems", Graph Theory@Georgia Tech, Atlanta, USA, May 7-11, 2012.

• "Weight classication in multiflow problems", Combinatorial Optimization, Oberwolfach, Germany, November 13-19, 2011.

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

• "Tree metrics and edge-disjoint S-paths", NII Shonan Meeting: Graph Algorithm and Combinatorial Optimization Shonan Village Center, February 13-18, 2011.
• "Tree metrics and edge-disjoint S-paths", Kyoto Prize Satellite Workshop in Tokyo, Tokyo, November 16-18, 2010. [slide]

• "The maximum multiflow problems with bounded fractionality", STOC 2010, Cambridge, USA, June 5-8, 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 23-28, 2009. [slide]

• "Multiflow feasibility problem for demand graph K3+K3", 6th Japanese-Hungarian Symposium on Discrete Mathematics and Its Applications, Budapest, Hungary, May 16-19, 2009. [slide]

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

• "Tx-approaches to multiflows and metrics", Workshop: Combinatorial Optimization and Discrete Algorithms, Kyoto, June 9-13, 2008. [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]