Andrew V. Goldberg

Andrew Goldberg
Född	Andrew Vladislav Goldberg 1960 (62–63 år)
Alma mater	Massachusetts Institute of Technology (BS, PhD) University of California, Berkeley (MS)
Utmärkelser	ACM Fellow (2009)
Vetenskaplig karriär
institutioner	Amazon Stanford University
Avhandling	Effektiva grafalgoritmer för sekventiella och parallella datorer ( 1987)
Doktorand rådgivare	Charles E. Leiserson
Doktorander	Edith Cohen
Hemsida	avglab .com /andrew

Andrew Vladislav Goldberg (född 1960) är en amerikansk datavetare som främst arbetar med design, analys och experimentell utvärdering av algoritmer. Han arbetade också med mekanismdesign, datorsystem och komplexitetsteori. För närvarande är han Senior Principal Scientist på Amazon.com .

Utbildning och karriär

Goldberg gjorde sina grundutbildningar vid Massachusetts Institute of Technology och tog examen 1982. Efter att ha tagit en magisterexamen vid University of California, Berkeley, återvände han till MIT med finansiering från ett prestigefyllt Hertz Fellowship, och avslutade sin doktorsexamen där 1987 med en avhandling på effektiva grafalgoritmer för sekventiella och parallella datorer övervakade av Charles E. Leiserson .

Karriär och forskning

Efter att ha avslutat sin doktorsexamen var Goldberg på fakulteten vid Stanford University och arbetade för NEC Research Institute, Intertrust STAR Laboratories och Microsoft Research Silicon Valley Lab. Han gick med på Amazon.com 2014.

Goldberg är mest känd för sin forskning inom design och analys av algoritmer för grafer och nätverk, och särskilt för sitt arbete med problemet med maximalt flöde och problem med kortaste vägen , inklusive upptäckten av push-relabel-algoritmen för maximalt flöde . Han arbetade också med algoritmisk spelteori, där han var en av de första forskarna som studerade design av mekanismer i värsta fall.

Utvalda publikationer

G87.

Goldberg, Andrew V. (1987), Effektiva grafalgoritmer för sekventiella och parallella datorer (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-139216 1392 MR   .

CG97.

   Cherkassky, BV; Goldberg, AV (1997), "Om implementering av push-relabel-metoden för det maximala flödesproblemet", 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) , s. 156–165, ISBN 978089871555 .

Pris och ära

Goldberg har ett antal utmärkelser, inklusive ett Hertz Fellowship 1985, 1988 AW Tucker Prize of the Mathematical Optimization Society, 1988 National Science Foundation (NSF) Presidential Young Investigator Award, 1991 ONR Young Investigator Award och 2011 INFORMS Optimization Society Farkas Prize . 2012–2013 var Goldberg en av grundarna av fakultetsstipendiaten vid Skolkovo Institute of Science and Technology .

Goldberg nominerades till Fellow i Association for Computing Machinery (ACM) 2009 "för bidrag till grundläggande teoretiska och praktiska problem i design och analys av algoritmer." 2013 blev han fellow i Society for Industrial and Applied Mathematics .