Эндрю В. Голдберг

Эндрю Голдберг
Рожденный	Андрей Владислав Гольдберг 1960 (63–64 года)
Альма-матер	Массачусетский технологический институт (бакалавр, доктор философии) Калифорнийский университет в Беркли (MS)
Награды	Сотрудник ACM (2009 г.)
Научная карьера
Учреждения	Амазонка Стэнфордский университет
Диссертация	Эффективные графовые алгоритмы для последовательных и параллельных компьютеров   (1987)
Докторантура	Чарльз Э. Лейзерсон
Докторанты	Эдит Коэн
Веб-сайт	авглаб .с / Эндрю

Эндрю Владислав Голдберг (1960 г.р.) — американский ученый-компьютерщик, занимающийся в основном разработкой, анализом и экспериментальной оценкой алгоритмов. Он также работал над проектированием механизмов, компьютерными системами и теорией сложности. В настоящее время он является старшим главным научным сотрудником Amazon.com .

Образование и карьера

Голдберг учился на бакалавриате в Массачусетском технологическом институте , который окончил в 1982 году. После получения степени магистра в Калифорнийском университете в Беркли он вернулся в Массачусетский технологический институт при финансовой поддержке престижной стипендии Герца, защитив там докторскую степень в 1987 году, защитив диссертацию. об эффективных графовых алгоритмах для последовательных и параллельных компьютеров под руководством Чарльза Э. Лейзерсона . ^[G87]

Карьера и исследования

После получения докторской степени Голдберг поступил на факультет Стэнфордского университета и работал в исследовательском институте NEC, лабораториях Intertrust STAR и исследовательской лаборатории Microsoft в Силиконовой долине. Он присоединился к Amazon.com в 2014 году.

Гольдберг наиболее известен своими исследованиями в области разработки и анализа алгоритмов для графов и сетей, и особенно своей работой над проблемой максимального потока. ^{[ГТ88] [CG97] [GR98]} и задача о кратчайшем пути , ^{[CGR96] [GH05]} включая открытие алгоритма максимального потока push-relabel . ^[ГТ88] Он также работал над алгоритмической теорией игр , где он был одним из первых ученых, изучавших проектирование механизмов наихудшего случая.

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

G87.

Голдберг, Эндрю В. (1987), Эффективные графовые алгоритмы для последовательных и параллельных компьютеров (Диссертация), DSpace@MIT, hdl : 1721.1/14912 .

ГТ88.

Гольдберг, Эндрю В.; Тарьян, Роберт Э. (1988), «Новый подход к проблеме максимального потока», Journal of the ACM , 35 (4): 921–940, doi : 10.1145/48014.61051 , MR   1072405 , S2CID   52152408 .

КГР96.

Черкасский Борис Владимирович; Гольдберг, Эндрю В.; Радзик, Томаш (1996), «Алгоритмы кратчайших путей: теория и экспериментальная оценка», Математическое программирование , серия A, 73 (2): 129–174, doi : 10.1016/0025-5610(95)00021-6 , MR   1392160 .

КГ97.

Черкасский, Б.В.; Гольдберг, А.В. (1997), «О реализации метода push-relabel для задачи максимального потока», Algorithmica , 19 (4): 390–410, doi : 10.1007/PL00009180 , MR   1470042 , S2CID   10774110 .

ГР98.

Гольдберг, Эндрю В.; Рао, Сатиш (1998), «За барьером разложения потока», Журнал ACM , 45 (5): 783–797, doi : 10.1145/290179.290181 , MR   1668151 , S2CID   96030 .

GH05.

Гольдберг, Эндрю В.; Харрельсон, Крис (2005), «Вычисление кратчайшего пути: поиск A * соответствует теории графов», Труды шестнадцатого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам (SODA '05) , стр. 156–165, ISBN  9780898715859 .

Награды и почести

Голдберг является обладателем ряда наград, в том числе стипендии Герца в 1985 году, премии А.В. Такера 1988 года Общества математической оптимизации . (NSF) 1988 года Президентская премия молодого исследователя Национального научного фонда , премия молодого исследователя ONR 1991 года и INFORMS 2011 года. премия Фаркаса Общества оптимизации В 2012–2013 годах Голдберг был научным сотрудником-основателем Сколковского института науки и технологий .

Голдберг был номинирован на членство Ассоциации вычислительной техники (ACM) в 2009 году «за вклад в фундаментальные теоретические и практические проблемы разработки и анализа алгоритмов». В 2013 году он стал членом Общества промышленной и прикладной математики .