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.
- Department of Mathematical Informatics
- University of Tokyo, Tokyo 113-8656, Japan
- Tel: +81-3 (5841) 7430
Lecture Video
Submodular Function Minimization
NIPS Workshop "Discrete Optimization in Machine Learning," Whistler (December 2010)
A Weighted Linear Matroid Parity Algorithm
William Tutte's 100th Distinguished Lecture Series, Waterloo (June 2017)
Lecture Notes
Discrete Methods in Informatics (Topics in Combinatorial Optimization)
University of Tokyo (October 2005 - January 2006)
Publications
Global Optimization
- 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.
Approximation Algorithms
Submodular Function Minimization
- 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.
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 (2002), 204-211.
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 Algorithms
- Counting Minimum Weight Arborescences (with K. Hayashi), Algorithmica, 80 (2018), 3908-3919.
- Making Bipartite Graphs DM-Irreducible (with K. Berczi, J. Kato, and Y. Yamaguchi),
SIAM J. Discrete Math., 32 (2018), 560-590.
- 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.
- Finding Coherent Cyclic Orders in Strong Digraphs (with T. Matsuda), Combinatorica, 28 (2008), 83-88.
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 and Supermodular Coloring
- List Supermodular Coloring (with Y. Yokoi), Combinatorica, 38 (2018), 1437-1456.
- 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.
Differential-Algebraic Equations
- Index Reduction for Differential-Algebraic Equations with Mixed Matrices (with T. Oki and M. Takamatsu),
J. ACM, 66 (2019), 35: 1-34.
- 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.
Matrix Pencils
- Index Reduction via Unimodular Transformations (with M. Takamatsu),
SIAM J. Matrix Anal. Appl. 39 (2018), 1135-1151.
- On the Kronecker Canonical Form of Singular Mixed Matrix Pencils (with M.
Takamatsu), SIAM J. Contr. Optim., 55 (2017), 2134-2150.
- 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.
Polynomial Matrices
- 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.
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
- Finding a Stable Allocation in Polymatroid Intersection (with Y. Yokoi),
Math. Oper. Res., 45 (2020), 63-85.
- 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.