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.

- Department of Mathematical Informatics

- University of Tokyo, Tokyo 113-8656, Japan
- Tel: +81-3 (5841) 7430

Submodular Function Minimization

NIPS Workshop "Discrete Optimization in Machine Learning," Whistler (December 2010)

University of Tokyo (October 2005 - January 2006)

- Lecture 1: Bipartite Edge Coloring (English) (Japanese)
- Lecture 2: Edge Coloring (English) (Japanese)
- Lecture 3: Stable Matching (Japanese)
- Lecture 4: Matroid (English) (Japanese)
- Lecture 6: Simultaneous Exchangeability (English) (Japanese)
- Lecture 7: Matroid Intersection (Japanese)
- Lecture 8: Connected Detachment (English) (Japanese)
- Lecture 10: Submodular Function 1 (English) (Japanese)
- Lecture 11: Submodular Function 2 (English) (Japanese)
- Lecture 12: Submodular Function 3 (English) (Japanese)

- Solving the Trust-Region Subproblem by a Generalized Eigenvalue Problem (with S. Adachi, Y. Nakatsukasa, and A. Takeda),
*SIAM J. Optim.*, 27 (2017), 269-291. - Solving Generalized CDT Problems via Two-Parameter Eigenvalues (with S. Sakaue, Y. Nakatsukasa, and A. Takeda),
*SIAM J. Optim.*, 26 (2016), 1669-1694. - Computing the Signed Distance Between Overlapping Ellipsoids (with Y. Nakatsukasa and A. Takeda),
*SIAM J. Optim.*, 25 (2015), 2359-2384.

- Finding 2-Factors Closer to TSP Tours in Cubic Graphs (with S. Boyd and K. Takazawa),
*SIAM J. Discrete Math.*, 27 (2013), 918-939. - Approximating Max-Min Weighted
*T*-joins (with R. Ravi),*Oper. Res. Lett.*, 41 (2013), 321-324.

- A Computational Geometric Approach to Submodular Function Minimization for
Multiclass Queueing Systems (with T. Itoko),
*Japan J. Indust. Appl. Math.*, 29 (2012), 453-468. - 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), 387-390. - A Fully Combinatorial Algorithm for Submodular Function Minimization,
*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 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.

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

- Orientations and Detachments of Graphs with Prescribed Degrees and Connectivity
(with T. Jordan),
*Discrete Optim.*, 12 (2014), 121-128. - 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*, 135 (2012), 1-23. - 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.*, 81 (2012), 923-939. - 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 Singular Mixed Matrix Pencils (with M.
Takamatsu),
*SIAM J. Contr. Optim.*, to appear. - On the Kronecker Canonical Form of Mixed Matrix Pencils (with M.
Takamatsu),
*SIAM J. Matrix Anal. Appl.*, 32 (2011), 44-71. - 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), 331-341.

- Computing the Maximum Degree of Minors in Mixed Polynomial Matrices via
Combinatorial Relaxation (with M. Takamatsu),
*Algorithmica*, 66 (2013), 346-368. - Computing the Degrees of All Cofactors in Mixed Polynomial Matrices (with
M. Takamatsu),
*SIAM J. Discrete Math.*, 23 (2009), 647-660. - Combinatorial Relaxation Algorithm for Mixed Polynomial Matrices (with K.
Murota),
*Math. Programming*, 90 (2001), 353-371. - 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), 441-447. - H-infinity Optimal Control for Symmetric Linear Systems,
*Japan J. Indust. Appl. Math.,*10 (1993), 97-107.