Komei Fukuda (Japanese: 福田 公明, born 1951)[1] is a Japanese mathematician known for his contributions to optimization, polyhedral computation and oriented matroid theory. Fukuda is a professor in optimization and computational geometry in the Department of Mathematics and in the Institute of Theoretical Computer Science at ETH Zurich.

Komei Fukuda
Born1951 (age 72–73)
Japan
Education
Scientific career
FieldsMathematics
Institutions
ThesisOriented matroid programming (1982)
Doctoral advisorJack Edmonds

Education and career

edit

Fukuda studied administration engineering at Keio University, graduating in 1974 and earning a master's degree in 1976. He began doctoral work in the same field, but in 1976 transferred to the University of Waterloo to their PhD program in combinatorics and optimization.[2] He completed his PhD in 1982, with Jack Edmonds as his doctoral advisor.[3]

After completing his PhD, he returned to Japan as an assistant professor at the Tokyo Institute of Technology. He moved to the University of Tsukuba as an associate professor in 1989. After visiting the École Polytechnique Fédérale de Lausanne and ETH Zurich in 1993–1994 and 1995–1996 respectively, as an invited professor, he took a joint position as a professor in the departments of mathematics at both universities in 1996. He also held a tenured professorship at McGill University in 2002–2003. In 2008 he gave up his position at the École Polytechnique Fédérale de Lausanne, becoming affiliated only with ETH Zurich, and since 2012 he has held a joint appointment in mathematics and computer science at ETH Zurich.[2]

Contributions

edit

Fukuda has studied finite pivot algorithms in various settings, including linear programming, linear complementarity and their combinatorial abstractions in oriented matroids. With Tamás Terlaky, Fukuda worked on a particular class of pivot algorithms, known as the criss-cross method.[4][FT92][FT97]

With David Avis, Fukuda proposed a reverse-search algorithm for the vertex enumeration problem; their algorithm generates all of the vertices of a convex polytope or, dually, of an arrangement of hyperplanes.[5][6][AF92][AF96]

Selected publications

edit
AF92.
Avis, David; Fukuda, Komei (December 1992). "A pivoting algorithm for convex hulls and vertex enumeration of arrangements and polyhedra". Discrete & Computational Geometry. 8 (1): 295–313. doi:10.1007/BF02293050. MR 1174359. Zbl 0752.68082.
AF96.
FT92.
Fukuda, Komei; Terlaky, Tamás (1992). "Linear complementarity and oriented matroids". Journal of the Operations Research Society of Japan. 35 (1): 45–61. doi:10.15807/jorsj.35.45. MR 1171579. Zbl 0773.90077.
FT97.
Fukuda, Komei; Terlaky, Tamás (1997). Liebling, Thomas M.; de Werra, Dominique (eds.). "Criss-cross methods: A fresh view on pivot algorithms" (PDF). Mathematical Programming, Series B. 79 (Papers from the 16th International Symposium on Mathematical Programming held in Lausanne, 1997, number 1–3): 369–395. doi:10.1007/BF02614325. MR 1464775. S2CID 2794181. Zbl 0887.90113.

References

edit
  1. ^ Birth year from VIAF authority control record, accessed May 23, 2021
  2. ^ a b "Curriculum vitae" (PDF). 28 March 2013. Retrieved 23 May 2021.
  3. ^ Komei Fukuda at the Mathematics Genealogy Project
  4. ^ Terlaky, Tamás (2009). "Criss-cross pivoting rules". In Floudas, Christodoulos A.; Pardalos, Panos M. (eds.). Encyclopedia of Optimization (2nd ed.). Springer. pp. 584–590.
  5. ^ Skiena, Steven S. (2009). The Algorithm Design Manual (2nd ed.). Springer. p. 571. ISBN 9781848000704.
  6. ^ Ziegler, Günter M. (1995). Lectures on Polytopes. Springer. pp. 48–49. ISBN 9783540943655.
edit