Мэйгу Гуань
Мэйгу Гуань | |||
---|---|---|---|
китайский | Канумейя | ||
|
Мэйгу Гуан ( китайский : 管梅谷 , также романизированный как Мэй-Ко Кван или Мэй-ку Куан , родился в 1934 году в Шанхае ) — китайский математик и один из ведущих специалистов страны по математическому программированию . [1] Он известен своими исследованиями проблемы проверки маршрутов и был президентом Шаньдунского педагогического университета .
Вклад в исследования
[ редактировать ]Гуань известен тем, что сформулировал задачу проверки маршрута . [1] Эта задача является обобщением задачи Эйлера об обходе , в которой входными данными является граф, взвешенный по ребрам , и цель состоит в том, чтобы найти замкнутый обход минимального общего веса, который посещает каждое ребро графа хотя бы один раз. Его приложения включают в себя задачи транспортного планирования, такие как планирование маршрутов для парка снегоочистителей, которые будут расчищать все улицы города за минимальное общее время. [2]
Гуань работал преподавателем в Шаньдунском педагогическом университете во время « Большого скачка» 1958–1960 годов, во время которого китайских математиков поощряли работать над практическими задачами. Он опубликовал свою работу по проблеме проверки маршрутов в 1960 году, а его статья была переведена на английский язык в 1962 году. [1] Она привлекла внимание Джека Эдмондса , который дал проблеме альтернативное название — «проблема китайского почтальона» в честь Гуаня. [3] и доказал, что эту задачу можно решить оптимально за полиномиальное время . [1]
Одним из более поздних достижений Гуана было доказательство того, что, напротив, задача о ветреном почтальоне NP -полна ; это обобщенная версия задачи проверки маршрута, в которой стоимость прохождения ребра зависит от направления, в котором оно пересекается. [4]
Академическая карьера
[ редактировать ]Гуань закончил учебу в 1957 году в Восточно-Китайском педагогическом университете в Шанхае и в том же году поступил на факультет Шаньдунского педагогического университета. [5] Он занимал должность президента Шаньдунского педагогического университета с 1984 по 1990 год. Затем он стал директором департамента исследования операций Фуданьского университета с 1990 по 1995 год, после чего перешёл в бизнес-школу Королевского Мельбурнского технологического института в Австралии . [1]
Избранные публикации
[ редактировать ]- Кван, Мей-ко (1960), «Графическое программирование с использованием нечетных или четных точек», Acta Mathematica Sinica (на китайском языке), 10 : 263–266, MR 0162630. Переведено на китайский язык Mathematics 1 , Американское математическое общество, 1962, стр. 273–277.
- Гуань, Мэйгу, Чжэн, Хэндинг (1983), ( на Линейное программирование китайском языке), Shandong Science and Technology Press .
- Гуань, Мейгу (1984), «О проблеме ветреного почтальона», Discrete Applied Mathematics , 9 (1): 41–46, doi : 10.1016/0166-218X(84)90089-1 , MR 0754427 .
- Гуань, Мэйгу (1989), «Теория графов в Китае», Теория графов и ее приложения: Восток и Запад (Цзинань, 1986) , Анналы Нью-Йоркской академии наук, том. 576, Нью-Йорк: Нью-Йоркская академия наук, стр. 203–218, doi : 10.1111/j.1749-6632.1989.tb16400.x , MR 1110817 , S2CID 86165306 .
Ссылки
[ редактировать ]- ^ Jump up to: а б с д и Гретшель, Мартин ; Юань, Я-сян (2012), «Эйлер, Мэй-Ко Кван, Кенигсберг и китайский почтальон» (PDF) , Истории оптимизации: 21-й Международный симпозиум по математическому программированию, Берлин, 19–24 августа 2012 г., Documenta Mathematica , Экстра: 43–50, МР 2991468 .
- ^ Ву, Маркус (23 февраля 2015 г.), «Математика, лежащая в основе уборки всего этого проклятого снега с вашей улицы» , Wired .
- ^ Гретшель и Юань (2012) . Некоторые источники благодарны Алану Дж. Голдману за то, что он предложил это имя Эдмондсу; см., например Питерс, Вреда; Блэк, Пол Э., ред. (2 сентября 2014 г.), «Проблема китайского почтальона» , Словарь алгоритмов и структур данных , Национальный институт стандартов и технологий , получено 26 апреля 2016 г.
- ^ Гуань (1984) .
- ^ Гретшель, Мартин (2006), «Лекция 03M2: Производство печатных плат: некоторые проблемы», Пекинский блочный курс «Комбинаторная оптимизация в работе» (PDF) , Институт вычислительной математики и научных/инженерных вычислений Китайской академии наук .
- 1934 рождения
- Живые люди
- Математики из Шанхая
- Исследователи операций
- Выпускники Восточно-Китайского педагогического университета
- Академический состав Шаньдунского педагогического университета
- Академический состав Фуданьского университета
- Академический состав Университета RMIT
- Преподаватели из Шанхая