54 citations · 123 across the 39 of their papers we have counts for
45 papers
On integral polytopes related to Edmonds' problem
Hiroshi Hirai
In this paper, we study polyhedral aspects on commutative and noncommutative Edmonds' problems for computing the rank of linear symbolic matrix . We regar…
Horospherically convex optimization for fractional subspace packing and its applications
Hiroshi Hirai
In this paper, we address a semi-infinite LP relaxation of the vector-subspace packing problem. This is a higher-dimensional generalization of the fractional linear matroid parity…
Generalized gradient flows in Hadamard manifolds and convex optimization on entanglement polytopes
Hiroshi Hirai
In this paper, we address the optimization problem of minimizing over a Hadamard manifold , where is a convex function on , is the differen…
A scaling characterization of nc-rank via unbounded gradient flow
Hiroshi Hirai
Given a tuple of complex matrices , the linear symbolic matrix is nonsingular in the noncomm…
Gradient descent for unbounded convex functions on Hadamard manifolds and its applications to scaling problems
Hiroshi Hirai, Keiya Sakabe
In this paper, we study the asymptotic behavior of continuous- and discrete-time gradient flows of a ``lower-unbounded" convex function on a Hadamard manifold , particularly…
Algebraic combinatorial optimization on the degree of determinants of noncommutative symbolic matrices
Hiroshi Hirai, Yuni Iwamasa, Taihei Oki +1
We address the computation of the degrees of minors of a noncommutative symbolic matrix of form \[ A[c] := \sum_{k=1}^m A_k t^{c_k} x_k, \] where are matrices over a field $\…
Interior-point methods on manifolds: theory and applications
Hiroshi Hirai, Harold Nieuwboer, Michael Walter
Interior-point methods offer a highly versatile framework for convex optimization that is effective in theory and practice. A key notion in their theory is that of a self-concordan…
Polyhedral Clinching Auctions for Indivisible Goods
Hiroshi Hirai, Ryosuke Sato
In this study, we propose the polyhedral clinching auction for indivisible goods, which has so far been studied for divisible goods. As in the divisible setting by Goel et al. (201…
Two flags in a semimodular lattice generate an antimatroid
Koyo Hayashi, Hiroshi Hirai
A basic property in a modular lattice is that any two flags generate a distributive sublattice. It is shown (Abels 1991, Herscovic 1998) that two flags in a semimodular lattice no…
Finding Hall blockers by matrix scaling
Koyo Hayashi, Hiroshi Hirai, Keiya Sakabe
For a given nonnegative matrix , the matrix scaling problem asks whether can be scaled to a doubly stochastic matrix for some positive diagonal matrices $…
Convex analysis on Hadamard spaces and scaling problems
Hiroshi Hirai
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…
Computing the nc-rank via discrete convex optimization on CAT(0) spaces
Masaki Hamada, Hiroshi Hirai
In this paper, we address the noncommutative rank (nc-rank) computation of a linear symbolic matrix \[ A = A_1 x_1 + A_2 x_2 + \cdots + A_m x_m, \] where each is an $n \times…
Node-Connectivity Terminal Backup, Separately-Capacitated Multiflow, and Discrete Convexity
Hiroshi Hirai, Motoki Ikeda
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…
A cost-scaling algorithm for computing the degree of determinants
Hiroshi Hirai, Motoki Ikeda
In this paper, we address computation of the degree of Dieudonné determinant of \[ A = \sum_{k=1}^m A_k x_k t^{c_k}, \] where ar…
Minimum 0-Extension Problems on Directed Metrics
Hiroshi Hirai, Ryuhei Mizutani
For a metric on a finite set , the minimum 0-extension problem 0-Ext is defined as follows: Given and , minimi…
Compression of M-convex Functions -- Flag Matroids and Valuated Permutohedra
Satoru Fujishige, Hiroshi Hirai
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 v…
A combinatorial algorithm for computing the rank of a generic partitioned matrix with submatrices
Hiroshi Hirai, Yuni Iwamasa
In this paper, we consider the problem of computing the rank of a block-structured symbolic matrix (a generic partitioned matrix) , where is a $2 \tim…
Helly groups
Jérémie Chalopin, Victor Chepoi, Anthony Genevois +2
Helly graphs are graphs in which every family of pairwise intersecting balls has a non-empty intersection. This is a classical and widely studied class of graphs. In this article w…
A Cost-Scaling Algorithm for Minimum-Cost Node-Capacitated Multiflow Problem
Hiroshi Hirai, Motoki Ikeda
In this paper, we address the minimum-cost node-capacitated multiflow problem in an undirected network. For this problem, Babenko and Karzanov (2012) showed strongly polynomial-tim…
On a weighted linear matroid intersection algorithm by deg-det computation
Hiroki Furue, Hiroshi Hirai
In this paper, we address the weighted linear matroid intersection problem from the computation of the degree of the determinants of a symbolic matrix. We show that a generic algor…
A Nonpositive Curvature Property of Modular Semilattices
Hiroshi Hirai
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, e_…
Counting Integral Points in Polytopes via Numerical Analysis of Contour Integration
Hiroshi Hirai, Ryunosuke Oshiro, Ken'ichiro Tanaka
In this paper, we address the problem of counting integer points in a rational polytope described by , where is an $n \t…
Computing the degree of determinants via discrete convex optimization on Euclidean buildings
Hiroshi Hirai
In this paper, we consider the computation of the degree of the Dieudonné determinant of a linear symbolic matrix , where each is an $n…
Uniform semimodular lattices and valuated matroids
Hiroshi Hirai
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 geometr…