Fujishige, Satoru ( Professor, Dr. Eng. )

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

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, 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: "A note on disjoint arborescences " Combinatorica (to appear)."

• S. T. McCormick and S. Fujishige: "Strongly polynomial and fully combinatorial algorithms for bisubmodular function minimization " Mathematical Programming, Vol. 122 (2009), pp. 87--120.

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

A code in C for submodular function minimization is available upon request.

The list of selected publications