Updated on 2024/05/01

写真a

 
HIRAI Hiroshi
 
Organization
Graduate School of Mathematics Division of Mathematics Computational Mathematics Professor
Graduate School
Graduate School of Mathematics
Undergraduate School
School of Science Department of Mathematics
Title
Professor

Degree 1

  1. 博士(理学) ( 2009.7   京都大学 ) 

Research Interests 3

  1. optimization

  2. algorithm

  3. 離散数学

Research Areas 3

  1. Informatics / Mathematical informatics

  2. Natural Science / Basic mathematics

  3. Natural Science / Applied mathematics and statistics

Research History 4

  1. Nagoya University   Graduate School of Mathematics   Professor

    2023.5

  2. The University of Tokyo   The Graduate School of Information Science and Technology, Department of Mathematical Informatics   Associate professor

    2014.4 - 2023.5

  3. The University of Tokyo   The Graduate School of Information Science and Technology, Department of Mathematical Informatics   Lecturer

    2010.11 - 2014.3

  4. Kyoto University   Research Institute for Mathematical Sciences   Assistant Professor

    2004.4 - 2010.10

Education 1

  1. The University of Tokyo

    2002.4 - 2004.3

      More details

    Country: Japan

Professional Memberships 2

  1. THE JAPAN SOCIETY FOR INDUSTRIAL AND APPLIED MATHEMATICS

  2. 日本オペレーションズリサーチ学会

Committee Memberships 2

  1. SIAM Journal on Applied Algebra and Geometry (SIAGA)   Associate Editor  

    2021.1   

      More details

    Committee type:Academic society

  2. 日本応用数理学会   離散システム研究部会 主査  

    2019.4   

Awards 7

  1. 日本オペレーションズ・リサーチ学会フェロー

    2019.3  

  2. 日本オペレーションズ・リサーチ学会60周年記念論文賞

    2018.9  

  3. 文部科学大臣表彰 若手科学者賞

    2018.4  

  4. 人工知能学会研究会優秀賞

    2015.6  

  5. 日本オペレーションズ・リサーチ学会研究賞

    2014.8  

  6. 日本オペレーションズ・リサーチ学会文献賞奨励賞

    2009.3  

  7. 日本オペレーションズ・リサーチ学会学生論文賞

    2004.9  

▼display all

 

