Meigu Guan

Meigu Guan (Chinese: 管梅谷, also Romanized as Mei-Ko Kwan or Mei-ku Kuan, born 1934 in Shanghai) was a Chinese researcher who "became one of the leading experts on mathematical programming in China".^[1]

An instance of Guan's route inspection problem (black edges and weights) and its optimal solution (doubling the red edges to produce an Eulerian multigraph)

Guan is known for formulating the route inspection problem.^[1] This problem is a generalization of the Euler tour problem, in which the input is an edge-weighted graph and the goal is to find a closed walk of minimum total weight that visits every graph edge at least once. Its applications include transportation planning problems such as planning routes for a fleet of snowplows to plow all the streets of a city, in minimum total time.^[2] Guan worked as a lecturer at Shandong Normal University during the Great Leap Forward of 1958–1960, during which Chinese mathematicians were encouraged to work on practical problems. He published his work on the route inspection problem in 1960, and his paper was translated into English in 1962.^[1] It attracted the attention of Jack Edmonds, who gave the problem its alternative name, the "Chinese postman problem", in honor of Guan,^[3] and proved that this problem can be solved optimally in polynomial time.^[1] One of Guan's later contributions was to prove that, in contrast, the windy postman problem is NP-complete; this is a generalized version of the route inspection problem in which the cost of traversing an edge depends on the direction in which it is traversed.^[4]

Guan finished his studies in 1957 at the East China Normal University in Shanghai, and in the same year joined the faculty at Shandong Normal University.^[5] He served as president of Shandong Normal University from 1984 to 1990. He then became director of the department of operations research at Fudan University from 1990 to 1995, after which he moved to the business school of the Royal Melbourne Institute of Technology in Australia.^[1]

Selected publications

• Kwan, Mei-ko (1960), "奇偶点图上作业法" [Graphic programming using odd or even points], Acta Mathematica Sinica (in Chinese) 10: 263–266, MR 0162630. Translated in Chinese Mathematics 1, American Mathematical Society, 1962, pp. 273–277.
• Guan, Meigu; Zheng, Handing (1983), 线性规划 [Linear Programming] (in Chinese), Shandong Science and Technology Press.
• Guan, Meigu (1984), "On the windy postman problem", Discrete Applied Mathematics 9 (1): 41–46, doi:10.1016/0166-218X(84)90089-1, MR 754427.
• Guan, Meigu (1989), "Graph theory in China", Graph theory and its applications: East and West (Jinan, 1986), Annals of the New York Academy of Sciences 576, New York: New York Academy of Sciences, pp. 203–218, doi:10.1111/j.1749-6632.1989.tb16400.x, MR 1110817.

References

1. Grötschel, Martin; Yuan, Ya-xiang (2012), "Euler, Mei-Ko Kwan, Königsberg, and a Chinese postman" (PDF), Optimization stories: 21st International Symposium on Mathematical Programming, Berlin, August 19–24, 2012, Documenta Mathematica, Extra: 43–50, MR 2991468.
2. Woo, Marcus (February 23, 2015), "The mathematics behind getting all that damned snow off your street", Wired.
3. Grötschel & Yuan (2012). Some sources credit Alan J. Goldman for suggesting this name to Edmonds; see e.g. Pieterse, Vreda; Black, Paul E., eds. (September 2, 2014), "Chinese postman problem", Dictionary of Algorithms and Data Structures, National Institute of Standards and Technology, retrieved 2016-04-26.
4. Guan (1984).
5. Grötschel, Martin (2006), "03M2 Lecture: Printed Circuit Board Production: Some Issues", Beijing Block Course "Combinatorial Optimization at Work" (PDF), Institute of Computational Mathematics and Scientific/Engineering Computing of Chinese Academy of Sciences.