Satoru Iwata
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
(RIMS)
 Kyoto University, Kyoto 6068502, Japan
 Fax: +8175 (753) 7272
Lecture Notes
Discrete Methods in Informatics (Topics in Combinatorial Optimization)
at University of Tokyo (October 2005  January 2006)
Publications
Discrete Convex Analysis
 A Capacity Scaling Algorithm for MConvex Submodular Flow
(with S. Moriguchi, K. Murota), Math. Programming,
103 (2005), 181202.
 Conjugate Scaling Algorithm for Fencheltype Duality
in Discrete Convex Optimization (with M. Shigeno),
SIAM J. Optim., 13 (2003), 204211.
Submodular Function Minimization
 Submodular Function Minimization,
Math. Programming, 112 (2008), 4564.

A Faster Scaling Algorithm for Minimizing Submodular Functions,
SIAM J. Comput., 32 (2003), 833840.
 A PushRelabel Framework for Submodular Function Minimization
and Applications to Parametric Optimization (with L. Fleischer),
Discrete Appl. Math., 131 (2003), 311322.
 A Descent Method for Submodular Function Minimization
(with S. Fujishige), Math. Programming, 92 (2002),
387390.
 A Fully Combinatorial Algorithm for Submodular Function
Minimization,
J. Combin. Theory, Ser. B, 84 (2002), 203212.

A Combinatorial Strongly Polynomial Algorithm for Minimizing
Submodular Functions (with L. Fleischer and S. Fujishige),
J. ACM, 48 (2001), 761777.
 Minimizing a Submodular Function Arising from a Concave Function
(with S. Fujishige), Discrete Appl. Math., 92 (1999), 211215.
Submodular Flow
 A Strongly Polynomial Cut Canceling Algorithm for Minimum Cost
Submodular Flow (with S. T. McCormick and M. Shigeno),
SIAM J. Discrete Math., 19 (2005), 304320.
 Fast Cycle Canceling Algorithms for Minimum Cost Submodular Flow
(with S. T. McCormick, and M. Shigeno), Combinatorica,
23 (2003), 503525.
 A Faster Capacity Scaling Algorithm for Minimum Cost
Submodular Flow (with L. Fleischer and S. T. McCormick),
Math. Programming, 92 (2002), 119139.
 A Fast Cost Scaling Algorithm for Submodular Flow
(with S. T. McCormick and M. Shigeno),
Inform. Process. Lett., 74 (2000), 123128.
 A Fast Parametric Submodular Intersection Algorithm for
Strong Map Sequences (with K. Murota and M. Shigeno),
Math. Oper. Res., 22 (1997), 803813.
 A Capacity Scaling Algorithm for Convex Cost Submodular Flows,
Math. Programming, 76 (1997), 299308.
 A CostScaling Algorithm for 01 Submodular Flows (with M. Shigeno),
Discrete Appl. Math., 73 (1997), 261273.
Network Flow
 Locating Sources to Meet Flow Demands in Undirected Networks
(with K. Arata, K. Makino, and S. Fujishige),
J. Algorithms, 42 (2002), 5468.
 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), 76104.
 Fast Bipartite Network Flow Algorithms for Assembly and Scheduling
(with T. Matsui and S. T. McCormick),
Oper. Res. Lett., 22 (1998), 137143.
Graph Orientation
 An Algorithm for Minimimum Cost ArcConnectivity Orientations
(with Y. Kobayashi), Algorithmica, 56 (2010), 437447.
 Recent Results on WellBalanced Orientations
(with A. Bernath, T. Kiraly, Z. Kiraly, and Z. Szigeti),
Discrete Optim., 5 (2008), 663676.
Matroid Intersection
 The Independent Even Factor Problem (with K. Takazawa),
SIAM J. Discrete Math., 22 (2008), 14111427.
 A Constrained Independent Set Problem for Matroids
(with T. Fleiner and A. Frank),
Oper. Res. Lett., 32 (2004), 2326.
 On Matroid Intersection Adjacency,
