Meigu Guan

Un exemple de problème du postier chinois de Guan (arêtes noires et poids) et sa solution optimale (doublement des arêtes rouges pour produire un multigraphe eulérien).

Guan est connu pour la formulation du problème du postier chinois[1]. Ce problème algorithmique est une généralisation du problème de la promenade d'Euler, dans lequel l'entrée est un graphe à arêtes pondérées et le but est de trouver un cycle de poids total minimum qui permet de visiter chaque arête du graphe au moins une fois. Les applications de ce problème comprennent des problèmes de planification des transports tels que la planification des itinéraires pour une flotte de chasse-neiges pour nettoyer toutes les rues d'une ville, en un temps total minimum[2].

Guan a travaillé comme chargé de cours à la Université normale du Shandong (en) pendant le Grand Bond en avant de 1958 à 1960, période au cours de laquelle les mathématiciens chinois ont été encouragés à travailler sur des problèmes pratiques. Il a publié ses travaux sur ce problème, alors appelé « problème d'inspection des routes », en 1960, et son livre a été traduit en anglais en 1962[1]. Il a attiré l'attention de Jack Edmonds, qui a donné au problème son autre nom, le « problème du postier chinois », en l'honneur de Guan[3] - [4] et a prouvé que ce problème peut être résolu de manière optimale en temps polynomial.

L'une des contributions ultérieures de Guan a été de prouver que, en revanche, le « problème du postier dans le vent » est NP-complet; c'est une version généralisée du problème du postier dans lequel le coût de la traversée d'une arête dépend de la direction dans laquelle elle est parcourue[5].

Guan achève ses études en 1957 à l'Université normale de la Chine de l'Est de Shanghai, et la même année, il rejoint le corps professoral de la Shandong Normal University[6]. Il a servi en tant que président de la Shandong Normal University de 1984 à 1990. Il est ensuite devenu directeur du département de recherche opérationnelle à l'Université Fudan de 1990 à 1995, date après laquelle il est parti à l'école de commerce de l'Institut royal de technologie de Melbourne en Australie[1].

• (zh) Mei-ko Kwan, « 奇偶点图上作业法 (programmation d'un graphique en utilisant des points impaires et paires) », Acta Mathematica Sinica (en), vol. 10,‎ 1960, p. 263–266 (MR 0162630, lire en ligne). Traduit du Chinois, Mathématiques 1), American Mathematical Society, 1962, pp. 273-277.
• (zh) Meigu Guan et Handing Zheng, Linear Programming, Shandong Science and Technology Press, 1983.
• Meigu Guan, « On the windy postman problem », Discrete Applied Mathematics, vol. 9, n^o 1,‎ 1984, p. 41–46 (DOI 10.1016/0166-218X(84)90089-1, MR 754427).
• Meigu Guan, Graph theory and its applications: East and West (Jinan, 1986), vol. 576, New York, New York Academy of Sciences, 1989 (DOI 10.1111/j.1749-6632.1989.tb16400.x, MR 1110817), p. 203–218.

• Notices d'autorité :

  • VIAF
  • ISNI
  • LCCN
  • WorldCat