Papers 60

  1. Polyhedral Clinching Auctions for Indivisible Goods. Reviewed

    Hiroshi Hirai, Ryosuke Sato

    Web and Internet Economics. WINE 2023. Lecture Notes in Computer Science     page: 366 - 383   2023.12

     More details

    Language:English   Publishing type:Research paper (international conference proceedings)  

    DOI: 10.1007/978-3-031-48974-7_21

    Other Link: https://dblp.uni-trier.de/db/conf/wine/wine2023.html#HiraiS23

  2. From Matrix Scaling to Geodesically-Convex Optimzation on Nonpositively Curved Spaces Invited

    Proceeding of the Thirty-Fourth RAMP Mathematical Optimization Symposium     page: 59 - 79   2023.11

     More details

    Authorship:Lead author, Last author, Corresponding author   Language:Japanese   Publishing type:Research paper (conference, symposium, etc.)  

  3. Interior-point methods on manifolds: theory and applications. Reviewed International coauthorship

    Hiroshi Hirai, Harold Nieuwboer, Michael Walter

    2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS)     page: 2021 - 2030   2023.11

     More details

    Language:English   Publishing type:Research paper (international conference proceedings)  

    DOI: 10.1109/FOCS57990.2023.00123

    Other Link: https://dblp.uni-trier.de/db/conf/focs/focs2023.html#0001N023

  4. Finding Hall Blockers by Matrix Scaling Reviewed

    Koyo Hayashi, Hiroshi Hirai, Keiya Sakabe

    Mathematics of Operations Research     2023.10

     More details

    Authorship:Lead author, Last author, Corresponding author   Language:English   Publishing type:Research paper (scientific journal)  

    DOI: 10.1287/moor.2022.0198

  5. Convex Analysis on Hadamard Spaces and Scaling Problems Reviewed

    Hiroshi Hirai

    Foundations of Computational Mathematics     2023.10

     More details

    Authorship:Lead author, Last author, Corresponding author   Language:English   Publishing type:Research paper (scientific journal)  

    In this paper, we address the bounded/unbounded determination of geodesically convex optimization on Hadamard spaces. In Euclidean convex optimization, the recession function is a basic tool to study the unboundedness and provides the domain of the Legendre–Fenchel conjugate of the objective function. In a Hadamard space, the asymptotic slope function (Kapovich et al. in J Differ Geom 81:297–354, 2009), which is a function on the boundary at infinity, plays a role of the recession function. We extend this notion by means of convex analysis and optimization and develop a convex analysis foundation for the unbounded determination of geodesically convex optimization on Hadamard spaces, particularly on symmetric spaces of nonpositive curvature. We explain how our developed theory is applied to operator scaling and related optimization on group orbits, which are our motivation.

    DOI: 10.1007/s10208-023-09628-5

    Scopus

  6. Two Flags in a Semimodular Lattice Generate an Antimatroid Reviewed

    Koyo Hayashi, Hiroshi Hirai

    Order     2023.6

     More details

    Authorship:Lead author, Last author, Corresponding author   Language:English   Publishing type:Research paper (scientific journal)  

    A basic property in a modular lattice is that any two flags generate a distributive sublattice. It is shown (Abels 1991, Herscovici 1998) that two flags in a semimodular lattice no longer generate such a good sublattice, whereas shortest galleries connecting them form a relatively good join-sublattice. In this note, we sharpen this investigation to establish an analogue of the two-flag generation theorem for a semimodular lattice. We consider the notion of a modular convex subset, which is a subset closed under the join and meet only for modular pairs, and show that the modular convex hull of two flags in a semimodular lattice of rank n is isomorphic to a union-closed family on [n]. This family uniquely determines an antimatroid, which coincides with the join-sublattice of shortest galleries of the two flags.

    DOI: 10.1007/s11083-023-09639-5

    Web of Science

    Scopus

  7. Node-Connectivity Terminal Backup, Separately Capacitated Multiflow, and Discrete Convexity. Reviewed

    Hiroshi Hirai, Motoki Ikeda

    SIAM Journal on Discrete Mathematics   Vol. 37 ( 1 ) page: 351 - 378   2023.3

     More details

    Publishing type:Research paper (scientific journal)  

    The terminal backup problems ([E. Anshelevich and A. Karagiozova, SIAM J. Comput., 40 (2011), pp. 678-708]) form a class of network design problems: Given an undirected graph with a requirement on terminals, the goal is to find a minimum-cost subgraph satisfying the connectivity requirement. The node-connectivity terminal backup problem requires a terminal to connect other terminals with a number of node-disjoint paths. This problem is not known whether is NP-hard or tractable. Fukunaga [SIAM J. Discrete Math., 30 (2016), pp. 777-800] gave a 4/3-approximation algorithm based on an LP-rounding scheme using a general LP-solver. In this paper, we develop a combinatorial algorithm for the relaxed LP to find a half-integral optimal solution in O(mlog(nUA) · MF(kn,m + k2n)) time, where n is the number of nodes, m is the number of edges, k is the number of terminals, A is the maximum edge-cost, U is the maximum edge-capacity, and MF(n' ,m') is the time complexity of a max-flow algorithm in a network with n' nodes and m' edges. The algorithm implies that the 4/3-approximation algorithm for the node-connectivity terminal backup problem is also efficiently implemented. For the design of algorithm, we explore a connection between the node-connectivity terminal backup problem and a new type of a multiflow, which is called a separately capacitated multiflow. We show a min-max theorem which extends the Lovász-Cherkassky theorem to the node-capacity setting. Our results build on discrete convexity in the node-connectivity terminal backup problem.

    DOI: 10.1137/20m1361857

    Scopus

  8. A cost-scaling algorithm for computing the degree of determinants Reviewed

    Hiroshi Hirai, Motoki Ikeda

    Computational Complexity   Vol. 31 ( 2 )   2022.12

     More details

    Publishing type:Research paper (scientific journal)  

    In this paper, we address computation of the degree deg Det A of Dieudonné determinant Det A ofA=∑k=1mAkxktck, where Ak are n× n matrices over a field K, xk are noncommutative variables,t is a variable commuting with xk, ck are integers,and the degree is considered for t.This problem generalizes noncommutative Edmonds' problem andfundamental combinatorial optimization problemsincluding the weighted linear matroid intersection problem.It was shown that deg Det A is obtained bya discrete convex optimization on a Euclidean building (Hirai 2019).We extend this framework by incorporating a cost-scaling techniqueand show that deg Det Acan be computed in time polynomial of n, m, log 2C, where C: = max k| ck|.We give a polyhedral interpretation of deg Det ,which says that deg Det A is given by linear optimizationover an integral polytope with respect to objective vector c= (ck).Based on it, we show that our algorithm becomes a strongly polynomial one.We also apply our result to an algebraic combinatorial optimization problemarising from a symbolic matrix having 2 × 2 -submatrix structure.

    DOI: 10.1007/s00037-022-00227-4

    Scopus

  9. A combinatorial algorithm for computing the rank of a generic partitioned matrix with 2 × 2 submatrices Reviewed

    Hiroshi Hirai, Yuni Iwamasa

    Mathematical Programming   Vol. 195 ( 1-2 ) page: 1 - 37   2022.9

     More details

    Publishing type:Research paper (scientific journal)  

    In this paper, we consider the problem of computing the rank of a block-structured symbolic matrix (a generic partitioned matrix) A= (Aαβxαβ) , where Aαβ is a 2 × 2 matrix over a field F and xαβ is an indeterminate for α= 1 , 2 , ⋯ , μ and β= 1 , 2 , ⋯ , ν. This problem can be viewed as an algebraic generalization of the bipartite matching problem and was considered by Iwata and Murota (SIAM J Matrix Anal Appl 16(3):719–734, 1995). Recent interests in this problem lie in the connection with non-commutative Edmonds’ problem by Ivanyos et al. (Comput Complex 27:561–593, 2018) and Garg et al. (Found. Comput. Math. 20:223–290, 2020), where a result by Iwata and Murota implicitly states that the rank and non-commutative rank (nc-rank) are the same for this class of symbolic matrices. The main result of this paper is a simple and combinatorial O((μν) 2min { μ, ν}) -time algorithm for computing the symbolic rank of a (2 × 2) -type generic partitioned matrix of size 2 μ× 2 ν. Our algorithm is inspired by the Wong sequence algorithm by Ivanyos et al. for the nc-rank of a general symbolic matrix, and requires no blow-up operation, no field extension, and no additional care for bounding the bit-size. Moreover it naturally provides a maximum rank completion of A for an arbitrary field F.

    DOI: 10.1007/s10107-021-01676-5

    Scopus

  10. A cost-scaling algorithm for minimum-cost node-capacitated multiflow problem Reviewed

    Hiroshi Hirai, Motoki Ikeda

    Mathematical Programming   Vol. 195 ( 1-2 ) page: 149 - 181   2022.9

     More details

    Publishing type:Research paper (scientific journal)  

    In this paper, we address the minimum-cost node-capacitated multiflow problem in undirected networks. For this problem, Babenko and Karzanov (JCO 24: 202–228, 2012) showed strong polynomial-time solvability via the ellipsoid method. Our result is the first combinatorial polynomial-time algorithm for this problem. Our algorithm finds a half-integral minimum-cost maximum multiflow in O(mlog (nCD) SF (kn, m, k)) time, where n is the number of nodes, m is the number of edges, k is the number of terminals, C is the maximum node capacity, D is the maximum edge cost, and SF (n′, m′, η) is the time complexity of solving the submodular flow problem in a network of n′ nodes, m′ edges, and a submodular function with η-time-computable exchange capacity. Our algorithm is built on discrete convex analysis on graph structures and the concept of reducible bisubmodular flows.

    DOI: 10.1007/s10107-021-01683-6

    Scopus

  11. Reconstructing Phylogenetic Trees from Multipartite Quartet Systems Reviewed

    Hiroshi Hirai, Yuni Iwamasa

    Algorithmica   Vol. 84 ( 7 ) page: 1875 - 1896   2022.7

     More details

    Publishing type:Research paper (scientific journal)  

    A phylogenetic tree is a graphical representation of an evolutionary history of taxa in which the leaves correspond to the taxa and the non-leaves correspond to speciations. One of important problems in phylogenetic analysis is to assemble a global phylogenetic tree from small phylogenetic trees, particularly, quartet trees. Quartet Compatibility is the problem of deciding whether there is a phylogenetic tree inducing a given collection of quartet trees, and to construct such a phylogenetic tree if it exists. It is known that Quartet Compatibility is NP-hard and that there are only a few results known for polynomial-time solvable subclasses. In this paper, we introduce two novel classes of quartet systems, called complete multipartite quartet system and full multipartite quartet system, and present polynomial-time algorithms for Quartet Compatibility for these systems.

    DOI: 10.1007/s00453-022-00945-9

    Scopus

  12. Polyhedral Clinching Auctions for Two-Sided Markets Reviewed

    Hiroshi Hirai, Ryosuke Sato

    Mathematics of Operations Research   Vol. 47 ( 1 ) page: 259 - 285   2022.2

     More details

    Publishing type:Research paper (scientific journal)  

    In this paper, we present a new model and mechanisms for auctions in twosided markets of buyers and sellers, where budget constraints are imposed on buyers. Our model incorporates polymatroidal environments and is applicable to a variety of models that include multiunit auctions, matching markets, and reservation exchangemarkets. Our mechanisms are built on the polymatroidal network flow model by Lawler and Martel. Additionally, they feature nice properties such as the incentive compatibility of buyers, individual rationality, Pareto optimality, and strong budget balance. The firstmechanismis a two-sided generalization of the polyhedral clinching auction by Goel et al. for one-sided markets. The second mechanism is a reduce-to-recover algorithm that reduces the market to be one-sided, applies the polyhedral clinching auction by Goel et al., and lifts the resulting allocation to the original two-sided market via the polymatroidal network flow. Both mechanisms are implemented by polymatroid algorithms. We demonstrate how our framework is applied to the Internet display advertisement auctions.

    DOI: 10.1287/moor.2021.1124

    Scopus

  13. Compression of M<sup>♮</sup>-convex functions — Flag matroids and valuated permutohedra Reviewed

    Satoru Fujishige, Hiroshi Hirai

    Journal of Combinatorial Theory. Series A   Vol. 185   2022.1

     More details

    Publishing type:Research paper (scientific journal)  

    Murota (1998) and Murota and Shioura (1999) introduced concepts of M-convex function and M♮-convex function as discrete convex functions, which are generalizations of valuated matroids due to Dress and Wenzel (1992). In the present paper we consider a new operation defined by a convolution of sections of an M♮-convex function that transforms the given M♮-convex function to an M-convex function, which we call a compression of an M♮-convex function. For the class of valuated generalized matroids, which are special M♮-convex functions, the compression induces a valuated permutohedron together with a decomposition of the valuated generalized matroid into flag-matroid strips, each corresponding to a maximal linearity domain of the induced valuated permutohedron. We examine the details of the structure of flag-matroid strips and the induced valuated permutohedron by means of discrete convex analysis of Murota.

    DOI: 10.1016/j.jcta.2021.105525

    Scopus

  14. A nonpositive curvature property of modular semilattices Reviewed

    Hiroshi Hirai

    Geometriae Dedicata   Vol. 214 ( 1 ) page: 427 - 463   2021.10

     More details

    Publishing type:Research paper (scientific journal)  

    The orthoscheme complex of a graded poset is a metrization of its order complex such that the simplex of each maximal chain is isometric to the Euclidean simplex of vertices 0 , e1, e1+ e2, … , e1+ e2+ ⋯ + en. This notion was introduced by Brady and McCammond in geometric group theory, and has applications in discrete optimization and submodularity theory. We address the question of which poset can yield the orthoscheme complex with CAT(0) property. The orthoscheme complex of a modular lattice has been shown to be CAT(0), and it is conjectured that this is the case for a modular semilattice. In this paper, we prove this conjecture affirmatively. This result implies that a larger class of weakly modular graphs yields CAT(0) complexes.

    DOI: 10.1007/s10711-021-00623-0

    Scopus

  15. Minimum 0-extension problems on directed metrics Reviewed

    Hiroshi Hirai, Ryuhei Mizutani

    Discrete Optimization   Vol. 40   2021.5

     More details

    Publishing type:Research paper (scientific journal)  

    For a metric μ on a finite set T, the minimum 0-extension problem 0-Ext[μ] is defined as follows: Given V⊇T and c:V2→Q+, minimize ∑c(xy)μ(γ(x),γ(y)) subject to γ:V→T,γ(t)=t(∀t∈T), where the sum is taken over all unordered pairs in V. This problem generalizes several classical combinatorial optimization problems such as the minimum cut problem or the multiterminal cut problem. Karzanov and Hirai established a complete classification of metrics μ for which 0-Ext[μ] is polynomial time solvable or NP-hard. This result can also be viewed as a sharpening of the general dichotomy theorem for finite-valued CSPs (Thapper and Živný 2016) specialized to 0-Ext[μ]. In this paper, we consider a directed version 0⃗-Ext[μ] of the minimum 0-extension problem, where μ and c are not assumed to be symmetric. We extend the NP-hardness condition of 0-Ext[μ] to 0⃗-Ext[μ]: If μ cannot be represented as the shortest path metric of an orientable modular graph with an orbit-invariant “directed” edge-length, then 0⃗-Ext[μ] is NP-hard. We also show a partial converse: If μ is a directed metric of a modular lattice with an orbit-invariant directed edge-length, then 0⃗-Ext[μ] is tractable. We further provide a new NP-hardness condition characteristic of 0⃗-Ext[μ], and establish a dichotomy for the case where μ is a directed metric of a star.

    DOI: 10.1016/j.disopt.2021.100642

    Scopus

  16. Computing the nc-Rank via discrete convex optimization on cat(0) spaces Reviewed

    Masaki Hamada, Hiroshi Hirai

    SIAM Journal on Applied Algebra and Geometry   Vol. 5 ( 3 ) page: 455 - 478   2021

     More details

    Publishing type:Research paper (scientific journal)  

    We study the noncommutative rank (nc-rank) computation of a symbolic matrix whose entries are linear forms in noncommutative variables. For this problem, polynomial time algorithms were given by Garg, Gurvits, Oliveira, and Wigderson over the rational numbers, and by Ivanyos, Qiao, and Subrahmanyam over arbitrary fields. We present a significantly different polynomial time algorithm that works for any field. Our algorithm is based on a combination of submodular optimization on modular lattices and convex optimization on CAT(0) spaces.

    DOI: 10.1137/20M138836X

    Scopus

  17. Weakly modular graphs and nonpositive curvature Reviewed

    Jérémie Chalopin, Victor Chepoi, Hiroshi Hirai, Damian Osajda

    Memoirs of the American Mathematical Society   Vol. 268 ( 1309 ) page: 1 - 172   2020.11

     More details

    Publishing type:Research paper (scientific journal)  

    This article investigates structural, geometrical, and topological characterizations and properties of weakly modular graphs and of cell complexes derived from them. The unifying themes of our investigation are various “nonpositive curvature” and “local-to-global” properties and characterizations of weakly modular graphs and their subclasses. Weakly modular graphs have been introduced as a far-reaching common generalization of median graphs (and more generally, of modular and orientable modular graphs), Helly graphs, bridged graphs, and dual polar graphs occurring under different disguises (1-skeletons, collinearity graphs, covering graphs, domains, etc.) in several seemingly-unrelated fields of mathematics: • Metric graph theory • Geometric group theory • Incidence geometries and buildings • Theoretical computer science and combinatorial optimization We give a local-to-global characterization of weakly modular graphs and their subclasses in terms of simple connectedness of associated triangle-square complexes and specific local combinatorial conditions. In particular, we revisit characterizations of dual polar graphs by Cameron and by Brouwer-Cohen. We also show that (disk-)Helly graphs are precisely the clique-Helly graphs with simply connected clique complexes. With l1-embeddable weakly modular and sweakly modular graphs we associate high-dimensional cell complexes, having several strong topological and geometrical properties (contractibility and the CAT(0) property). Their cells have a specific structure: they are basis polyhedra of even Δ-matroids in the first case and orthoscheme complexes of gated dual polar subgraphs in the second case. We resolve some open problems concerning subclasses of weakly modular graphs: we prove a Brady-McCammond conjecture about CAT(0) metric on the orthoscheme complexes of modular lattices; we answer Chastand's question about prime graphs for pre-median graphs. We also explore negative curvature for weakly modular graphs.

    DOI: 10.1090/memo/1309

    Scopus

  18. A Compact Representation for Modular Semilattices and Its Applications Reviewed

    Hiroshi Hirai, So Nakashima

    Order   Vol. 37 ( 3 ) page: 479 - 507   2020.10

     More details

    Publishing type:Research paper (scientific journal)  

    A modular semilattice is a semilattice generalization of a modular lattice. We establish a Birkhoff-type representation theorem for modular semilattices, which says that every modular semilattice is isomorphic to the family of ideals in a certain poset with additional relations. This new poset structure, which we axiomatize in this paper, is called a PPIP (projective poset with inconsistent pairs). A PPIP is a common generalization of a PIP (poset with inconsistent pairs) and a projective ordered space. The former was introduced by Barthélemy and Constantin for establishing Birkhoff-type theorem for median semilattices, and the latter by Herrmann, Pickering, and Roddy for modular lattices. We show the Θ(n) representation complexity and a construction algorithm for PPIP-representations of (∧,∨)-closed sets in the product Ln of modular semilattice L. This generalizes the results of Hirai and Oki for a special median semilattice Sk. We also investigate implicational bases for modular semilattices. Extending earlier results of Wild and Herrmann for modular lattices, we determine optimal implicational bases and develop a polynomial time recognition algorithm for modular semilattices. These results can be applied to retain the minimizer set of a submodular function on a modular semilattice.

    DOI: 10.1007/s11083-019-09516-0

    Scopus

  19. On a weighted linear matroid intersection algorithm by Deg-Det computation Reviewed

    Hiroki Furue, Hiroshi Hirai

    Japan Journal of Industrial and Applied Mathematics   Vol. 37 ( 3 ) page: 677 - 696   2020.9

     More details

    Publishing type:Research paper (scientific journal)  

    In this paper, we address the weighted linear matroid intersection problem from computation of the degree of the determinant of a symbolic matrix. We show that a generic algorithm computing the degree of noncommutative determinants, proposed by the second author, becomes an O(mn3log n) time algorithm for the weighted linear matroid intersection problem, where two matroids are given by column vectors of n× m matrices A, B. We reveal that our algorithm is viewed as a “nonstandard” implementation of Frank’s weight splitting algorithm for linear matroids. This gives a linear algebraic reasoning to Frank’s algorithm. Although our algorithm is slower than existing algorithms in the worst case estimate, it has a notable feature. Contrary to existing algorithms, our algorithm works on different matroids represented by another “sparse” matrices A, B, which skips unnecessary Gaussian eliminations for constructing residual graphs.

    DOI: 10.1007/s13160-020-00413-3

    Scopus

  20. Minimum 0-extension problems on directed metrics Reviewed

    Hiroshi Hirai, Ryuhei Mizutani

    Leibniz International Proceedings in Informatics, LIPIcs   Vol. 170   2020.8

     More details

    Publishing type:Research paper (international conference proceedings)  

    For a metric µ on a finite set T, the minimum 0-extension problem 0-Ext[µ] is defined as follows: Given V ⊇ T and c: (V/2) → Q+, minimize P c(xy)µ(γ(x), γ(y)) subject to γ: V → T, γ(t) = t (∀t ∈ T), where the sum is taken over all unordered pairs in V . This problem generalizes several classical combinatorial optimization problems such as the minimum cut problem or the multiterminal cut problem. The complexity dichotomy of 0-Ext[µ] was established by Karzanov and Hirai, which is viewed as a manifestation of the dichotomy theorem for finite-valued CSPs due to Thapper and Živný. In this paper, we consider a directed version →0 -Ext[µ] of the minimum 0-extension problem, where µ and c are not assumed to be symmetric. We extend the NP-hardness condition of 0-Ext[µ] to →0 -Ext[µ]: If µ cannot be represented as the shortest path metric of an orientable modular graph with an orbit-invariant “directed” edge-length, then →0 -Ext[µ] is NP-hard. We also show a partial converse: If µ is a directed metric of a modular lattice with an orbit-invariant directed edge-length, then →0 -Ext[µ] is tractable. We further provide a new NP-hardness condition characteristic of → 0 -Ext[µ], and establish a dichotomy for the case where µ is a directed metric of a star.

    DOI: 10.4230/LIPIcs.MFCS.2020.46

    Scopus

  21. Uniform modular lattices and affine buildings Reviewed

    Hiroshi Hirai

    Advances in Geometry   Vol. 20 ( 3 ) page: 375 - 390   2020.7

     More details

    Publishing type:Research paper (scientific journal)  

    A simple lattice-theoretic characterization for affine buildings of type A is obtained. We introduce a class of modular lattices, called uniform modular lattices, and show that uniform modular lattices and affine buildings of type A constitute the same object. This is an affine counterpart of the well-known equivalence between projective geometries ( complemented modular lattices) and spherical buildings of type A.

    DOI: 10.1515/advgeom-2020-0007

    Scopus

  22. Node-connectivity terminal backup, separately-capacitated multiflow, and discrete convexity Reviewed

    Hiroshi Hirai, Motoki Ikeda

    Leibniz International Proceedings in Informatics, LIPIcs   Vol. 168   2020.6

     More details

    Publishing type:Research paper (international conference proceedings)  

    The terminal backup problems [Anshelevich and Karagiozova, 2011] form a class of network design problems: Given an undirected graph with a requirement on terminals, the goal is to find a minimum cost subgraph satisfying the connectivity requirement. The node-connectivity terminal backup problem requires a terminal to connect other terminals with a number of node-disjoint paths. This problem is not known whether is NP-hard or tractable. Fukunaga (2016) gave a 4/3-approximation algorithm based on LP-rounding scheme using a general LP-solver. In this paper, we develop a combinatorial algorithm for the relaxed LP to find a half-integral optimal solution in O(mlog(mUA)·MF(kn,m+k2n)) time, where m is the number of edges, k is the number of terminals, A is the maximum edge-cost, U is the maximum edge-capacity, and MF(n0,m0) is the time complexity of a max-flow algorithm in a network with n0 nodes and m0 edges. The algorithm implies that the 4/3-approximation algorithm for the node-connectivity terminal backup problem is also efficiently implemented. For the design of algorithm, we explore a connection between the node-connectivity terminal backup problem and a new type of a multiflow, called a separately-capacitated multiflow. We show a min-max theorem which extends Lovász-Cherkassky theorem to the node-capacity setting. Our results build on discrete convex analysis for the node-connectivity terminal backup problem.

    DOI: 10.4230/LIPIcs.ICALP.2020.65

    Scopus

  23. Counting integral points in polytopes via numerical analysis of contour integration Reviewed

    Hiroshi Hirai, Ryunosuke Oshiro, Ken'ichiro Tanaka

    Mathematics of Operations Research   Vol. 45 ( 2 ) page: 455 - 464   2020.5

     More details

    Publishing type:Research paper (scientific journal)  

    In this paper, we address the problem of counting integer points in a rational polytope described by P(y) = {x ∈ ℝm: Ax = y, x ≥ 0}, where A is an n × m integer matrix and y is an n-dimensional integer vector. We study the Z transformation approach initiated in works by Brion and Vergne, Beck, and Lasserre and Zeron from the numerical analysis point of view and obtain a new algorithm on this problem. If A is nonnegative, then the number of integer points in P(y) can be computed in O(poly(n, m, ||y||∞)(||y||∞ + 1)n) time and O(poly(n, m, ||y||∞)) space. This improves, in terms of space complexity, a naive DP algorithm with O((||y||∞ + 1)n)-size dynamic programming table. Our result is based on the standard error analysis of the numerical contour integration for the inverse Z transform and establishes a new type of an inclusion-exclusion formula for integer points in P(y). We apply our result to hypergraph b-matching and obtain a O(poly(n, m, ||b||∞)(||b||∞+ 1)(1−1/k)n) time algorithm for counting b-matchings in a k-partite hypergraph with n vertices and m hyperedges. This result is viewed as a b-matching generalization of the classical result by Ryser for k = 2 and its multipartite extension by Björklund and Husfeldt.

    DOI: 10.1287/moor.2019.0997

    Scopus

  24. A Combinatorial Algorithm for Computing the Rank of a Generic Partitioned Matrix with 2 × 2 Submatrices Reviewed

    Hiroshi Hirai, Yuni Iwamasa

    Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)   Vol. 12125 LNCS   page: 196 - 208   2020

     More details

    Publishing type:Research paper (international conference proceedings)  

    In this paper, we consider the problem of computing the rank of a block-structured symbolic matrix (a generic partitioned matrix) [Formula Presented], where [Formula Presented] is a [Formula Presented] matrix over a field [Formula Presented] and [Formula Presented] is an indeterminate for [Formula Presented] and [Formula Presented]. This problem can be viewed as an algebraic generalization of the bipartite matching problem, and was considered by Iwata and Murota (1995). One of recent interests on this problem lies in the connection with non-commutative Edmonds’ problem by Ivanyos, Qiao and Subrahamanyam (2018), and Garg, Gurvits, Oliveiva and Wigderson (2019), where a result by Iwata and Murota implicitly says that the rank and the non-commutative rank (nc-rank) are the same for this class of symbolic matrices. The main result of this paper is a combinatorial [Formula Presented]-time algorithm for computing the symbolic rank of a [Formula Presented]-type generic partitioned matrix of size [Formula Presented]. Our algorithm is based on the Wong sequence algorithm by Ivanyos, Qiao, and Subrahamanyam for the nc-rank of a general symbolic matrix, but is simpler. Our proposed algorithm requires no blow-up operation, no field extension, and no additional care for bounding the bit-size. Moreover it naturally provides a maximum rank completion of A for an arbitrary field [Formula Presented].

    DOI: 10.1007/978-3-030-45771-6_16

    Scopus

  25. A tractable class of binary vcsps via m-convex intersection Reviewed

    Hiroshi Hirai, Yuni Iwamasa, Kazuo Murota, Stanislav Zivný

    ACM Transactions on Algorithms   Vol. 15 ( 3 )   2019.7

     More details

    Publishing type:Research paper (scientific journal)  

    A binary VCSP is a general framework for the minimization problem of a function represented as the sum of unary and binary cost functions. An important line of VCSP research is to investigate what functions can be solved in polynomial time. Cooper and Živn?classified the tractability of binary VCSP instances according to the concept of "triangle," and showed that the only interesting tractable case is the one induced by the joint winner property (JWP). Recently, Iwamasa, Murota, and Živn?made a link between VCSP and discrete convex analysis, showing that a function satisfying the JWPcan be transformed into a function represented as the sum of two quadratic M-convex functions, which can be minimized in polynomial time via an M-convex intersection algorithm if the value oracle of each M-convex function is given. In this article,we give an algorithmic answer to a natural question:What binary finite-valued CSP instances can be represented as the sum of two quadratic M-convex functions and can be solved in polynomial time via an M-convex intersection algorithm? We solve this problem by devising a polynomial-Time algorithm for obtaining a concrete form of the representation in the representable case. Our result presents a larger tractable class of binary finite-valued CSPs, which properly contains the JWP class.

    DOI: 10.1145/3329862

    Scopus

  26. Uniform semimodular lattices and valuated matroids Reviewed

    Hiroshi Hirai

    Journal of Combinatorial Theory. Series A   Vol. 165   page: 325 - 359   2019.7

     More details

    Publishing type:Research paper (scientific journal)  

    In this paper, we present a lattice-theoretic characterization for valuated matroids, which is an extension of the well-known cryptomorphic equivalence between matroids and geometric lattices (= atomistic semimodular lattices). We introduce a class of semimodular lattices, called uniform semimodular lattices, and establish a cryptomorphic equivalence between integer-valued valuated matroids and uniform semimodular lattices. Our result includes a coordinate-free lattice-theoretic characterization of integer points in tropical linear spaces, incorporates the Dress-Terhalle completion process of valuated matroids, and establishes a smooth connection with Euclidean buildings of type A.

    DOI: 10.1016/j.jcta.2019.02.013

    Scopus

  27. Computing the degree of determinants via discrete convex optimization on euclidean buildings Reviewed

    Hiroshi Hirai

    SIAM Journal on Applied Algebra and Geometry   Vol. 3 ( 3 ) page: 523 - 557   2019

     More details

    Publishing type:Research paper (scientific journal)  

    In this paper, we consider the computation of the degree of the Dieudonne determinant of a linear symbolic matrix A = A0 + A1x1 + \cdot \cdot \cdot + Amxm, where each Ai is an n \times n polynomial matrix over \BbbK [t] and x1, x2, . . ., xm are pairwise ``noncommutative"" variables. This quantity is regarded as a weighted generalization of the noncommutative rank (nc-rank) of a linear symbolic matrix, and its computation is shown to be a generalization of several basic combinatorial optimization problems, such as weighted bipartite matching and weighted linear matroid intersection problems. Based on the work on nc-rank by Fortin and Reutenauer [Sem. Lothar. Combin., 52 (2004), B52f] and Ivanyos, Qiao, and Subrahmanyam [Comput. Complex., 27 (2018), pp. 561-593], we develop a framework to compute the degree of the Dieudonne determinant of a linear symbolic matrix. We show that the deg-det computation reduces to a discrete convex optimization problem on the Euclidean building for SL(\BbbK (t)n). To deal with this optimization problem, we introduce a class of discrete convex functions on the building. This class is a natural generalization of L-convex functions in discrete convex analysis (DCA). We develop a DCA-oriented algorithm (steepest descent algorithm) to compute the degree of determinants. Our algorithm works with matrix computation on \BbbK and uses a subroutine to compute a certificate vector subspace for the nc-rank, where the number of calls of the subroutine is sharply estimated. Our algorithm enhances some classical combinatorial optimization algorithms with new insights, and it is also understood as a variant of the combinatorial relaxation algorithm, which was developed earlier by Murota for computing the degree of the (ordinary) determinant.

    DOI: 10.1137/18M1190823

    Scopus

  28. Reconstructing phylogenetic tree from multipartite quartet system Reviewed

    Hiroshi Hirai, Yuni Iwamasa

    Leibniz International Proceedings in Informatics, LIPIcs   Vol. 123   2018.12

     More details

    Publishing type:Research paper (international conference proceedings)  

    A phylogenetic tree is a graphical representation of an evolutionary history in a set of taxa in which the leaves correspond to taxa and the non-leaves correspond to speciations. One of important problems in phylogenetic analysis is to assemble a global phylogenetic tree from smaller pieces of phylogenetic trees, particularly, quartet trees. Quartet Compatibility is to decide whether there is a phylogenetic tree inducing a given collection of quartet trees, and to construct such a phylogenetic tree if it exists. It is known that Quartet Compatibility is NP-hard but there are only a few results known for polynomial-time solvable subclasses. In this paper, we introduce two novel classes of quartet systems, called complete multipartite quartet system and full multipartite quartet system, and present polynomial time algorithms for Quartet Compatibility for these systems. We also see that complete/full multipartite quartet systems naturally arise from a limited situation of block-restricted measurement.

    DOI: 10.4230/LIPIcs.ISAAC.2018.57

    Scopus

  29. A Dual Descent Algorithm for Node-capacitated Multiflow Problems and Its Applications Reviewed

    Hiroshi Hirai

    ACM Transactions on Algorithms   Vol. 15 ( 1 )   2018.12

     More details

    Publishing type:Research paper (scientific journal)  

    In this article, we develop an O((m log k)MSF(n, m, 1))-time algorithm to find a half-integral node-capacitated multiflow of the maximum total flow-value in a network with n nodes, m edges, and k terminals, where MSF(n, m, γ ) denotes the time complexity of solving the maximum submodular flow problem in a network with n nodes, m edges, and the complexity γ of computing the exchange capacity of the submodular function describing the problem. By using Fujishige-Zhang algorithm for submodular flow, we can find a maximum half-integral multiflow in O(mn 3 log k) time. This is the first combinatorial strongly polynomial time algorithm for this problem. Our algorithm is built on a developing theory of discrete convex functions on certain graph structures. Applications include “ellipsoid-free” combinatorial implementations of a 2-approximation algorithm for the minimum node-multiway cut problem by Garg, Vazirani, and Yannakakis.

    DOI: 10.1145/3291531

    Scopus

  30. A compact representation for minimizers of k-submodular functions Reviewed

    Hiroshi Hirai, Taihei Oki

    Journal of Combinatorial Optimization   Vol. 36 ( 3 ) page: 709 - 741   2018.10

     More details

    Publishing type:Research paper (scientific journal)  

    A k-submodular function is a generalization of submodular and bisubmodular functions. This paper establishes a compact representation for minimizers of a k-submodular function by a poset with inconsistent pairs (PIP). This is a generalization of Ando–Fujishige’s signed poset representation for minimizers of a bisubmodular function. We completely characterize the class of PIPs (elementary PIPs) arising from k-submodular functions. We give algorithms to construct the elementary PIP of minimizers of a k-submodular function f for three cases: (i) a minimizing oracle of f is available, (ii) f is network-representable, and (iii) f arises from a Potts energy function. Furthermore, we provide an efficient enumeration algorithm for all maximal minimizers of a Potts k-submodular function. Our results are applicable to obtain all maximal persistent labelings in actual computer vision problems. We present experimental results for real vision instances.

    DOI: 10.1007/s10878-017-0142-0

    Scopus

  31. Shortest (A+ B) -Path Packing Via Hafnian Reviewed

    Hiroshi Hirai, Hiroyuki Namba

    Algorithmica   Vol. 80 ( 8 ) page: 2478 - 2491   2018.8

     More details

    Publishing type:Research paper (scientific journal)  

    Björklund and Husfeldt developed a randomized polynomial time algorithm to solve the shortest two disjoint paths problem. Their algorithm is based on computation of permanents modulo 4 and the isolation lemma. In this paper, we consider the following generalization of the shortest two disjoint paths problem, and develop a similar algebraic algorithm. The shortest perfect (A+ B) -path packing problem is: given an undirected graph G and two disjoint node subsets A, B with even cardinalities, find shortest | A| / 2 + | B| / 2 disjoint paths whose ends are both in A or both in B. Besides its NP-hardness, we prove that this problem can be solved in randomized polynomial time if | A| + | B| is fixed. Our algorithm basically follows the framework of Björklund and Husfeldt but uses a new technique: computation of hafnian modulo 2 k combined with Gallai’s reduction from T-paths to matchings. We also generalize our technique for solving other path packing problems, and discuss its limitation.

    DOI: 10.1007/s00453-017-0334-0

    Scopus

  32. Computing DM-decomposition of a partitioned matrix with rank-1 blocks Reviewed

    Hiroshi Hirai

    Linear Algebra and Its Applications   Vol. 547   page: 105 - 123   2018.6

     More details

    Publishing type:Research paper (scientific journal)  

    In this paper, we develop a polynomial time algorithm to compute a Dulmage–Mendelsohn-type decomposition of a matrix partitioned into submatrices of rank at most 1.

    DOI: 10.1016/j.laa.2018.02.008

    Scopus

  33. Beyond JWP: A tractable class of binary VCSPs via M-convex intersection Reviewed

    Hiroshi Hirai, Yuni Iwamasa, Kazuo Murota, Stanislav Živný

    Leibniz International Proceedings in Informatics, LIPIcs   Vol. 96   2018.2

     More details

    Publishing type:Research paper (international conference proceedings)  

    A binary VCSP is a general framework for the minimization problem of a function represented as the sum of unary and binary cost functions. An important line of VCSP research is to investigate what functions can be solved in polynomial time. Cooper-Živný classified the tractability of binary VCSP instances according to the concept of “triangle,” and showed that the only interesting tractable case is the one induced by the joint winner property (JWP). Recently, Iwamasa-Murota-Živný made a link between VCSP and discrete convex analysis, showing that a function satisfying the JWP can be transformed into a function represented as the sum of two M-convex functions, which can be minimized in polynomial time via an M-convex intersection algorithm if the value oracle of each M-convex function is given. In this paper, we give an algorithmic answer to a natural question: What binary finite-valued CSP instances can be solved in polynomial time via an M-convex intersection algorithm? We solve this problem by devising a polynomial-time algorithm for obtaining a concrete form of the representation in the representable case. Our result presents a larger tractable class of binary finite-valued CSPs, which properly contains the JWP class.

    DOI: 10.4230/LIPIcs.STACS.2018.39

    Scopus

  34. L-convexity on graph structures Reviewed

    Hiroshi Hirai

    Journal of the Operations Research Society of Japan   Vol. 61 ( 1 ) page: 71 - 109   2018.1

     More details

    Publishing type:Research paper (scientific journal)  

    In this paper, we study classes of discrete convex functions: submodular functions on modular semilattices and L-convex functions on oriented modular graphs. They were introduced by the author in complexity classification of minimum 0-extension problems. We clarify the relationship to other discrete convex functions, such as k-submodular functions, skew-bisubmodular functions, L-convex functions, tree submodular functions, and UJ-convex functions. We show that they actually can be viewed as submodular/L-convex functions in our sense. We also prove a sharp iteration bound of the steepest descent algorithm for minimizing our L-convex functions. The underlying structures, modular semilattices and oriented modular graphs, have rich connections to projective and polar spaces, Euclidean building, and metric spaces of global nonpositive curvature (CAT(0) spaces). By utilizing these connections, we formulate an analogue of the Lovász extension, introduce well-behaved subclasses of submodular/L-convex functions, and show that these classes can be characterized by the convexity of the Lovász extension. We demonstrate applications of our theory to combinatorial optimization problems that include multicommodity flow, multiway cut, and related labeling problems: these problems had been outside the scope of discrete convex analysis so far.

    DOI: 10.15807/jorsj.61.71

    Scopus

  35. A representation of antimatroids by Horn rules and its application to educational systems Reviewed

    Hiyori Yoshikawa, Hiroshi Hirai, Kazuhisa Makino

    Journal of Mathematical Psychology   Vol. 77   page: 82 - 93   2017.4

     More details

    Publishing type:Research paper (scientific journal)  

    We study a representation of an antimatroid by Horn rules, motivated by its recent application to computer-aided educational systems. We associate any set R of Horn rules with the unique maximal antimatroid A(R) that is contained in the union-closed family K(R) naturally determined by R. We address algorithmic and Boolean function theoretic aspects on the association R↦A(R), where R is viewed as the input. We present linear time algorithms to solve the membership problem and the inference problem for A(R). We also provide efficient algorithms for generating all members and all implicates of A(R). We show that this representation is essentially equivalent to the Korte–Lovász representation of antimatroids by rooted sets. Based on the equivalence, we provide a quadratic time algorithm to construct the uniquely-determined minimal representation. These results have potential applications to computer-aided educational systems, where an antimatroid is used as a model of the space of possible knowledge states of learners, and is constructed by giving Horn queries to a human expert.

    DOI: 10.1016/j.jmp.2016.09.002

    Scopus

  36. Discrete convexity and polynomial solvability in minimum 0-extension problems Reviewed

    Hiroshi Hirai

    Mathematical Programming   Vol. 155 ( 1-2 ) page: 1 - 55   2016.1

     More details

    Publishing type:Research paper (scientific journal)  

    A 0-extension of graph Γ is a metric d on a set V containing the vertex set VΓ of Γ such that d extends the shortest path metric of Γ and for all x∈V there exists a vertex s in Γ with d(x,s)=0. The minimum 0-extension problem 0-Ext[Γ] on Γ is: given a set V⊇VΓ and a nonnegative cost function c defined on the set of all pairs of V, find a 0-extension d of Γ with ∑xyc(xy)d(x,y) minimum. The 0-extension problem generalizes a number of basic combinatorial optimization problems, such as minimum (s,t)-cut problem and multiway cut problem. Karzanov proved the polynomial solvability of 0-Ext[Γ] for a certain large class of modular graphs Γ, and raised the question: What are the graphs Γ for which 0-Ext[Γ] can be solved in polynomial time? He also proved that 0-Ext[Γ] is NP-hard if Γ is not modular or not orientable (in a certain sense). In this paper, we prove the converse: if Γ is orientable and modular, then 0-Ext[Γ] can be solved in polynomial time. This completes the classification of graphs Γ for which 0-Ext[Γ] is tractable. To prove our main result, we develop a theory of discrete convex functions on orientable modular graphs, analogous to discrete convex analysis by Murota, and utilize a recent result of Thapper and Živný on valued CSP.

    DOI: 10.1007/s10107-014-0824-7

    Scopus

  37. A compact representation for minimizers of k-submodular functions Reviewed

    Hiroshi Hirai, Taihei Oki

    Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)   Vol. 9849 LNCS   page: 381 - 392   2016

     More details

    Publishing type:Research paper (international conference proceedings)  

    k-submodular functions were introduced by Huber and Kolmogorov as a generalization of bisubmodular functions. This paper establishes a compact representation of minimizers of k-submodular functions by posets with inconsistent pairs (PIPs), and completely characterizes the class of PIPs (elementary PIPs) corresponding to minimizers of k-submodular functions. Our representation coincides with Birkhoff’s representation theorem if k = 1 and with signed-poset representation by Ando and Fujishige if k = 2.We also give algorithms to construct the elementary PIP representing the minimizers of a k-submodular function f for three cases: (i) a minimizing oracle of f is available, (ii) f is networkrepresentable, and (iii) f is the objective function of the relaxation of multiway cut problem. Furthermore, we provide an efficient algorithm to enumerate all maximal minimizers from the PIP representation. Our results are applied to obtain all maximal persistent assignments in labeling problems arising from computer vision.

    DOI: 10.1007/978-3-319-45587-7_33

    Scopus

  38. On uncrossing games for skew-supermodular functions Reviewed

    Hiroshi Hirai

    Journal of the Operations Research Society of Japan   Vol. 59 ( 2 ) page: 218 - 223   2016

     More details

    Publishing type:Research paper (scientific journal)  

    In this note, we consider the uncrossing game for a skew-supermodular function f, which is a two-player game with players, Red and Blue, and abstracts the uncrossing procedure in the cut-covering linear program associated with f. Extending the earlier results by Karzanov for {0, 1}-valued skew-supermodular functions, we present an improved polynomial time strategy for Red to win, and give a strongly polynomial time uncrossing procedure for dual solutions of the cut-covering LP as its consequence. We also mention its implication on the optimality of laminar solutions.

    DOI: 10.15807/jorsj.59.218

    Scopus

  39. On $k$submodular relaxation Reviewed

    Hiroshi Hirai, Yuni Iwamasa

    SIAM Journal on Discrete Mathematics   Vol. 30 ( 3 ) page: 1726 - 1736   2016

     More details

    Publishing type:Research paper (scientific journal)  

    k-submodular functions, introduced by Huber and Kolmogorov, are functions defined on {0, 1, 2;...,k}n satisfying certain submodular-type inequalities. k-submodular functions typically arise as relaxations of NP-hard problems, and the relaxations by k-submodular functions play key roles in design of eficient, approximation, or fixed-parameter tractable algorithms. Motivated by this, we consider the following problem: Given a function f :{1,2...,k}n→ℝ∪{+∞}, determine whether f can be extended to a k-submodular function g : {0,1,2,...K,}n→ℝ∪{+∞}, where g is called a k-submodular relaxation of f, i.e., the restriction of g on {1,2,...k,}n is equal to f. We give a characterization, in terms of polymorphisms, of the functions which admit a k-submodular relaxation, and also give a combinatorial O((kn)2)-time algorithm to find a k-submodular relaxation or establish that a k-submodular relaxation does not exist. Our algorithm has interesting properties: (1) If the input function is integer valued, then our algorithm outputs a half-integral relaxation, and (2) if the input function is binary, then our algorithm outputs the unique optimal relaxation. We present applications of our algorithm to valued constraint satisfaction problems.

    DOI: 10.1137/15M101926X

    Scopus

  40. L-extendable functions and a proximity scaling algorithm for minimum cost multiflow problem Reviewed

    Hiroshi Hirai

    Discrete Optimization   Vol. 18   page: 1 - 37   2015.8

     More details

    Publishing type:Research paper (scientific journal)  

    In this paper, we develop a theory of new classes of discrete convex functions, called L-extendable functions and alternating L-convex functions, defined on the product of trees. We establish basic properties for optimization: a local-to-global optimality criterion, the steepest descend algorithm by successive k-submodular function minimizations, the persistency property, and the proximity theorem. Our theory is motivated by minimum cost free multiflow problem. To this problem, Goldberg and Karzanov gave two combinatorial weakly polynomial time algorithms based on capacity and cost scalings, without explicit running time. As an application of our theory, we present a new simple polynomial proximity scaling algorithm to solve minimum cost free multiflow problem in O(nlog(nAC)MF(kn,km)) time, where n is the number of nodes, m is the number of edges, k is the number of terminals, A is the maximum of edge-costs, C is the total sum of edge-capacities, and MF(<sup>n′</sup>,<sup>m′</sup>) denotes the time complexity to find a maximum flow in a network of <sup>n′</sup> nodes and <sup>m′</sup> edges. Our algorithm is designed to solve, in the same time complexity, a more general class of multiflow problems, minimum cost node-demand multiflow problem, and is the first combinatorial polynomial time algorithm to this class of problems. We also give an application to network design problem.

    DOI: 10.1016/j.disopt.2015.07.001

    Scopus

  41. A combinatorial formula for principal minors of a matrix with tree-metric exponents and its applications Reviewed

    Hiroshi Hirai, Akihiro Yabe

    Journal of Combinatorial Theory. Series A   Vol. 133   page: 261 - 279   2015.7

     More details

    Publishing type:Research paper (scientific journal)  

    Let T be a tree with a vertex set {1, 2, . . ., N}. Denote by dij the distance between vertices i and j. In this paper, we present an explicit combinatorial formula of principal minors of the matrix (tdij), and its applications to tropical geometry, study of multivariate stable polynomials, and representation of valuated matroids. We also give an analogous formula for a skew-symmetric matrix associated with T.

    DOI: 10.1016/j.jcta.2015.02.005

    Scopus

  42. A Linear programming formulation for routing asynchronous power systems of the Digital Grid Reviewed

    Kyohei Shibano, Reo Kontani, Hiroshi Hirai, Mikio Hasegawa, Kazuyuki Aihara, Hisao Taoka, David McQuilkin, Rikiya Abe

    European Physical Journal: Special Topics   Vol. 223 ( 12 ) page: 2611 - 2620   2014.10

     More details

    Publishing type:Research paper (scientific journal)  

    In recent years, practical research related to distributed power generation and networked distribution grids has been increasing. This research uses a relatively abstract model for the cost reduction in the Digital Grid Power Network. In the Digital Grid, the traditional wide-area synchronous grid is divided into smaller segmented grids which are connected asynchronously. In this paper, we demonstrate how to formulate the minimized cost of power generation by using linear programming methods, while considering the cost of electric transmission and distribution and using asynchronous power interchange among separate grids.

    DOI: 10.1140/epjst/e2014-02277-8

    Scopus

  43. On half-integrality of network synthesis problem Reviewed

    Than Nguyen Hau, Hiroshi Hirai, Nobuyuki Tsuchimura

    Journal of the Operations Research Society of Japan   Vol. 57 ( 2 ) page: 63 - 73   2014.6

     More details

    Publishing type:Research paper (scientific journal)  

    Network synthesis problem is the problem of constructing a minimum cost network satisfying a given flow-requirement. A classical result of Gomory and Hu is that if the cost is uniform and the flow requirement is integer-valued, then there exists a half-integral optimal solution. They also gave a simple algorithm to find a half-integral optimal solution. In this paper, we show that this half-integrality and the Gomory-Hu algorithm can be extended to a class of fractional cut-covering problems defined by skew-supermodular functions. Application to approximation algorithm is also given. © The Operations Research Society of Japan.

    DOI: 10.15807/jorsj.57.63

    Scopus

  44. Optimization for centralized and decentralized cognitive radio networks Reviewed

    Mikio Hasegawa, Hiroshi Hirai, Kiyohito Nagano, Hiroshi Harada, Kazuyuki Aihara

    Proceedings of the IEEE   Vol. 102 ( 4 ) page: 574 - 584   2014.4

     More details

    Publishing type:Research paper (scientific journal)  

    Cognitive radio technology improves radio resource usage by reconfiguring the wireless connection settings according to the optimum decisions, which are made on the basis of the collected context information. This paper focuses on optimization algorithms for decision making to optimize radio resource usage in heterogeneous cognitive wireless networks. For networks with centralized management, we proposed a novel optimization algorithm whose solution is guaranteed to be exactly optimal. In order to avoid an exponential increase of computational complexity in large-scale wireless networks, we model the target optimization problem as a minimum cost-flow problem and find the solution of the problem in polynomial time. For the networks with decentralized management, we propose a distributed algorithm using the distributed energy minimization dynamics of the Hopfield-Tank neural network. Our algorithm minimizes a given objective function without any centralized calculation. We derive the decision-making rule for each terminal to optimize the entire network. We demonstrate the validity of the proposed algorithms by several numerical simulations and the feasibility of the proposed schemes by designing and implementing them on experimental cognitive radio network systems. © 2014 IEEE.

    DOI: 10.1109/JPROC.2014.2306255

    Scopus

  45. The maximum multiflow problems with bounded fractionality Reviewed

    Hiroshi Hirai

    Mathematics of Operations Research   Vol. 39 ( 1 ) page: 60 - 104   2014.2

     More details

    Publishing type:Research paper (scientific journal)  

    We consider the weighted maximum multiflow problem with respect to a terminal weight. We show that if the dimension of the tight span associated with the weight is at most 2, then this problem has a 1=12-integral optimal multiflow for every Eulerian supply graph. This result solves a weighted generalization of Karzanov's conjecture for classifying commodity graphs with finite fractionality. In addition, our proof technique proves the existence of an integral or half-integrality optimal multiflow for a large class of multiflow maximization problems, and it gives a polynomial time algorithm. © 2014 INFORMS.

    DOI: 10.1287/moor.2013.0600

    Scopus

  46. Tree metrics and edge-disjoint S-paths Reviewed

    Hiroshi Hirai, Gyula Pap

    Mathematical Programming   Vol. 147 ( 1-2 ) page: 81 - 123   2013.10

     More details

    Publishing type:Research paper (scientific journal)  

    Given an undirected graph G=(V,E) with a terminal set S⊆V, a weight function [InlineEquation not available: see fulltext.] on terminal pairs, and an edge-cost a:E→Z+, the μ-weighted minimum-cost edge-disjoint S-paths problem (μ-CEDP) is to maximize ∑P∈Pμμ(sP, tP)−a(P) over all edge-disjoint sets P of S-paths, where sP, tP denote the ends of P and a(p) is the sum of edge-cost a(e) over edges e in P. Our main result is a complete characterization of terminal weights μ for which μ-CEDP is tractable and admits a combinatorial min–max theorem. We prove that if μ is a tree metric, then μ-CEDP is solvable in polynomial time and has a combinatorial min–max formula, which extends Mader’s edge-disjoint S-paths theorem and its minimum-cost generalization by Karzanov. Our min–max theorem includes the dual half-integrality, which was earlier conjectured by Karzanov for a special case. We also prove that μ-EDP, which is μ-CEDP with a=0, is NP-hard if μ is not a truncated tree metric, where a truncated tree metric is a weight function represented as pairwise distances between balls in a tree. On the other hand, μ-CEDP for a truncated tree metric μ reduces to μ′-CEDP for a tree metric μ′. Thus our result is best possible unless P = NP. As an application, we obtain a good approximation algorithm for μ-EDP with “near” tree metric μ by utilizing results from the theory of low-distortion embedding.

    DOI: 10.1007/s10107-013-0713-5

    Scopus

  47. Half-integrality of node-capacitated multiflows and tree-shaped facility locations on trees Reviewed

    Hiroshi Hirai

    Mathematical Programming   Vol. 137 ( 1-2 ) page: 503 - 530   2013.2

     More details

    Publishing type:Research paper (scientific journal)  

    In this paper, we establish a novel duality relationship between node-capacitated multiflows and tree-shaped facility locations. We prove that the maximum value of a tree-distance-weighted maximum node-capacitated multiflow problem is equal to the minimum value of the problem of locating subtrees in a tree, and the maximum is attained by a half-integral multiflow. Utilizing this duality, we show that a half-integral optimal multiflow and an optimal location can be found in strongly polynomial time. These extend previously known results in the maximum free multiflow problems. We also show that the set of tree-distance weights is the only class having bounded fractionality in maximum node-capacitated multiflow problems. © 2011 Springer and Mathematical Optimization Society.

    DOI: 10.1007/s10107-011-0506-7

    Scopus

  48. Discrete convexity and polynomial solvability in minimum 0-extension problems Reviewed

    Hiroshi Hirai

    Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms     page: 1770 - 1788   2013

     More details

    Publishing type:Research paper (international conference proceedings)  

    The minimum 0-extension problem 0-Ext[Γ] on a graph Γ is: given a set V including the vertex set VΓ of Γ and a nonnegative cost function c denned on the set of all pairs of V, find a 0-extension d of the path metric dΓ of Γ with ∑xy c(xy)d(x, y) minimum, where a 0-extension is a metric d on V such that the restriction of d to VΓ coincides with d Γ and for all x ∈ V there exists a vertex s in Γ with d(x, s) = 0. 0-Ext[Γ] includes a number of basic combinatorial optimization problems, such as minimum (s, t)-cut problem and multiway cut problem. Karzanov proved the polynomial solvability for a certain large class of modular graphs, and raised the question: What are the graphs Γ for which 0-Ext[Γ] can be solved in polynomial time? He also proved that 0-Ext[Γ] is NP-hard if Γ is not modular or not orientable (in a certain sense). In this paper, we prove the converse: if Γ is orientable and modular, then 0-Ext[Γ] can be solved in polynomial time. This completes the classification of the tractable graphs for the 0-extension problem. To prove our main result, we develop a theory of discrete convex functions on orientable modular graphs, analogous to discrete convex analysis by Murota, and utilize a recent result of Thapper and Živný on Valued-CSP. Copyright © SIAM.

    Scopus

  49. On Tight Spans for Directed Distances Reviewed

    Hiroshi Hirai, Shungo Koichi

    Annals of Combinatorics   Vol. 16 ( 3 ) page: 543 - 569   2012.8

     More details

    Publishing type:Research paper (scientific journal)  

    An extension (V, d) of a metric space (S, μ) is a metric space with S ⊆ V, and is said to be tight if there is no other extension (V, d′) of (S, μ) with d′ ≤ d. Isbell and Dress independently found that every tight extension embeds isometrically into a certain metrized polyhedral complex associated with (S, μ), called the tight span. This paper develops an analogous theory for directed metrics, which are "not necessarily symmetric" distance functions satisfying the triangle inequality. We introduce a directed version of the tight span and show that it has a universal embedding property for tight extensions. Also we introduce a new natural class of extensions, called cyclically tight extensions, and we show that there also exists a certain polyhedral complex having a universal property relative to cyclically tightness. This polyhedral complex coincides with (a fiber of) the tropical polytope spanned by the column vectors of -μ, which was earlier introduced by Develin and Sturmfels. Thus this gives a tight-span interpretation to the tropical polytope generated by a nonnegative square matrix satisfying the triangle inequality. As an application, we prove the following directed version of the tree metric theorem: A directed metric μ is a directed tree metric if and only if the tropical rank of -μ is at most two. Also we describe how tight spans and tropical polytopes are applied to the study of multicommodity flows in directed networks. © 2012 Springer Basel AG.

    DOI: 10.1007/s00026-012-0146-5

    Scopus

  50. Bounded fractionality of the multiflow feasibility problem for demand graph K <inf>3</inf>+K <inf>3</inf> and related maximization problems Reviewed

    Hiroshi Hirai

    Journal of Combinatorial Theory. Series B   Vol. 102 ( 4 ) page: 875 - 899   2012.7

     More details

    Publishing type:Research paper (scientific journal)  

    We consider the multiflow feasibility problem whose demand graph is the vertex-disjoint union of two triangles. We show that this problem has a 1/12-integral solution whenever it is feasible and satisfies the Euler condition. This solves a conjecture raised by Karzanov, and completes the classification of the demand graphs having bounded fractionality. We reduce this problem to the multiflow maximization problem whose terminal weight is the graph metric of the complete bipartite graph, and show that it always has a 1/12-integral optimal multiflow for every inner Eulerian graph. © 2012 Elsevier Inc..

    DOI: 10.1016/j.jctb.2012.02.001

    Scopus

  51. On duality and fractionality of multicommodity flows in directed networks Reviewed

    Hiroshi Hirai, Shungo Koichi

    Discrete Optimization   Vol. 8 ( 3 ) page: 428 - 445   2011.8

     More details

    Publishing type:Research paper (scientific journal)  

    In this paper we address a topological approach to multiflow (multicommodity flow) problems in directed networks. Given a terminal weight μ, we define a metrized polyhedral complex, called the directed tight span Tμ, and prove that the dual of the μ-weighted maximum multiflow problem reduces to a facility location problem on Tμ. Also, in case where the network is Eulerian, it further reduces to a facility location problem on the tropical polytope spanned by μ. By utilizing this duality, we establish the classifications of terminal weights admitting a combinatorial minmax relation (i) for every network and (ii) for every Eulerian network. Our result includes the LomonosovFrank theorem for directed free multiflows and IbarakiKarzanovNagamochi's directed multiflow locking theorem as special cases. © 2011 Elsevier B.V. All rights reserved.

    DOI: 10.1016/j.disopt.2011.03.001

    Scopus

  52. Folder complexes and multiflow combinatorial dualities Reviewed

    Hiroshi Hirai

    SIAM Journal on Discrete Mathematics   Vol. 25 ( 3 ) page: 1119 - 1143   2011

     More details

    Publishing type:Research paper (scientific journal)  

    In multiflow maximization problems, there are several combinatorial duality relations, such as the Ford-Fulkerson max-flow min-cut theorem for single commodity flows, Hu's max-biflow min-cut theorem for two-commodity flows, the Lovász-Cherkassky duality theorem for free multiflows, and so on. In this paper, we provide a unified framework for such multiflow combinatorial dualities by using the notion of a folder complex, which is a certain 2-dimensional polyhedral complex introduced by Chepoi. We show that for a nonnegative weight μ on terminal set, the μ-weighted maximum multiflow problem admits a combinatorial duality relation if and only if μ is represented by distances between certain subsets in a folder complex, and we show that the corresponding combinatorial dual problem is a discrete location problem on the graph of the folder complex. This extends a result of Karzanov in the case of metric weights. © 2011 Society for Industrial and Applied Mathematics.

    DOI: 10.1137/090767054

    Scopus

  53. A note on multiflow locking theorem Reviewed

    Hiroshi Hirai

    Journal of the Operations Research Society of Japan   Vol. 53 ( 2 ) page: 149 - 156   2010.6

     More details

    Publishing type:Research paper (scientific journal)  

    This note addresses the undirected multiflow (multicommodity flow) theory. A multifiow in a network with terminal set T can be regarded as a single commodity (A, T\ A)-flow for any nonempty proper subset A C T by ignoring flows not connecting A and T \ A. A set system A on T is said to be lockable if for every network having T as terminal set there exists a multiflow being simultaneously a maximum (A, T \ A)-fiow for every A c A. The multiflow locking theorem, due to Karzanov and Lomonosov, says that A is lockable if and only if it is 9-cross-free. A multiflow can also be regarded as a single commodity (A, B)-flow for every partial cut (A, B) of terminals, where a partial cut is a pair of disjoint subsets (not necessarily a bipartition). Based on this observation, we study the locking property for partial cuts, and prove an analogous characterization for a lockable family of partial cuts. © 2010 The Operations Research Society of Japan.

    DOI: 10.15807/jorsj.53.149

    Scopus

  54. Metric packing for K<inf>3</inf>+K<inf>3</inf> Reviewed

    Hiroshi Hirai

    Combinatorica   Vol. 30 ( 3 ) page: 295 - 326   2010

     More details

    Publishing type:Research paper (scientific journal)  

    In this paper, we consider the metric packing problem for the commodity graph of disjoint two triangles K3+K3, which is dual to the multiflow feasibility problem for the commodity graph K3+K3. We prove a strengthening of Karzanov's conjecture concerning quarterintegral packings by certain bipartite metrics. © 2010 János Bolyai Mathematical Society and Springer Verlag.

    DOI: 10.1007/s00493-010-2447-9

    Scopus

  55. The maximum multiflow problems with bounded fractionality Reviewed

    Hiroshi Hirai

    Proceedings of the Annual ACM Symposium on Theory of Computing     page: 115 - 120   2010

     More details

    Publishing type:Research paper (international conference proceedings)  

    This paper addresses a fundamental issue in the multicommodity flow theory. For an undirected capacitated supply graph (G,c) having commodity graph H, the maximum multiflow problem is to maximize the total flow-value of multicommodity flows with respect to (G,c;H). For a commodity graph H, the fractionality of H is the least positive integer k with property that there exists a 1/k-integral optimal multiflow in the maximum multiflow problem for every integer-capacitated supply graph (G,c) having H as a commodity graph. If such a positive integer k does not exist, then the fractionality is defined to be +∞. Around 1990, Karzanov raised the problem of classifying commodity graphs with finite fractionality, gave a necessary condition (property P) for the finiteness of fractionality, and conjectured that the property P is also sufficient. Our main result affirmatively solves Karzanov's conjecture in algorithmic form: If H has property P, then there exists a 1/24-integral optimal multiflow in maximum multiflow problem for every integer-capacitated supply graph having H as a commodity graph, and there exists a strongly polynomial time algorithm to find it. Our proof is based on a special combinatorial duality relation involving a class of CAT(0) complexes, and on a fractional version of the splitting-off method for finding an optimal multiflow with a bounded denominator. © 2010 ACM.

    DOI: 10.1145/1806689.1806707

    Scopus

  56. Tight spans of distances and the dual fractionality of undirected multiflow problems Reviewed

    Hiroshi Hirai

    Journal of Combinatorial Theory. Series B   Vol. 99 ( 6 ) page: 843 - 868   2009.11

     More details

    Publishing type:Research paper (scientific journal)  

    In this paper, we give a complete characterization of the class of weighted maximum multiflow problems whose dual polyhedra have bounded fractionality. This is a common generalization of two fundamental results of Karzanov. The first one is a characterization of commodity graphs H for which the dual of maximum multiflow problem with respect to H has bounded fractionality, and the second one is a characterization of metrics d on terminals for which the dual of metric-weighed maximum multiflow problem has bounded fractionality. A key ingredient of the present paper is a nonmetric generalization of the tight span, which was originally introduced for metrics by Isbell and Dress. A theory of nonmetric tight spans provides a unified duality framework to the weighted maximum multiflow problems, and gives a unified interpretation of combinatorial dual solutions of several known min-max theorems in the multiflow theory. © 2009 Elsevier Inc. All rights reserved.

    DOI: 10.1016/j.jctb.2009.03.001

    Scopus

  57. Electric network classifiers for semi-supervised learning on graphs Reviewed

    Hiroshi Hirai, Kazuo Murota, Masaki Rikitoku

    Journal of the Operations Research Society of Japan   Vol. 50 ( 3 ) page: 219 - 232   2007.9

     More details

    Publishing type:Research paper (scientific journal)  

    We propose a new classifier, named electric network classifiers, for semi-supervised learning on graphs. Our classifier is based on nonlinear electric network theory and classifies data set with respect to the sign of electric potential. Close relationships to C-SVM and graph kernel methods are revealed. Unlike other graph kernel methods, our classifier does not require heavy kernel computations but obtains the potential directly using efficient network flow algorithms. Furthermore, with flexibility of its formulation, our classifier can incorporate various edge characteristics; influence of edge direction, unsymmetric dependence and so on. Therefore, our classifier has the potential to tackle large complex real world problems. Experimental results show that the performance is fairly good compared with the diffusion kernel and other standard methods.

    DOI: 10.15807/jorsj.50.219

    Scopus

  58. A geometric atudy of the split decomposition Reviewed

    Hiroshi Hirai

    Discrete and Computational Geometry   Vol. 36 ( 2 ) page: 331 - 361   2006.9

     More details

    Publishing type:Research paper (scientific journal)  

    This paper sheds new light on split decomposition theory and T-theory from the viewpoint of convex analysis and polyhedral geometry. By regarding finite metrics as discrete concave functions, Bandelt-Dress' split decomposition can be derived as a special case of more general decomposition of polyhedral/discrete concave functions introduced in this paper. It is shown that the combinatorics of splits discussed in connection with the split decomposition corresponds to the geometric properties of a hyperplane arrangement and a point configuration. Using our approach, the split decomposition of metrics can be naturally extended to distance functions, which may violate the triangle inequality, using partial split distances. © 2006 Springer Science+Business Media, Inc.

    DOI: 10.1007/s00454-006-1243-1

    Scopus

  59. Characterization of the distance between subtrees of a tree by the associated tight span Reviewed

    Hiroshi Hirai

    Annals of Combinatorics   Vol. 10 ( 1 ) page: 111 - 128   2006.6

     More details

    Publishing type:Research paper (scientific journal)  

    A characterization is given to the distance between subtrees of a tree defined as the shortest path length between subtrees. This is a generalization of the four-point condition for tree metrics. For this, we use the theory of the tight span and obtain an extension of the famous result by Dress that a metric is a tree metric if and only if its tight span is a tree. © Birkhäuser Verlag, Basel, 2006.

    DOI: 10.1007/s00026-006-0277-7

    Scopus

  60. M-convex functions and tree metrics Reviewed

    Hiroshi Hirai, Kazuo Murota

    Japan Journal of Industrial and Applied Mathematics   Vol. 21 ( 3 ) page: 391 - 403   2004.10

     More details

    Publishing type:Research paper (scientific journal)  

    We reveal a close relationship between quadratic M-convex functions and tree metrics: A quadratic function defined on the integer lattice points is M-convex if and only if it has a tree representation. Furthermore, a discrete analogue of the Hessian matrix is defined for functions on the integer points. A function is M-convex if and only if the negative of the 'discrete Hessian matrix' is a tree metric matrix at each integer point. Thus, the M-convexity of a function can be characterized by that of its local quadratic approximations.

    DOI: 10.1007/bf03167590

    Scopus

