Satoru FUJISHIGE (Professor Emeritus, Dr. Eng.)

Research Institute for Mathematical Sciences
Kyoto University

Japanese version

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

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

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

Office : RIMS Annex, Room 312, RIMS