My primary research interests are in the areas of mathematical
programming. I have been working on design and analysis of efficient
algorithms for discrete optimization concerning matroids and
submodular functions. I am also interested in applications of discrete
optimization techniques to algebraic/numerical computation that arises
in systems analysis and control.
- Research Institute for Mathematical Sciences
- Kyoto University, Kyoto 606-8502, Japan
- Fax: +81-75 (753) 7272
Discrete Methods in Informatics (Topics in Combinatorial Optimization)
at University of Tokyo (October 2005 - January 2006)
Discrete Convex Analysis
- A Capacity Scaling Algorithm for M-Convex Submodular Flow
(with S. Moriguchi, K. Murota), Math. Programming,
103 (2005), 181-202.
- Conjugate Scaling Algorithm for Fenchel-type Duality
in Discrete Convex Optimization (with M. Shigeno),
SIAM J. Optim., 13 (2003), 204-211.
Submodular Function Minimization
- Submodular Function Minimization,
Math. Programming, 112 (2008), 45-64.
A Faster Scaling Algorithm for Minimizing Submodular Functions,
SIAM J. Comput., 32 (2003), 833-840.
- A Push-Relabel Framework for Submodular Function Minimization
and Applications to Parametric Optimization (with L. Fleischer),
Discrete Appl. Math., 131 (2003), 311-322.
- A Descent Method for Submodular Function Minimization
(with S. Fujishige), Math. Programming, 92 (2002),
- A Fully Combinatorial Algorithm for Submodular Function
J. Combin. Theory, Ser. B, 84 (2002), 203-212.
A Combinatorial Strongly Polynomial Algorithm for Minimizing
Submodular Functions (with L. Fleischer and S. Fujishige),
J. ACM, 48 (2001), 761-777.
- Minimizing a Submodular Function Arising from a Concave Function
(with S. Fujishige), Discrete Appl. Math., 92 (1999), 211-215.
- A Strongly Polynomial Cut Canceling Algorithm for Minimum Cost
Submodular Flow (with S. T. McCormick and M. Shigeno),
SIAM J. Discrete Math., 19 (2005), 304-320.
- Fast Cycle Canceling Algorithms for Minimum Cost Submodular Flow
(with S. T. McCormick, and M. Shigeno), Combinatorica,
23 (2003), 503-525.
- A Faster Capacity Scaling Algorithm for Minimum Cost
Submodular Flow (with L. Fleischer and S. T. McCormick),
Math. Programming, 92 (2002), 119-139.
- A Fast Cost Scaling Algorithm for Submodular Flow
(with S. T. McCormick and M. Shigeno),
Inform. Process. Lett., 74 (2000), 123-128.
- A Fast Parametric Submodular Intersection Algorithm for
Strong Map Sequences (with K. Murota and M. Shigeno),
Math. Oper. Res., 22 (1997), 803-813.
- A Capacity Scaling Algorithm for Convex Cost Submodular Flows,
Math. Programming, 76 (1997), 299-308.
- A Cost-Scaling Algorithm for 0-1 Submodular Flows (with M. Shigeno),
Discrete Appl. Math., 73 (1997), 261-273.
- Locating Sources to Meet Flow Demands in Undirected Networks
(with K. Arata, K. Makino, and S. Fujishige),
J. Algorithms, 42 (2002), 54-68.
- Relaxed Most Negatived Cycle and Most Positive Cut Canceling
Algorithms for Minimum Cost Flow (with M. Shigeno and S. T. McCormick),
Math. Oper. Res., 25 (2000), 76-104.
- Fast Bipartite Network Flow Algorithms for Assembly and Scheduling
(with T. Matsui and S. T. McCormick),
Oper. Res. Lett., 22 (1998), 137-143.
- An Algorithm for Minimimum Cost Arc-Connectivity Orientations
(with Y. Kobayashi), Algorithmica, 56 (2010), 437-447.
- Recent Results on Well-Balanced Orientations
(with A. Bernath, T. Kiraly, Z. Kiraly, and Z. Szigeti),
Discrete Optim., 5 (2008), 663-676.
- The Independent Even Factor Problem (with K. Takazawa),
SIAM J. Discrete Math., 22 (2008), 1411-1427.
- A Constrained Independent Set Problem for Matroids
(with T. Fleiner and A. Frank),
Oper. Res. Lett., 32 (2004), 23-26.
- On Matroid Intersection Adjacency,
Discrete Math., 242 (2002), 277-281.
- A Dual Approximation Approach to Weighted Matroid Intersection
(with M. Shigeno), Oper. Res. Lett., 18 (1995), 153-156.
Bisubmodular Function Minimization (with S. Fujishige),
SIAM J. Discrete Math., 19 (2006), 1065-1073.
- Matroid Matching via Mixed Skew-Symmetric Matrices
(with J. Geelen),
Combinatorica, 25 (2005), 187-215.
- The Linear Delta-Matroid Parity Problem
(with J. F. Geelen and K. Murota),
J. Combin. Theory, Ser. B, 88 (2003), 377-398.
- A Flow Model Based on Polylinking Systems
(with M. X. Goemans and R. Zenklusen),
Math. Programming, to appear.
- Linking Systems and Matroid Pencils,
J. Oper. Res. Soc. Japan, 50 (2007), 315-324.
- Tractability Index of Hybrid Equations for Circuit Simulation
(with M. Takamatsu and C. Tischendrof), Math. Comput.,
- Index Minimization of Differential-Algebraic Equations
in Hybrid Analysis for Circuit Simulation (with M. Takamatsu),
Math. Programming, 121 (2010), 105-121.
- Index Characterization of Differential-Algebraic Equations
in Hybrid Analysis for Circuit Simulation (with M. Takamatsu),
Int. J. Circuit Theory Appl., 38 (2010), 419-440.
- Index Reduction for Differential-Algebraic Equations
by Substitution Method (with M. Takamatsu),
Linear Algebra Appl., 429 (2008), 2268-2277.
- On the Kronecker Canonical Form of Mixed Matrix Pencils
(with M. Takamatsu), SIAM J. Matrix Anal. Appl., to appear.
- Combinatorial Analysis of Singular Matrix Pencils (with R. Shimizu),
SIAM J. Matrix Anal. Appl., 29 (2007), 245-259.
- Computing the Maximum Degree of Minors in Matrix Pencils via
Combinatorial Relaxation, Algorithmica, 36 (2003),
- Computing the Degrees of All Cofactors in Mixed Polynomial Matrices
(with M. Takamatsu), SIAM J. Discrete Math., 23 (2009),
- Combinatorial Relaxation Algorithm for Mixed Polynomial Matrices
(with K. Murota), Math. Programming, 90 (2001),
- Primal-Dual Combinatorial Relaxation Algorithms for the Maximum
Degree of Subdeterminants (with K. Murota and I. Sakuta),
SIAM J. Sci. Comput., 17 (1996), 993-1012.
- Solving Linear Programs from Sign Patterns (with N. Kakimura),
Math. Programming, 114 (2008), 393-418.
- Computing the Inertia from Sign Patterns (with. N. Kakimura),
Math. Programming, 110 (2007), 229-244.
- A Minimax Theorem and a Dulmage-Mendelsohn Type Decomposition for
a Class of Generic Partitioned Matrices (with K. Murota),
SIAM J. Matrix Anal. Appl., 16 (1995), 719-734.
- Block-Triangularizations of Partitioned Matrices under
Similarity/Equivalence Transformations (with H. Ito and K. Murota),
SIAM J. Matrix Anal. Appl., 15 (1994), 1226-1255.
Block-Triangularization of Skew-Symmetric Matrices,
Linear Algebra Appl., 273 (1998), 215-226.
Horizontal Principal Structure of Layered Mixed Matrices: Decomposition of
Discrete Systems by Design-Variable Selections (with K. Murota),
SIAM J. Discrete Math., 9 (1996), 71-86.
Principal Structure of Submodular Systems and Hitchcock-type
Independent Flows, Combinatorica, 15 (1995), 515-532.
A Theorem on the Principal Structure for Independent Matchings
(with K. Murota), Discrete Appl. Math., 61 (1995), 229-244.
- A Network Flow Approach to Cost Allocation for Rooted Trees
(with N. Zuiki), Networks, 44 (2004), 297--301.
- Structural Analysis of Fault-Tolerance for Homogeneous Systems
(with R. Tanaka and S. Shin) Trans. SICE, 33 (1997),
- H-infinity Optimal Control for Symmetric Linear Systems,
Japan J. Indust. Appl. Math., 10 (1993), 97-107.