Andrew V. Goldberg
Andrew Vladislav Goldberg (born 1960) is a computer scientist working primarily on design, analysis, and experimental evaluation of algorithms. He also worked on mechanism design, computer systems, and complexity theory. Until September 2014, when the laboratory closed, he was a principal researcher at Microsoft Research in Mountain View, California.
Education and career
Goldberg did his undergraduate studies at the Massachusetts Institute of Technology, graduating in 1982. After earning a masters degree at the University of California, Berkeley, he returned to MIT, finishing his doctorate there in 1987 with thesis titled Efficient graph algorithms for sequential and parallel computers and adviser Charles E. Leiserson. After completing his PhD, Goldberg was on the faculty of Stanford University and worked for NEC Research Institute and Intertrust STAR Laboratories. He joined Microsoft Research in 2002.
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[pub 1][pub 2][pub 3] and shortest path problem,[pub 4][pub 5] including the discovery of the push–relabel maximum flow algorithm.[pub 1]. He also worked on algorithmic game theory, where he was one of the first scientists to study worst-case mechanism design.
Awards and honors
Goldberg holds a number of awards, including the 1988 A.W. Tucker Prize of the Mathematical Optimization Society, 1988 NSF Presidential Young Investigator Award, 1991 ONR Young Investigator Award, and 2011 INFORMS Optimization Society Farkas Prize. In 2012–2013, Goldberg was a Founding Faculty Fellow of the Skolkovo Institute of Science and Technology.
Goldberg was elected as a fellow of the Association for Computing Machinery 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.
- 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.
- 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.
- 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.
- 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.
- 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), pp. 156–165.
- Andrew Goldberg, Microsoft Research, retrieved 2013-10-12.
- Goldberg, Andrew V. "Efficient graph algorithms for sequential and parallel computers". DSpace@MIT. Retrieved 8 January 2014.
- A.W. Tucker Prize, Mathematical Optimization Soc., retrieved 2013-10-12.
- Farkas Prize, INFORMS, retrieved 2014-1-25.
- ACM Fellow award citation, retrieved 2013-10-12.
- SIAM Fellows, retrieved 2013-10-12.