▼display all

MISC 5

  1. From Matrix Scaling to Geodesically-Convex Optimzation on Nonpositively Curved Spaces Invited

    Proceeding of the Thirty-Fourth RAMP Mathematical Optimization Symposium     page: 59 - 79   2023.11

     More details

    Authorship:Lead author, Last author, Corresponding author   Language:Japanese  

  2. CAT(0)空間上のアルゴリズムと最適化について Invited

    平井広志

    電子情報通信学会誌   Vol. 101 ( 3 )   2018

     More details

  3. Discrete convex functions on graphs and their algorithmic applications Invited Reviewed

    Hiroshi Hirai

    Combinatorial Optimization and Graph Algorithms: Communications of NII Shonan Meetings     page: 67 - 100   2017.10

     More details

    The present article is an exposition of a theory of discrete convex functions on certain graph structures, developed by the author in recent years. This theory is a spin-off of discrete convex analysis by Murota, and is motivated by combinatorial dualities in multiflow problems and the complexity classification of facility location problems on graphs. We outline the theory and algorithmic applications in combinatorial optimization problems.

    DOI: 10.1007/978-981-10-6147-9_4

    Scopus

  4. Discrete convex function on graph structure and its application Invited

      Vol. 92   page: 59 - 64   2014.1

     More details

    Language:Japanese  

    CiNii Books

  5. T_X-approaches to multiflows and metrics Invited Reviewed

    平井 広志

    RIMS Kokyrurok Bessatsu   Vol. B23   page: 107 - 130   2010

