Meigu Guan (, also Romanized as Mei-Ko Kwan or Mei-ku Kuan, born 1934 in

Shanghai Shanghai, Shanghainese: , Standard Chinese pronunciation: is a direct-administered municipality and the most populous urban area in China. The city is located on the Chinese shoreline on the southern estuary of the Yangtze River, with the ...

) is a Chinese mathematician and one of the country's leading experts on

mathematical programming Mathematical optimization (alternatively spelled ''optimisation'') or mathematical programming is the selection of a best element, with regard to some criteria, from some set of available alternatives. It is generally divided into two subfiel ...

. He is known for his research on the

route inspection problem In graph theory and combinatorial optimization, Guan's route problem, the Chinese postman problem, postman tour or route inspection problem is to find a shortest closed path or circuit that visits every edge of an (connected) undirected graph at ...

, and served as president of

Shandong Normal University Shandong Normal University (, English acronym SDNU) is a university in Jinan City, Shandong Province, China. It is one of the earliest institutions of higher learning established in Shandong Province since the founding of the People's Republic o ...

Research contributions

Guan is known for formulating the

. This problem is a generalization of the

Euler tour In graph theory, an Eulerian trail (or Eulerian path) is a trail in a finite graph that visits every edge exactly once (allowing for revisiting vertices). Similarly, an Eulerian circuit or Eulerian cycle is an Eulerian trail that starts and end ...

problem, in which the input is an

edge-weighted graph In discrete mathematics, particularly in graph theory, a graph is a structure consisting of a set of objects where some pairs of the objects are in some sense "related". The objects are represented by abstractions called '' vertices'' (also call ...

and the goal is to find a

closed walk In graph theory, a cycle in a Graph (discrete mathematics), graph is a non-empty Path (graph theory)#Walk, trail, and path, trail in which only the first and last Vertex (graph theory), vertices are equal. A directed cycle in a directed graph is ...

of minimum total weight that visits every graph edge at least once. Its applications include

transportation planning Transportation planning is the process of defining future policies, goals, investments, and spatial planning designs to prepare for future needs to move people and goods to destinations. As practiced today, it is a collaborative process that i ...

problems such as planning routes for a fleet of

snowplow A snowplow (also snow plow, snowplough or snow plough) is a device intended for mounting on a vehicle, used for removing snow and ice from outdoor surfaces, typically those serving transportation purposes. Although this term is often used to ref ...

s to plow all the streets of a city, in minimum total time. Guan worked as a lecturer at

during the

Great Leap Forward The Great Leap Forward was an industrialization campaign within China from 1958 to 1962, led by the Chinese Communist Party (CCP). Party Chairman Mao Zedong launched the campaign to transform the country from an agrarian society into an indu ...

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. It attracted the attention of

Jack Edmonds Jack R. Edmonds (born April 5, 1934) is an American-born and educated computer scientist and mathematician who lived and worked in Canada for much of his life. He has made fundamental contributions to the fields of combinatorial optimization, po ...

, who gave the problem its alternative name, the "Chinese postman problem", in honor of Guan, and proved that this problem can be solved optimally in

polynomial time In theoretical computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations p ...

. One of Guan's later contributions was to prove that, in contrast, the

windy postman problem Windy may refer to: Music * Windy (album), ''Windy'' (album), a 1968 album by Astrud Gilberto * Windy (EP), ''Windy'' (EP), a 2021 extended play by Jeon So-yeon * Windy (song), "Windy" (song), 1967 * "Windy", 2014 song by Scarlet Pleasure Peopl ...

NP-complete In computational complexity theory, NP-complete problems are the hardest of the problems to which ''solutions'' can be verified ''quickly''. Somewhat more precisely, a problem is NP-complete when: # It is a decision problem, meaning that for any ...

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

Academic career

Guan finished his studies in 1957 at the

East China Normal University East China Normal University (ECNU) is a public university in Shanghai, China. It is affiliated with the Ministry of Education (China), Ministry of Education and co-funded with the Shanghai Municipal People's Government. The university is part of ...

, and in the same year joined the faculty at Shandong Normal University.. He served as president of Shandong Normal University from 1984 to 1990. He then became director of the department of

operations research Operations research () (U.S. Air Force Specialty Code: Operations Analysis), often shortened to the initialism OR, is a branch of applied mathematics that deals with the development and application of analytical methods to improve management and ...

Fudan University Fudan University (FDU) is a public university, national public university in Yangpu, Shanghai, Yangpu, Shanghai, China. It is affiliated with the Ministry of Education (China), Ministry of Education and is co-funded with the Shanghai Municipal ...

from 1990 to 1995, after which he moved to the business school of the

Royal Melbourne Institute of Technology The Royal Melbourne Institute of Technology (abbreviated as RMIT University) is a public research university located in the city of Melbourne in Victoria, Australia., section 4(b) Established in 1887 by Francis Ormond, it is the seventh-o ...

Australia Australia, officially the Commonwealth of Australia, is a country comprising mainland Australia, the mainland of the Australia (continent), Australian continent, the island of Tasmania and list of islands of Australia, numerous smaller isl ...

Selected publications

* . Translated in ''Chinese Mathematics'' 1, American Mathematical Society, 1962, pp. 273–277. * . * . * .

References

{{DEFAULTSORT:Guan, Meigu 1934 births Living people Mathematicians from Shanghai Operations researchers East China Normal University alumni Academic staff of Shandong Normal University Academic staff of Fudan University Academic staff of RMIT University Educators from Shanghai