Discrete Math., 242 (2002), 277281.
 A Dual Approximation Approach to Weighted Matroid Intersection
(with M. Shigeno), Oper. Res. Lett., 18 (1995), 153156.
DeltaMatroid

Bisubmodular Function Minimization (with S. Fujishige),
SIAM J. Discrete Math., 19 (2006), 10651073.
 Matroid Matching via Mixed SkewSymmetric Matrices
(with J. Geelen),
Combinatorica, 25 (2005), 187215.
 The Linear DeltaMatroid Parity Problem
(with J. F. Geelen and K. Murota),
J. Combin. Theory, Ser. B, 88 (2003), 377398.
Linking System
 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), 315324.
DifferentialAlgebraic Equations
 Tractability Index of Hybrid Equations for Circuit Simulation
(with M. Takamatsu and C. Tischendrof), Math. Comput.,
to appear.
 Index Minimization of DifferentialAlgebraic Equations
in Hybrid Analysis for Circuit Simulation (with M. Takamatsu),
Math. Programming, 121 (2010), 105121.
 Index Characterization of DifferentialAlgebraic Equations
in Hybrid Analysis for Circuit Simulation (with M. Takamatsu),
Int. J. Circuit Theory Appl., 38 (2010), 419440.
 Index Reduction for DifferentialAlgebraic Equations
by Substitution Method (with M. Takamatsu),
Linear Algebra Appl., 429 (2008), 22682277.
Matrix Pencils
 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), 245259.
 Computing the Maximum Degree of Minors in Matrix Pencils via
Combinatorial Relaxation, Algorithmica, 36 (2003),
331341.
Polynomial Matrices
 Computing the Degrees of All Cofactors in Mixed Polynomial Matrices
(with M. Takamatsu), SIAM J. Discrete Math., 23 (2009),
647660.
 Combinatorial Relaxation Algorithm for Mixed Polynomial Matrices
(with K. Murota), Math. Programming, 90 (2001),
353371.
 PrimalDual Combinatorial Relaxation Algorithms for the Maximum
Degree of Subdeterminants (with K. Murota and I. Sakuta),
SIAM J. Sci. Comput., 17 (1996), 9931012.
Signed Matrices
 Solving Linear Programs from Sign Patterns (with N. Kakimura),
Math. Programming, 114 (2008), 393418.
 Computing the Inertia from Sign Patterns (with. N. Kakimura),
Math. Programming, 110 (2007), 229244.
Partitioned Matrices
 A Minimax Theorem and a DulmageMendelsohn Type Decomposition for
a Class of Generic Partitioned Matrices (with K. Murota),
SIAM J. Matrix Anal. Appl., 16 (1995), 719734.
 BlockTriangularizations of Partitioned Matrices under
Similarity/Equivalence Transformations (with H. Ito and K. Murota),
SIAM J. Matrix Anal. Appl., 15 (1994), 12261255.
Decomposition Technique

BlockTriangularization of SkewSymmetric Matrices,
Linear Algebra Appl., 273 (1998), 215226.

Horizontal Principal Structure of Layered Mixed Matrices: Decomposition of
Discrete Systems by DesignVariable Selections (with K. Murota),
SIAM J. Discrete Math., 9 (1996), 7186.

Principal Structure of Submodular Systems and Hitchcocktype
Independent Flows, Combinatorica, 15 (1995), 515532.

A Theorem on the Principal Structure for Independent Matchings
(with K. Murota), Discrete Appl. Math., 61 (1995), 229244.
Game Theory
 A Network Flow Approach to Cost Allocation for Rooted Trees
(with N. Zuiki), Networks, 44 (2004), 297301.
Control Theory
 Structural Analysis of FaultTolerance for Homogeneous Systems
(with R. Tanaka and S. Shin) Trans. SICE, 33 (1997),
441447.
 Hinfinity Optimal Control for Symmetric Linear Systems,
Japan J. Indust. Appl. Math., 10 (1993), 97107.