Naștere |
1934 Shanghai |
---|---|
Instruire | Școala normală superioară din China de Est |
Activități | Matematician , profesor universitar |
Lucrat pentru | Royal Melbourne Institute of Technology , Universitatea Fudan |
---|
Meigu Guan (în chineză :管 梅 谷, romanizat și ca Mei-Ko Kwan sau Mei-ku Kuan , născut în 1934 la Shanghai ) este un matematician și cercetător chinez care „a devenit unul dintre cei mai importanți experți în optimizarea matematică din China”. . Este cunoscut pentru cercetările sale asupra problemei poștașului chinez și a fost președintele Universității Normale din Shandong (ro) .
Guan este cunoscut pentru formularea problemei poștașului chinez . Această problemă algoritmică este o generalizare a problemei Euler walk , în care intrarea este un grafic de margine ponderat și scopul este de a găsi un ciclu de greutate totală minimă care să permită vizitarea fiecărei margini a graficului cel puțin o dată. Aplicațiile acestei probleme includ probleme de planificare a transportului , cum ar fi planificarea rutelor pentru o flotă de pluguri de zăpadă pentru a curăța toate străzile dintr-un oraș, în timp total minim.
Guan a lucrat ca lector la Universitatea Normală Shandong (în) în timpul Marelui Salt înainte din 1958 până în 1960, perioadă în care matematicienii chinezi au fost încurajați să lucreze la probleme practice. El și-a publicat lucrarea despre această problemă, apoi a numit-o „problema inspecției rutiere”, în 1960, iar cartea sa a fost tradusă în limba engleză în 1962. A atras atenția lui Jack Edmonds , care a dat problemei un alt nume, „poștașul chinez” problemă ", în onoarea lui Guan și a dovedit că această problemă poate fi rezolvată optim în timp polinomial .
Una dintre contribuțiile ulterioare ale lui Guan a fost să demonstreze că, pe de altă parte, „problema de poștal care suflă” este NP-completă ; este o versiune generalizată a problemei poștaș în care costul traversării unei margini depinde de direcția în care este parcursă.
Guan a absolvit în 1957 Universitatea Normală China de Est din Shanghai , iar în același an s-a alăturat facultății Universității Normale din Shandong. A ocupat funcția de președinte al Universității Normale Shandong din 1984 până în 1990. A devenit apoi director al departamentului de cercetare operațională de la Universitatea Fudan din 1990 până în 1995, după care a mers la școala de afaceri din Royal Melbourne Institute of Technology din Australia .