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 | |
---|---|
Born | 1951 (age 72–73) Japan |
Education | |
Scientific career | |
Fields | Mathematics |
Institutions | |
Thesis | Oriented matroid programming (1982) |
Doctoral advisor | Jack Edmonds |
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]
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]
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. | Avis, David; Fukuda, Komei (1996). "Reverse search for enumeration". Discrete Applied Mathematics. 65 (1–3): 21–46. doi:10.1016/0166-218x(95)00026-n. MR 1380066. Zbl 0854.68070.
|
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.
|