**Satoru FUJISHIGE ** (Professor Emeritus, Dr. Eng.)

Research Institute for Mathematical Sciences

Kyoto University

**Research Feilds**- Mathematical Engineering, Mathematical Programming
- Combinatorial Optimization
- Discrete Algorithms
- Graphs, Networks, and Matroids
- Submodular Functions
- Location and Scheduling Problems
- The LP-Newton Method for Linear Programming

**Lecture**- NIPS Workshop on Discrete Optimization in Machine Learning (DISCML) 2012 (plenary talk): Submodularity and Discrete Convexity (video)

**Prize**

- 2003 Fulkerson Prize (The American Mathematical Society and The Mathematical Programming Society (the name of the latter was changed to The Mathematical Optimization Society in 2011))

**Editorial Board Members**

- 1987--Present: Discrete Applied Mathematics
- 2004--Present: Discrete Optimization
- 2005--Present: Pacific Journal of Optimization
- 2008--2010 (Editor): Journal of the Operations Research Society of Japan

**Books**

- S. Fujishige: "Submodular Functions and Optimization" (North-Holland, 1991) (2nd ed., Elsevier, 2005)
- M. Iri, S. Fujishige, and T. Oyama: "Graphs, Networks, and Matroids" (Sangyo-Tosho, 1986, 2005) (in Japanese)
- S. Fujishige: "Discrete Mathematics " (Iwanami, 1993) (in Japanese)

**Recent noteworthy results**

- S. Fujishige, K. Murota, and A. Shioura: Monotonicity in steepest ascent algorithms for polyhedral L-concave functions. Journal of Operations Research Society of Japan, Vol. 58 (2015) 184--208.
- S. Fujishige, M. X. Goemans, T. Harks, B. Peis, and R. Zenklusen: Congestion games viewed from M-convexity. Operations Research Letters, Vol. 43 (2015) 329--333. DOI: 10.1016/j.orl.2015.04.002
- S. Fujishige and J. Massberg: Dual consistent systems of linear inequalities and cardinality constrained polytopes. Mathematical Programming, Ser.B, Vol. 150 (2015) 35--48. DOI 10.1007/s10107-014-0748-2
- S. Fujishige and S. Tanigawa: A min-max theorem for transversal submodular functions and its implications. SIAM Journal on Discrete Mathematics}, Vol. 28 (2014) 1855--1875. http://dx.doi.org/10.1137/130936415
- S. Fujishige: Bisubmodular polyhedra, simplicial divisions, and discrete convexity. Discrete Optimization, Vol. 12 (2014) 115--120.
- S. Fujishige, S. Tanigawa, and Y. Yoshida: Generalized skew bisubmodularity: A characterization and a min-max theorem. Discrete Optimization, Vol. 12 (2014) 1--9.
- B. Chen and S. Fujishige: On the feasible payoff set of two-player repeated games with unequal discounting. International Journal of Game Theory, Vol. 42 (2013), pp. 295--303.
- S. Fujishige: A note on polylinking flow networks. Mathematical Programming, Ser. A, Vol. 137 (2013), pp. 601--607.
- A. Frank, S. Fujishige, N. Kamiyama, and N. Katoh: Independent arborescences in directed graphs. Discrete Mathematics, Vol. 313 (2013), pp. 453--459.
- S. Fujishige and Z. Yang: On revealed preference and indivisibilities. Modern Economy, Vol. 3 (2012), pp. 752--758 (papaer); DOI: 10.4236/me.2012.36096.
- S. Fujishige and N. Kamiyama: "The root location problem for arc-disjoint arborescences. " Discrete Applied Mathematics, Vol. 160 (2012), pp. 1964--1970.
- S. Fujishige and S. Isotani: "A submodular function minimization algorithm based on the minimum-norm base " Pacific Journal of Optimization, Vol. 7 (2011), pp. 3--17 (preprint).
- S. Fujishige: "A note on disjoint arborescences " Combinatorica, Vol. 30(2) (2010), pp. 247--252 (preprint).
- S. T. McCormick and S. Fujishige: "Strongly polynomial and fully combinatorial algorithms for bisubmodular function minimization " Mathematical Programming, Vol. 122 (2010), pp. 87--120.
- S. Fujishige: "Theory of principal partitions revisited. " In: W. Cook, L. Lov\'asz, and J. Vygen (Editors): Research Trends in Combinatorial Optimization (Springer, Berlin, 2009), pp. 127--162 (preprint).
- S. Fujishige, T. Hayashi, and K. Nagano: "Minimizing continuous extensions of discrete convex functions with linear inequality constraints " SIAM Journal on Optimization, Vol. 20 (2009), pp. 856--867.
- S. Fujishige and K. Nagano: "A structure theory for the parametric submodular intersection problem " Mathematics of Operations Research, Vol. 34 (2009), pp. 513--521.
- S. Fujishige, T. Hayashi, K. Yamashita, and U. Zimmermann: "Zonotopes and the LP-Newton method " Optimization and Engineering, Vol. 10 (2009), pp. 193--205.
- M. Sakashita, K. Makino, H. Nagamochi, and S. Fujishige: "Minimum transversals in posi-modular systems " SIAM Journal on Discrete Mathematics, Vol. 23 (2009), pp. 858--871.
- U. Faigle and S. Fujishige: "A general model for matroids and the greedy algorithm" Mathematical Programming, Ser. A, Vol. 119 (2009), pp. 353--369.
- M. Sakashita, K. Makino, and S. Fujishige: "Minimizing a monotone concave function with laminar covering constraints" Discrete Applied Mathematics, Vol. 156 (2008), pp. 204--219.
- M. Sakashita, K. Makino, and S. Fujishige: "Minimum cost source location problems with flow requirements" Algorithmica, Vol. 50 (2008), pp. 555--583.
- S. Fujishige, G. A. Koshevoy, and Y. Sano: "Matroids on convex geometries" Discrete Mathematics, Vol. 307 (2007), pp. 1936--1950.
- S. Fujishige and A. Tamura: "A two-sided discrete-concave market with possibly bounded side payments: an approach by discrete convex analysis" Mathematics of Operations Research, Vol. 32 (2007), pp. 136--155.
- S. Fujishige: "A maximum flow algorithm using MA ordering" Operations Research Letters, Vol. 31 (2003), pp. 176--178. Also see: S. Fujishige and S. Isotani: "New maximum flow algorithms by MA orderings and scaling " Journal of the Operations Research Society of Japan, Vol. 46 (2003), pp. 243-250; and Y. Matsuoka and S. Fujishige: "Practical efficiency of maximum flow algorithms using MA orderings and preflows " Journal of the Operations Research Society of Japan, Vol. 48 (2005), pp. 297-307.
- S. Iwata, L. Fleischer, and S. Fujishige: "A combinatorial strongly
polynomial algorithm for minimizing submodular functions" Journal
of ACM, Vol. 48 (2001), pp. 761-777 [
*2003 Fulkerson Prize-winning paper*].

**Some old but noteworthy results**

- S. Fujishige: "Algorithms for solving the independent-flow problems " Journal of the Operations Research Society of Japan, Vol. 21, No. 2 (June 1978), pp. 189-203 (pdf).

- The list of selected publications

- A code in C for submodular function minimization is available upon request by e-mail.

Office : RIMS Annex, Room 312, RIMS

E-mail : fujishig (at) kurims.kyoto-u.ac.jp