Jump to content

Andrew V. Goldberg

Add links
From Wikipedia, the free encyclopedia
Andrew Goldberg
Born
Andrew Vladislav Goldberg

1960 (age 65–66)
EducationMassachusetts Institute of Technology (BS, PhD)
University of California, Berkeley (MS)
Known forPush–relabel maximum flow algorithm
AwardsACM Fellow (2009)
SIAM Fellow (2013)
INFORMS Farkas Prize (2011)
ACM SIGecom Test of Time Award (2021)
Scientific career
FieldsAlgorithms, combinatorial optimization, algorithmic game theory
WorkplacesLehigh University
Amazon
Microsoft Research
Intertrust Technologies
NEC Research Institute
Stanford University
ThesisEfficient graph algorithms for sequential and parallel computers (1987)
Charles E. Leiserson[1]
Doctoral students
Edith Cohen[1]

Andrew Vladislav Goldberg (born 1960) is an American computer scientist and operations researcher. He is known for algorithms on graphs and networks, including the push–relabel maximum flow algorithm developed with Robert Tarjan, work on shortest paths and minimum-cost flow, and experimental algorithm engineering.[GT88][GT89][CGR96][2][3][4] He has also worked on mechanism design for digital-goods auctions and on scheduling in distributed computing systems.[5][IQ09]

He is a fellow of the Association for Computing Machinery and of the Society for Industrial and Applied Mathematics and received the 2011 INFORMS Optimization Society Farkas Prize.[6][7][2] Since 2025 he has been an endowed chair professor of industrial and systems engineering at Lehigh University.[8]

Education

[edit]

Goldberg received a B.S. in mathematics from the Massachusetts Institute of Technology in 1982 and an M.S. in computer science from the University of California, Berkeley in 1983.[9][8] He completed a Ph.D. in computer science at MIT in 1987, supported by a Hertz Fellowship. His dissertation, Efficient graph algorithms for sequential and parallel computers, was supervised by Charles E. Leiserson and received the 1988 A.W. Tucker Prize of the Mathematical Optimization Society.[10][G87][1][11][12]

Career

[edit]

Goldberg was an assistant professor of computer science at Stanford University from 1987 to 1995, with a courtesy appointment in operations research.[9] He then held research positions at NEC Research Institute (1995–1998), Intertrust Technologies' STAR Laboratory (1998–2001), Microsoft Research (2002–2014), and Amazon (2014–2025).[9] Later work at Microsoft and Amazon included algorithms for large road networks and transportation routing.[2][8] In July 2025 he joined Lehigh as an endowed chair professor in the Department of Industrial and Systems Engineering.[8]

Research

[edit]

Network flows

[edit]

With Tarjan, Goldberg developed the push–relabel method for the maximum flow problem.[GT88] The method is treated as a standard maximum-flow algorithm in textbooks, including Cormen, Leiserson, Rivest, and Stein's Introduction to Algorithms and Ahuja, Magnanti, and Orlin's Network Flows.[3][4] The 2011 INFORMS Optimization Society Farkas Prize citation states that this work "changed the basic paradigms in efficient flow computation, and today is taught in undergraduate and graduate courses worldwide."[2] Independent computational studies have found push–relabel implementations to be among the fastest maximum-flow codes in practice.[13]

Later work with Satish Rao improved theoretical time bounds for maximum flow; Williamson's *Network Flow Algorithms* presents the Goldberg–Rao algorithm as a standard blocking-flow method.[GR98][14][2] With Tarjan he also studied the minimum-cost flow problem, including a strongly polynomial cycle-canceling algorithm that repeatedly cancels a residual cycle of minimum mean cost.[GT89][2][14]

Shortest paths and routing

[edit]

Goldberg has worked on shortest path problems, including experimental comparisons of algorithms and combinations of A* search with graph algorithms.[CGR96][GH05][2] Later work with Ittai Abraham, Daniel Delling, and Renato F. Werneck developed hub-labeling methods for point-to-point shortest paths on road networks.[ADGW11] The Farkas citation notes subsequent shortest-path algorithms motivated by GPS-scale road networks.[2]

Algorithm engineering

[edit]

