Andrew V. Goldberg

Andrew Goldberg
Born	Andrew Vladislav Goldberg 1960 (age 65–66)
Alma mater	Massachusetts Institute of Technology (BS, PhD) University of California, Berkeley (MS)
Scientific career
Workplaces	Amazon Stanford University
Thesis	Efficient graph algorithms for sequential and parallel computers (1987)
Doctoral advisor	Charles E. Leiserson
Doctoral students	Edith Cohen
Website	avglab.com/andrew

Andrew Vladislav Goldberg (born 1960) is an American computer scientist working primarily on design, analysis, and experimental evaluation of algorithms. He also worked on mechanism design, computer systems, and complexity theory. Currently he is a senior principal scientist at Amazon.com.

Education and career

Goldberg did his undergraduate studies at the Massachusetts Institute of Technology, graduating in 1982. After earning a master's degree at the University of California, Berkeley, he returned to MIT with funding from a prestigious Hertz Fellowship, finishing his doctorate there in 1987 with a thesis on the Efficient graph algorithms for sequential and parallel computers supervised by Charles E. Leiserson.^[G87]

Career and research

After completing his PhD, Goldberg was on the faculty of Stanford University (1987–1995) and worked for NEC Research Institute (1995–1998, Senior Research Scientist), Intertrust STAR Laboratories (1998–2001, Research Fellow), and Microsoft Research Silicon Valley Lab (2002–2014, Principal Researcher). He joined Amazon.com in 2014 as Senior Principal Research Scientist.

Goldberg is best known for his research in the design and analysis of algorithms for graphs and networks, and particularly for his work on the maximum flow problem^{[GT88][CG97][GR98]} and shortest path problem,^{[CGR96][GH05]} including the discovery of the push–relabel maximum flow algorithm.^[GT88] He also worked on algorithmic game theory, where he was one of the first scientists to study worst-case mechanism design.

Selected publications

G87.

Goldberg, Andrew V. (1987), Efficient graph algorithms for sequential and parallel computers (Thesis), DSpace@MIT, hdl:1721.1/14912.

GT88.

Goldberg, Andrew V.; Tarjan, Robert E. (1988), "A new approach to the maximum-flow problem", Journal of the ACM, 35 (4): 921–940, doi:10.1145/48014.61051, MR 1072405, S2CID 52152408.

CGR96.

Cherkassky, Boris V.; Goldberg, Andrew V.; Radzik, Tomasz (1996), "Shortest paths algorithms: theory and experimental evaluation", Mathematical Programming, Series A, 73 (2): 129–174, doi:10.1016/0025-5610(95)00021-6, MR 1392160.

CG97.

Cherkassky, B. V.; Goldberg, A. V. (1997), "On implementing the push-relabel method for the maximum flow problem", Algorithmica, 19 (4): 390–410, doi:10.1007/PL00009180, MR 1470042, S2CID 10774110.

GR98.

Goldberg, Andrew V.; Rao, Satish (1998), "Beyond the flow decomposition barrier", Journal of the ACM, 45 (5): 783–797, doi:10.1145/290179.290181, MR 1668151, S2CID 96030.

GH05.

Goldberg, Andrew V.; Harrelson, Chris (2005), "Computing the shortest path: A* search meets graph theory", Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '05), Society for Industrial and Applied Mathematics, pp. 156–165, ISBN 9780898715859.

Awards and honors

Goldberg holds a number of awards, including a Hertz Fellowship in 1985. Early in his career, he was awarded the 1988 National Science Foundation (NSF) Presidential Young Investigator Award and the 1991 ONR Young Investigator Award. He received the 1988 A.W. Tucker Prize of the Mathematical Optimization Society, 1988 National Science Foundation (NSF) Presidential Young Investigator Award, 1991 ONR Young Investigator Award, and 2011 INFORMS Optimization Society Farkas Prize. Two of his papers received test-of-time awards (2001 and 2016) from the European Symposium on Algorithms. In 2012–2013, Goldberg was a Founding Faculty Fellow of the Skolkovo Institute of Science and Technology.

Goldberg was nominated a Fellow of the Association for Computing Machinery (ACM) in 2009 "for contributions to fundamental theoretical and practical problems in the design and analysis of algorithms." In 2013, he became a fellow of the Society for Industrial and Applied Mathematics.

His work on graph algorithms, including max-flow and shortest path problems, is covered in network algorithms textbooks and taught in operations research courses at undergraduate and graduate levels.