Presentations 20

  1. 非正曲率空間のアルゴリズムと最適化について Invited

    平井広志

    名古屋大学多元数理科学研究科 大談話会  2023.12.20 

     More details

    Event date: 2023.12

    Presentation type:Oral presentation (invited, special)  

  2. 行列スケーリングから非正曲率空間上の測地的凸最適化へ Invited

    平井広志

    第35回 RAMP 数理最適化シンポジウム (RAMP 2023)  2023.11.20 

     More details

    Event date: 2023.11

    Presentation type:Oral presentation (invited, special)  

  3. Interior point methods on manifolds: theory and applications Invited International conference

    Hiroshi Hirai

    ICIAM2023, Mini-symposium "Advances in Optimization II", 早稲田大学  2023.8.23 

     More details

    Event date: 2023.8

    Presentation type:Oral presentation (invited, special)  

  4. Finding Hall blockers by matrix scaling Invited International conference

    Hiroshi Hirai

    Fifth Conference on Optimization and Machine Learning (DOxML), 政策研究大学院大学(GRIPS)  2023.8.8 

     More details

    Event date: 2023.8

    Presentation type:Oral presentation (invited, special)  

  5. 行列スケーリングから非正曲率空間上の測地的凸最適化へ Invited

    平井広志

    幾何セミナー,東京都立大学  2023.6.30 

     More details

    Event date: 2023.6

    Presentation type:Oral presentation (invited, special)  

  6. 離散凸解析 beyond Z^n Invited

    平井広志

    ワークショップ「離散凸解析と最適化」, 京都大学数理解析研究所  2019.9.9 

  7. 行列スケーリングから非正曲率空間上の測地的凸最適化へ Invited

    平井広志

    JST数学関連3領域連携WS「情報科学と拓く新しい数理科学」,北海道大学  2022.9.12 

  8. 新しい凸性に基づくアルゴリズムと最適化理論 Invited

    平井広志

    「つながる数学」さきがけ数理構造活用領域1期生成果報告会, JST東京本部別館  2023.1.29 

  9. 代数的組合せ最適化 --- Edmonds問題の最近の発展について --- Invited

    平井広志

    RIMS共同研究「組合せ最適化セミナー」, 京都大学数理解析研究所  2019.8.7 

  10. Optimization of Unbounded Convex Functions and its Application to Matrix Scaling Invited

    Hiroshi Hirai

    Theory Colloquium, The Faculty of Computer Science, Ruhr University  2023.3.28 

  11. Metric Graph Theory in Combinatorial Optimization Invited

    Hiroshi Hirai

    Metric Graph Theory and Related Topics, CIRM, onlin  2021.12.7 

  12. Euclidean buildings in combinatorial optimization Invited

    Hiroshi Hirai

    Buildings, Varieties and Applications, MPI-Leipzig  2019.11.12 

  13. Discrete Convex Optimization for Left-Right Action (nc-rank & det), part II Invited

    Hiroshi Hirai

    GCT2022 Online Lecture Series  2021.12.17 

  14. Discrete Convex Optimization for Left-Right Action (nc-rank & det), part I Invited

    Hiroshi Hirai

    GCT2022 Online Lecture Series  2021.12.14 

  15. Computing the nc-rank via discrete convex optimization on CAT(0) spaces Invited

    Hiroshi Hirai

    SIAM Conference on Applied Algebraic Geometry (AG21), Online  2021.8.16 

  16. Computing the nc-rank via discrete convex optimization on CAT(0) spaces Invited

    Hiroshi Hirai

    Optimization Under Symmetry, Simons Institute for the Theory of Computing,  2021.11.29 

  17. CAT(0)空間上のアルゴリズムと最適化について Invited

    平井広志

    談話会,大阪大学  2021.10.25 

  18. Algorithmic and combinatorial aspects of CAT(0) spaces Invited

    平井広志

    日本OR学会「超スマート社会のシステムデザインのための理論と応用」研究部会 第4回研究会, 京都大学数理解析研究所  2019.9.9 

  19. Algorithmic and combinatorial aspects of CAT(0) complexes Invited

    Hiroshi Hirai

    Mathematics and CS Seminar, IST Austria  2019.11.15 

  20. Algebraic combinatorial optimization for noncommutative rank & determinant Invited

    Hiroshi Hirai

    12th Japanese-Hungarian Symposium on Discrete Mathematics and Its Applications, Budapest  2023.3.21 

