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 606-8502, Japan

Fax: +81-75 (753) 7272

Lecture Notes

Discrete Methods in Informatics (Topics in Combinatorial Optimization)

at 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)

Publications

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

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

Network Flow

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

Graph Orientation

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

Matroid Intersection

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

Delta-Matroid

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

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), 315-324.

Differential-Algebraic Equations

• Tractability Index of Hybrid Equations for Circuit Simulation (with M. Takamatsu and C. Tischendrof), Math. Comput., to appear.
• 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.

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), 245-259.
• Computing the Maximum Degree of Minors in Matrix Pencils via Combinatorial Relaxation, Algorithmica, 36 (2003), 331-341.

Polynomial Matrices

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

Signed Matrices

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

Partitioned Matrices

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

Decomposition Technique

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

Game Theory

• A Network Flow Approach to Cost Allocation for Rooted Trees (with N. Zuiki), Networks, 44 (2004), 297--301.

Control Theory

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