Мейгу Гуань - Meigu Guan - Wikipedia

Родная форма этого личное имя является Гуань Мейгу. В этой статье используется Западный порядок имен при упоминании лиц.

Мейгу Гуань (Китайский : 管 梅 谷, также романизированный как Мей-Ко Кван или же Мэй-ку Куан, родился 1934 г. в г. Шанхай ) - китайский математик и один из ведущих специалистов страны по математическое программирование.[1] Он известен своими исследованиями проблема проверки маршрута и был президентом Шаньдунский педагогический университет.

Вклад в исследования

Пример задачи проверки маршрута Гуана (черные края и веса) и ее оптимальное решение (удвоение красных краев для получения Эйлеров мультиграф )

Гуань известен тем, что сформулировал проблема проверки маршрута.[1] Эта проблема является обобщением Эйлер тур проблема, в которой вход является реберно-взвешенный граф и цель - найти закрытая прогулка минимального общего веса, который посещает каждое ребро графа хотя бы один раз. Его приложения включают планирование транспортировки проблемы, такие как планирование маршрутов для флота снегоочистители вспахать все улицы города за минимальное время.[2]

Гуань работал преподавателем в Шаньдунский педагогический университет вовремя Большой скачок вперед 1958–1960 гг., во время которого китайских математиков поощряли к работе над практическими задачами. Он опубликовал свою работу по проблеме проверки маршрута в 1960 году, а его статья была переведена на английский язык в 1962 году.[1] Это привлекло внимание Джек Эдмондс, который дал проблеме альтернативное название, "проблема китайского почтальона", в честь Гуаня,[3] и доказал, что эту задачу можно оптимально решить за полиномиальное время.[1]

Одним из более поздних вкладов Гуаня было доказательство того, что, напротив, проблема ветреного почтальона является НП-полный; это обобщенная версия задачи проверки маршрута, в которой стоимость пересечения ребра зависит от направления, в котором оно пересекается.[4]

Академическая карьера

Гуань закончил учебу в 1957 г. Восточно-китайский педагогический университет в Шанхай, и в том же году поступил на факультет Шаньдунского педагогического университета.[5]Он был президентом Шаньдунского педагогического университета с 1984 по 1990 год. Затем он стал директором департамента исследование операций в Университет Фудань с 1990 по 1995 год, после чего перешел в бизнес-школу Королевский технологический институт Мельбурна в Австралия.[1]

Избранные публикации

  • Кван, Мэй-ко (1960), "奇偶 点 图 上 作业 法" [Графическое программирование с использованием нечетных или четных точек], Acta Mathematica Sinica (на китайском), 10: 263–266, МИСТЕР  0162630. Переведено на Китайская математика 1, Американское математическое общество, 1962, стр. 273–277.
  • Гуань, Мейгу; Чжэн, Вручение (1983), 线性 规划 [Линейное программирование] (на китайском языке), Shandong Science and Technology Press.
  • Гуань, Мейгу (1984), «О ветреной проблеме почтальона», Дискретная прикладная математика, 9 (1): 41–46, Дои:10.1016 / 0166-218X (84) 90089-1, МИСТЕР  0754427.
  • Гуань, Мейгу (1989), "Теория графов в Китае", Теория графов и ее приложения: Восток и Запад (Цзинань, 1986), Анналы Нью-Йоркской академии наук, 576, Нью-Йорк: Нью-Йоркская академия наук, стр. 203–218, Дои:10.1111 / j.1749-6632.1989.tb16400.x, МИСТЕР  1110817.

Рекомендации

  1. ^ а б c d е Грётшель, Мартин; Юань, Я-сян (2012), «Эйлер, Мей-Ко Кван, Кенигсберг и китайский почтальон» (PDF), Истории оптимизации: 21-й Международный симпозиум по математическому программированию, Берлин, 19–24 августа 2012 г., Documenta Mathematica, Экстра: 43–50, МИСТЕР  2991468, заархивировано из оригинал (PDF) на 08.08.2016, получено 2016-04-25.
  2. ^ Ву, Маркус (23 февраля 2015 г.), "Математика, которая стоит за тем, чтобы убрать весь этот проклятый снег с вашей улицы", Проводной.
  3. ^ Грёчель и Юань (2012). Некоторые источники указывают Алан Дж. Голдман за предложение этого имени Эдмондсу; см. например Питерс, Вреда; Блэк, Пол Э., ред. (2 сентября 2014 г.), "Проблема китайского почтальона", Словарь алгоритмов и структур данных, Национальный институт стандартов и технологий, получено 2016-04-26.
  4. ^ Гуань (1984).
  5. ^ Грётшель, Мартин (2006), «Лекция 03М2: Производство печатных плат: некоторые проблемы», Пекинский блочный курс «Комбинаторная оптимизация в действии» (PDF), Институт вычислительной математики и научных / инженерных вычислений Китайской академии наук.