▼display all

KAKENHI (Grants-in-Aid for Scientific Research) 11

  1. Auction design for two-sided markets: an approach from discrete optimization

    Grant number:21K19759  2021.7 - 2024.3

    Japan Society for the Promotion of Science  Grants-in-Aid for Scientific Research  Grant-in-Aid for Challenging Research (Exploratory)

      More details

    Authorship:Principal investigator  Grant type:Competitive

  2. 新しい凸性に基づくアルゴリズムと最適化理論

    2019.10 - 2023.3

    科学技術振興機構  戦略的な研究開発の推進 戦略的創造研究推進事業 さきがけ 

    平井 広志

      More details

    Authorship:Principal investigator 

    従来のユークリッド空間上の凸性に基づく連続・離散最適化の枠組みを乗り越えて、CAT(0) 空間といった非正曲率距離空間の凸性に基づく新しい連続・離散最適化理論、および計算複雑度・アルゴリズム論を展開し、数学・数理科学・情報科学諸分野へと横断的に活用します。

  3. Exploring novel discrete convexity in discrete optimization and designing high performance algorithms based on it

    Grant number:17K00029  2017.4 - 2021.3

    Japan Society for the Promotion of Science  Grants-in-Aid for Scientific Research  Grant-in-Aid for Scientific Research (C)

    Hirai Hiroshi

      More details

    In this research project, we explored new types of discrete convexity, which will be useful for discrete optimization, and designed algorithms based on it. We introduced the problem of computing the Dieudonne determinant of a matrix having noncommutative variables, and showed that it generalizes fundamental combinatorial optimization problems and can be efficiently solved by discrete convex optimization on a Euclidean building. We introduced a new class of lattices, called uniform semimodular lattices, and showed that it is equivalent to valuated matroids, which is an important class of discrete convex functions. We studied systematically a class of graphs, called weakly modular graphs, which is expected as ground structures of discrete convex functions, and clarified its relationships to nonpositively curved spaces.

  4. Discrete structures and algorithms for multiflow, facility location, and network design

    Grant number:26330023  2014.4 - 2018.3

    Japan Society for the Promotion of Science  Grants-in-Aid for Scientific Research  Grant-in-Aid for Scientific Research (C)

    Hirai Hiroshi

      More details

    In this research project, we developed a new theory of discrete structures across multicommodity flow, facility location, and network design problems in discrete optimization. In particular, we partially extended discrete convex analysis, which was a theory of discrete convex functions on the integer lattice, to more general discrete structures. Based on this theory, we developed combinatorial polynomial time algorithms to classes of multicommodity flow problems for which such good algorithms had not been known before. As an application, we provided a combinatorial 2-approximation algorithm to the node-multiway cut problem.

  5. Development of machine learning algorithms based on discrete convex analysis

    Grant number:26280086  2014.4 - 2018.3

    Japan Society for the Promotion of Science  Grants-in-Aid for Scientific Research  Grant-in-Aid for Scientific Research (B)

    Kawahara Yoshinobu, HIRAI Hiroshi, KANEMURA Atsunori, ISHIHATA Masakazu, TAKEUCHI Koh

      More details

    In this study, we developed several machine learning algorithms based on discrete convexity such as submodularity. In particular, we developed efficient learning algorithm with structured sparsity, which is formulated with continuous relaxations of submodular functions. We applied those to problems in several engineering fields, and confirmed the proposed methods effectiveness in those problems.

  6. Developments of discrete optimization theory and efficient algorithms based on submodular structures

    Grant number:25280004  2013.4 - 2019.3

    Japan Society for the Promotion of Science  Grants-in-Aid for Scientific Research  Grant-in-Aid for Scientific Research (B)

    Fujishige Satoru

      More details

    From the view points of the discrete structures associated with submodularity, we have investigated the theory and algorithms for discrete and combinatorial optimization problems which has been drawing researchers' attention in the world. We have developed a new theory of discrete convex functions, based on submodular structures, and effectively applied the theory to combinatorial and discrete optimization problems. We have also examined a general class of submodular-like discrete structures such as transversal-submodular functions and skew-bisubmodular functions. We then have shown fundamental min-max theorems for such discrete systems and investigated discrete algorithmic structures. We have also shown that the submodular structures play crucial roles in economy with indivisible commodities and a class of allocation problems in gaming situations.

  7. Theory and algorithm of multiflow, facility location, and network design

    Grant number:23740068  2011 - 2013

    Japan Society for the Promotion of Science  Grants-in-Aid for Scientific Research  Grant-in-Aid for Young Scientists (B)

    HIRAI Hiroshi

      More details

    The main result of this research project is to complete the classification of graphs G for which multifacility location problem (minimum 0-extension problem) on G is polynomial time solvable. In the proof, we introduced discrete convex functions on a class of graphs, and opened up new research direction "discrete convexity for multiflow and facility locations." This is an important step toward a unified theory for multiflow, facility location, and network design, which was the goal of this research project.

  8. Developments of the Fundamental Theory of Discrete Optimization andFast Algorithms Based on Submodular Structures

    Grant number:20310088  2008 - 2012

    Japan Society for the Promotion of Science  Grants-in-Aid for Scientific Research  Grant-in-Aid for Scientific Research (B)

    FUJISHIGE Satoru, IWATA Satoru, MAKINO Kazuhisa, KIJIMA Shuji, HIRAI Hiroshi

      More details

    We have investigated large-scale discrete optimization problems by paying special attention to submodular structures which are effective to devise efficient algorithms. Specifically we have examined discrete optimization problems related to network flows, matchings, multiflows, facility location, resource allocation,graph connectivity, communication network design, and queueing networks, discrete structures arisen in dual greedy algorithms such as dual greedy polyhedra and zonotopes,discrete structures for Horn functions and stable matching problems, and so on to establish the fundamental theory and fast algorithms by integrating the knowledge and insights gained on the individual discrete structures.

  9. Multiflows and metrics

    Grant number:20740054  2008 - 2010

    Japan Society for the Promotion of Science  Grants-in-Aid for Scientific Research  Grant-in-Aid for Young Scientists (B)

    HIRAI Hiroshi

      More details

    We studied multiflow problems in combinatorial optimization. We introduced and developed the tight-span duality theory, which extends the duality relationship between multiflows and metrics, a well-known duality since 70's. As a consequence, We solved Karzanov' s problem, one of important open problems in the literature, which asks a complete characterization for the class of multiflow problems admitting combinatorial min-max theorems and the discreteness of flows. This result is an important step toward a unified theory for multiflow problems.

  10. 離散凸解析と離散距離空間の研究

    Grant number:17740056  2005 - 2006

    日本学術振興会  科学研究費助成事業  若手研究(B)

    平井 広志

      More details

    離散凸解析と離散距離空間の理論と応用に関して,本年度は以下のよう研究を行った
    1.6月と1月に韓国のPohang工科大学のJack Koolen教授を訪問し,Tight SpanやSplit分解法,正則多面体分割について有益なディスカッションを行った.特に2度目の訪問においては,私の研究すなわち,Tight SpanやSplit分解法の拡張や関連する話題のチュートリアル講演を行った.これにより,互いの研究のより良い理解が得られた.
    2.前年度に明らかになった4点条件を拡張した「木の上の部分木族間の距離の特徴付け」とTropical行列式との関連を調べた.特に「木の上のパス間の距離」が距離行列の「任意のサイズ4の主対角行列の行列式のTropical化が消える」ことによって特徴付けられることが分かった.これを踏まえて,関連するTropical幾何学に関する文献調査等を行った.また1月に開かれたRIMSの研究集会「計算可換代数と計算代数幾何」において,この結果の一部を講演した.
    3.私が提案した拡張スプリット分解法の系統学への応用に関して調査研究を行った.前年度の調査によって欠損のあるデータへの応用の可能性が見つかったのであるが,特に生物の形態学データからの系統樹構成問題において,絶滅した生物と現存する生物を混ぜて解析する場合にこのような問題が発生する.すなわち絶滅種は化石からデータを取るしかなく数多くの欠損データを含むのである.この問題を扱った論文をいくつか調査し,そこにあるデータに対し,実際に距離を構成して拡張スプリット分解を適用してみた.すると,いくつかのデータに対しては化石種が得られた系統樹内の部分木に対応させられた.これはこの手法の将来的有望性を物語るものと考えている.

  11. Analysis of Large-scale Discrete Optimization Problems and Development of Efficient Algorithms Based on Submodularity Structures

    Grant number:16310111  2004 - 2007

    Japan Society for the Promotion of Science  Grants-in-Aid for Scientific Research  Grant-in-Aid for Scientific Research (B)

    FUJISHIGE Satoru, TAMURA Akihisa, MAKINO Kazuhisa, HIRAI Hiroshi

      More details

    Major results of our research are the following.
    1. By utilizing discrete concave functions and considering possibly bounded side payments, we have established a common generalization of the marriage model due to Gale and Shapley and the assignment model due to Shapley and Shubik that are standard in the theory of two-sided matching markets, and have shown the existence of a pairwise stable outcome in our model.
    2. We have presented a first polynomial-time algorithm for the monotone min-max connected partitioning problem and have shown that the min-max connected partitioning problem is NP-hard if the cost function is not monotone, and that the min-sum connected partitioning problem is NP-hard even if the cost function is monotone. We also considered an evacuation problem in dynamic networks as an application of the tree partitioning problem.
    3. Bisubmodular functions are a natural "directed", or "signed", extension of submodular functions with several applications. We have investigated the difficulty of extending the strongly polynomial version of the ordinary submodular function minimization algorithms to bisubmodular function minimization (BSFM), and we have showen a way around the difficulty. This new method gives the first combinatorial strongly polynomial algorithm for BSFM.
    4. We have considered minimum-cost source-location problems and their generalizations with three connectivity requirements (arc-connectivity requirements and two kinds of vertex-connectivity requirements), and have shown that the source location problem with edge-connectivity requirements in undirected networks is strongly NP-hard. Moreover, we have shown that the source location problems with three connectivity requirements are inapproximable within a ratio of c In D for some constant c, unless every problem in NP has an O (N log^2 N) -time deterministic algorithm. Here D denotes the sum of given demands. We have also devised (1+ In D) -approximation algorithms for all the extended source location problems if we have the integral capacity and demand functions.
    5. We have investigated support vector machine (SVM) with a discrete kernel, named electric network kernel, mined on the vertex set of an undirected graph. Emphasis is laid on mathematical analysis of its theoretical properties with the aid of electric network theory and the theory of discrete metrics. SVM with this kernel admits physical interpretations in terms of resistive eletric networks; in particular, the SVM decision function corresponds to an electric potential.
    6. We nave considered a problem of finding a minimum transversal that can be regarded as a natural generalization of source location problems and external network problems in (undirected) graphs and hypergraphs. We have found an interesting structural characterization of minimal deficient sets and have shown a necessary and sufficient condition for such sets to form a tree hypergraph. By using this characterization, we have obtained a polynomial-time algorithm, which provides first polynomial-time algorithms for source location problem in hypergraphs and external network problems in graphs and hypergraphs.

▼display all

 

Teaching Experience (On-campus) 2

  1. Linear Algebra II

    2023

  2. Linear Algebra II

    2023

Teaching Experience (Off-campus) 1

  1. Geometric Methods in Mathematical Engineering

    2023.10 - 2024.3 The University of Tokyo)