He has published on implementations of flow algorithms and on experimental algorithmics more generally.[CG97][2][13] In addition to theoretical contributions, he has worked on algorithm engineering, including experimental evaluation of graph algorithms and publicly available optimization software.[CG97][CGR96][2]

Other work

[edit]

Other work includes algorithmic game theory and mechanism design for digital-goods auctions.[5][15] While at Microsoft Research he was a coauthor of Quincy, a cluster scheduler that models locality and fairness as a min-cost flow problem.[IQ09]

Selected publications

[edit]

Awards and honors

[edit]

Goldberg received a Hertz Fellowship while a doctoral student at MIT.[12] Early awards include the 1988 A.W. Tucker Prize,[11] a 1988 NSF Presidential Young Investigator Award, and a 1991 ONR Young Investigator Award.[9][16] In 2011 he received the INFORMS Optimization Society Farkas Prize.[2] Two of his papers later received ESA Test-of-Time Awards: with Boris V. Cherkassky, "Negative-cycle detection algorithms" (ESA 1996; awarded 2016), and with Jason D. Hartline, "Competitive Auctions for Multiple Digital Goods" (ESA 2001; awarded 2021).[15]

In 2021 he also shared the ACM SIGecom Test of Time Award for the related SODA 2001 paper "Competitive Auctions and Digital Goods," with Hartline and Andrew Wright.[5] He was a founding faculty fellow of the Skolkovo Institute of Science and Technology in 2012–2013.[9]

He became 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"[6] and a fellow of the Society for Industrial and Applied Mathematics in 2013 "for fundamental contributions in the design, analysis, and implementation of algorithms for network optimization problems."[7]

References

[edit]
  1. 1 2 3 Andrew V. Goldberg at the Mathematics Genealogy Project
  2. 1 2 3 4 5 6 7 8 9 10 11 "Andrew Goldberg". INFORMS. Retrieved 2026-09-11.
  3. 1 2 Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2009). Introduction to Algorithms (3rd ed.). MIT Press. pp. 736–757. ISBN 978-0-262-03384-8.
  4. 1 2 Ahuja, Ravindra K.; Magnanti, Thomas L.; Orlin, James B. (1993). Network Flows: Theory, Algorithms, and Applications. Prentice Hall. pp. 207–249. ISBN 0-13-617549-X.
  5. 1 2 3 "Test of Time Award". ACM SIGecom. Retrieved 2026-09-11.
  6. 1 2 "Andrew V. Goldberg". Association for Computing Machinery. Retrieved 2013-10-12.
  7. 1 2 "SIAM Fellows". Society for Industrial and Applied Mathematics. Retrieved 2026-09-11.
  8. 1 2 3 4 "Lehigh ISE hires Andrew Goldberg, a leading scientist in network routing". P.C. Rossin College of Engineering and Applied Science. 2025-04-28. Retrieved 2026-09-07.
  9. 1 2 3 4 5 Andrew V. Goldberg. "Curriculum vitae" (PDF). avglab.com. Retrieved 2026-09-11 – via Wayback Machine.
  10. ↑ Goldberg, Andrew Vladislav (1987). Efficient graph algorithms for sequential and parallel computers (PhD thesis). MIT. hdl:1721.1/14912. Free access icon
  11. 1 2 "A.W. Tucker Prize". Mathematical Optimization Society. Retrieved 2013-10-12.
  12. 1 2 "Andrew Goldberg, PhD". Hertz Foundation. Retrieved 2026-09-11.
  13. 1 2 Ahuja, Ravindra K.; Kodialam, Murali; Mishra, Ajay K.; Orlin, James B. (1997). "Computational investigations of maximum-flow algorithms". European Journal of Operational Research. 97 (3): 509–542. doi:10.1016/S0377-2217(96)00269-X.
  14. 1 2 Williamson, David P. (2019). Network Flow Algorithms. Cambridge University Press. pp. 56–76, 122–128. ISBN 978-1-316-63683-1.
  15. 1 2 "Test-of-Time Award – ESA". algo-conference.org. Retrieved 2026-09-11.
  16. ↑ "Andrew V. Goldberg". P.C. Rossin College of Engineering and Applied Science. 2025-07-03. Retrieved 2026-09-11.
Retrieved from "https://en.wikipedia.org/w/index.php?title=Andrew_V._Goldberg&oldid=1374828054"