# Microsoft Research -- Silicon Valley

Address:1065 La Avenida, Mountain View, CA 94043, USA Phone/fax:+1(650) 693-1787 / +1(650) 693-2005 (recipient name required) Email:avg <

at>acm<dot>org

# Short Bio

Andrew V. Goldberg is a Principal Researcher at Microsoft Research -- Silicon Valley. His research interests include design, analysis, and experimental evaluation of algorithms, data structures, algorithm engineering, and computational game theory. Goldberg received his PhD degree in Computer Science from M.I.T. in 1987. Before joining Microsoft, he worked for Stanford University, NEC Research Institute, and InterTrust STAR Lab. His graph algorithms are taught in computer science and operations research classes and their implementations are widely used in industry and academia. Goldberg received a number of awards, including the NSF Presidential Young Investigator Award, the ONR Young Investigator Award, the Mathematical Programming Society A.W. Tucker Prize, and INFORMS Optimization Society Farkas Prize. He is a Fellow of ACM and SIAM.

More information, including software downloads, is available here.

# News

- The Silicon Valley Lab closed down; my new contact e-mail is avg <
*at>*acm<*dot*>org .

# Selected Presentations

- The Hub Labeling Algorithm, (given at Erice School on Graph Theory, Algorithms and Applications)
- Recent Results on Hub Labeling, (given at
*Microsoft Research, Columbia University, EPFL, KIT*) - The Hub Labeling Algorithm, a survey talk (given at
*SEA 2013 (plenary talk), Microsoft Research*) - Highway and VC-Dimensions: from Practice to Theory and Back, updated version with new definitions and results (given at
*Northwestern*,*U. Chicago, MIT, ADS at Bertinoro*) - The Hub Labeling Algorithm, (given at
*Cornell, Harvard, MIT, Moscow State University, 2012 SIAM Disc. Math. Conf. (plenary talk), MOPTA 2012 (plenary talk), ISMP 2012*) - Hub Labels in Databases, 2012 Workshop on Algorithms for Modern Massive Datasets
- Shortest Paths in Road Networks,
*Erice school*"Graph Algorithms, Theory, and Applications - Maximum Flows by Incremental Breadth-First Search, (given at
*Moscow State University, MSR Cambridge*) - Routing Algorithms and Related Technology, innagural lecture of the
*Open University of Skolkovo*, Polytechnical Museum, Moscow - Highway and VC-Dimensions: from Practice to Theory and Back (variants given at
*Microsoft Research -- Silicon Valley,**Daghstuhl, MIDAS Summer School, AT&T Labs, U. Karlsruhe, Tel Aviv U., Princeton U., Cornell U., Stanford U., Google*) - Highway Dimension and Provably Efficient Shortest Path Algorithms (variants given at
*Princeton U., SODA, St. Petersburg CS Club, Yandex Data Analysis School, MSR-Redmond, U. Cal. Berkeley, Qualcomm, Google, Tel Aviv University, Weitzmann Institute)*

# Publications

Below is my work published since I joined Microsoft. More can be found here.

- Daniel Delling, Andrew V. Goldberg, Ruslan Savchenko, and Renato F.Werneck, Hub Labels: Theory and Practice, in
*Proceedings of the 13th International Symposium on Experimental Algorithms (SEA'14)*, Springer, June 2014 - Andrew V. Goldberg, Ilya Razenshteyn, and Ruslan Savchenko, Separating Hierarchical and General Labelings, in
*Proc. 38th Int. Symp. on Math. Found. of CS (MFCS 2013)*, Springer Verlag, 2013 - Daniel Delling, Andrew V. Goldberg, and Renato F. Werneck, Hub Label Compression, in
*Proceedings of the 12th International Symposium on Experimental Algorithms (SEA'13)*, Springer Verlag, 2013 - Maxim Babenko, Andrew V. Goldberg, Anupam Gupta, and Viswanath Nagarajan, Algorithms for Hub Label Optimization, in
*40th International Colloquium on Automata, Languages and Programming (ICALP 2013)*, Springer Verlag, 2013 - Edith Cohen, Daniel Delling, Fabian Fuchs, Andrew V. Goldberg, Moises Goldszmidt, and Renato F. Werneck, Scalable Similarity Estimation in Social Networks: Closeness, Node Labels, and Random Edge Lengths, in
*Proceedings of the ACM Conference on Online Social Networks (COSN'13)*, ACM, 2013 - Ittai Abraham, Daniel Delling, Amos Fiat, Andrew V. Goldberg, and Renato F. Werneck, HLDB: Location-Based Services in Databases, in
*SIGSPATIAL GIS*, ACM, November 2012 - Daniel Delling, Andrew V. Goldberg, Ilya Razenshteyn, and Renato F. Werneck, Exact Combinatorial Branch-and-Bound for Graph Bisection, in
*Proceedings of the 14th Meeting on Algorithm Engineering and Experiments (ALENEX'12)*, Society for Industrial and Applied Mathematics, 2012 - Ittai Abraham, Daniel Delling, Andrew V. Goldberg, and Renato F. Werneck, Hierarchical Hub Labelings for Shortest Paths, in
*Proceedings of the 20th Annual European Symposium on Algorithms (ESA'12)*, Springer, 2012 - Daniel Delling, Andrew V. Goldberg, Thomas Pajor, and Renato F. Werneck, Customizable Route Planning, in
*Proceedings of the 10th International Symposium on Experimental Algorithms (SEA'11)*, Springer Verlag, May 2011 - Ittai Abraham, Daniel Delling, Andrew V. Goldberg, and Renato F. Werneck, A Hub-Based Labeling Algorithm for Shortest Paths on Road Networks, in
*Proceedings of the 10th International Symposium on Experimental Algorithms (SEA'11)*, Springer Verlag, May 2011 - Daniel Delling, Andrew V. Goldberg, Andreas Nowatzyk, and Renato F. Werneck, PHAST: Hardware-Accelerated Shortest Path Trees, in
*25th International Parallel and Distributed Processing Symposium (IPDPS'11)*, IEEE, 2011 - Daniel Delling, Andrew V. Goldberg, and Renato F. Werneck, Faster Batched Shortest Paths in Road Networks, in
*Proceedings of the 11th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'11)*, OpenAccess Series in Informatics, 2011 - A. V. Goldberg, S. Hed, H. Kaplan, R. E. Tarjan, and R. F. Werneck, Maximum Flows by Incremental Breadth-First Search, in
*19th European Symposium on Algorithms (ESA 2011)*, Springer Verlag, 2011 - Ittai Abraham, Daniel Delling, Amos Fiat, Andrew V. Goldberg, and Renato F. Werneck, VC-Dimension and Shortest Path Algorithms, in
*Proc. ICALP 2011*, Springer Verlag, 2011 - Daniel Delling, Andrew V. Goldberg, Ilya Razenshteyn, and Renato F. Werneck, Graph Partitioning with Natural Cuts, in
*25th International Parallel and Distributed Processing Symposium (IPDPS'11)*, IEEE, 2011 - Ittai Abraham, Daniel Delling, Andrew V. Goldberg, and Renato F. Werneck, Alternative Routes in Road Networks, in
*Proc. 9th International Symposium on Experimental Algorithms (SEA)*, Springer Verlag, 2010 - Ittai Abraham, Amos Fiat, Andrew V. Goldberg, and Renato F. Werneck, Highway Dimension, Shortest Paths, and Provably Efficient Algorithms, in
*Proc. ACM-SIAM Symposium on Discrete Algorithms (SODA10)*, Society for Industrial and Applied Mathematics, 2010 - Michael Isard, Vijayan Prabhakaran, Jon Currey, Udi Wieder, Kunal Talwar, and Andrew Goldberg, Quincy: Fair Scheduling for Distributed Computing Clusters, in
*Proceedings of 22nd ACM Symposium on Operating Systems Principles*, Association for Computing Machinery, Inc., 11 October 2009 - A.V. Goldberg, Two Level Push-Relabel Algorithm for the Maximum Flow Problem, in
*Proc. 5th Alg. Aspects in Info. Management*, Springer, 2009 - L. Georgiadis, A.V. Goldberg, R.E. Tarjan, and R.F. Werneck, An Experimental Study of Minimum Mean Cycle Algorithms, in
*Proc. 6th International Workshop on Algorithm Engineering and Experiments*, SIAM, 2009 - A. V. Goldberg, The Partial Augment-Relabel Algorithm for the Maximum Flow Problem, in
*Proc. 16th Europ. Symp. Alg.*, Springer-Verlag, 2008 - B.V. Cherkassky, L. Georgiadis, A.V. Goldberg, R.E. Tarjan, and Renato F. Werneck, Shortest Path Feasibility Algorithms: an Experimental Evaluation, in
*Proc. 6th International Workshop on Algorithm Engineering and Experiments*, SIAM, 2008 - Maxim Babenko, Jonathan Derryberry, Andrew V. Goldberg, Robert E. Tarjan, and Yunhong Zhou, Experimental Evaluation of Parametric Maximum Flow Algorihtms, in
*Workshop on Experimental Algorithms (WEA)*, Rome, Italy, June 2007 - Andrew V. Goldberg, Haim Kaplan, and Renato F. Werneck, Better Landmarks within Reach, in
*Workshop on Experimental Algorithms (WEA)*, Rome, Italy, June 2007 - Andrew V. Goldberg, Point-to-Point Shortest Path Algorithms with Preprocessing, in
*Current Trends in Theory and Practice of Computer Science (SOFSEM)*, Springer-Verlag, Harrachov, Czech Republic, January 2007 - Ittai Abraham, Cyril Gavoille, Andrew V. Goldberg, and Dahlia Malkhi, Routing in Networks with Low Doubling Dimension, in
*Intl Conference on Distributed Computer Systems (ICDCS)*, IEEE Computer Society, Los Alamitos, CA, USA, 2006 - A.V. Goldberg, Haim Kaplan, and Renato F. Werneck, Reach for A*: Efficient Point-to-Point Shortest Path Algorithms, in
*SIAM Workshop on Algorithms Engineering and Experimentation (ALENEX 06)*, Society for Industrial and Applied Mathematics, Miami, FL, January 2006 - Andrew V. Goldberg and Chris Harrelson, Computing the Shortest Path: A* Search Meets Graph Theory, in
*Proc. ACM_SIAM Symp. on Discrete Algorithms*, ACM, 2005 - G. Aggarwal, A. Fiat, A. Goldberg, J. Hartline, N. Imorlica, and M. Sudan, Derandomization of Auctions, in
*Proc. 37rd ACM Symposium on the Theory of Computing*, ACM Press, January 2005 - A. V. Goldberg and J. D. Hartline, Collusion-resistant mechanisms for single-parameter agents, in
*Proc. 16th Symp. on Discr. Alg.*, 2005 - A. V. Goldberg and R. Werneck, Computing Point-to-Point Shortest Paths from External Memory, in
*SIAM Workshop on Algorithms Engineering and Experimentation (ALENEX '05)*, Vancouver, Canada, 2005 - Andrew V. Goldberg, Jason D. Hartline, Anna R. Karlin, and Michael E. Saks, A Lower Bound on the Competitive Ratio of Truthful Auctions, in
*21st Annual Symposium on Theoretical Aspects of Computer Science (STACS 2004)*, Springer, March 2004 - Cynthia Dwork, Andrew Goldberg, and Moni Naor, On Memory-Bound Functions for Fighting Spam, in
*Proceedings of the 23rd Annual International Cryptology Conference (CRYPTO 2003)*, Springer-Verlag, Santa Barbara, CA, August 2003 - Andrew V. Goldberg and Jason D. Hartline, Envy-Free Auctions for Digital Goods, in
*ACM Conference on Electronic Commerce (EC '03)*, Association for Computing Machinery, Inc., San Diego, CA, June 2003 - Andrew V. Goldberg and Jason D. Hartline, Competitiveness via Consensus, in
*14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '03)*, ACM/SIAM, Baltimore, MD, January 2003 - K. Deshmukh, A. V. Goldberg, J. D. Hartline, and A. R. Karlin, Truthful and Competitive Double Auctions, in
*Proceedings of the 10th European Symposium on Algorithms (ESA '02)*, Springer-Verlag, September 2002 - A. Fiat, A. V. Goldberg, J. D. Hartline, and A. Karlin, Competitive Generalized Auctions, in
*Proc. 34th Symp. on Theory of Comp.*, 2002

- Daniel Delling, Andrew V. Goldberg, Thomas Pajor, and Renato F. Werneck, Robust Exact Distance Queries on Massive Networks, no. MSR-TR-2014-12, July 2014
- Hannah Bast, Daniel Delling, Andrew Goldberg, Matthias Müller-Hannemann, Thomas Pajor, Peter Sanders, Dorothea Wagner, and Renato Werneck, Route Planning in Transportation Networks, no. MSR-TR-2014-4, January 2014
- Ittai Abraham, Daniel Delling, Amos Fiat, Andrew V. Goldberg, and Renato F. Werneck, Highway Dimension and Provably Efficient Shortest Path Algorithms, no. MSR-TR-2013-91, September 2013
- Ittai Abraham, Daniel Delling, Amos Fiat, Andrew V. Goldberg, and Renato F. Werneck, HLDB: Location-Based Services in Databases, no. MSR-TR-2012-59, June 2012
- Ittai Abraham, Daniel Delling, Andrew V. Goldberg, and Renato F. Werneck, Hierarchical Hub Labelings for Shortest Paths, no. MSR-TR-2012-46, April 2012
- Ittai Abraham, Daniel Delling, Andrew V. Goldberg, and Renato F. Werneck, A Hub-Based Labeling Algorithm for Shortest Paths on Road Networks, no. MSR-TR-2010-165, December 2010
- Daniel Delling, Andrew V. Goldberg, Ilya Razenshteyn, and Renato F. Werneck, Graph Partitioning with Natural Cuts, no. MSR-TR-2010-164, December 2010
- Daniel Delling, Andrew V. Goldberg, Andreas Nowatzyk, and Renato F. Werneck, PHAST: Hardware-Accelerated Shortest Path Trees, no. MSR-TR-2010-125, September 2010
- Maxim Babenko and Andrew V. Goldberg, Experimental Evaluation of a Parametric Flow Algorithm, no. MSR-TR-2006-77, June 2006
- A. V. Goldberg and C. Harrelson, Computing the Shortest Path: A* Search Meets Graph Theory, no. MSR-TR-2004-24, July 2004
- Andrew Goldberg and Jason Hartline, Collusion-Resistant Mechanisms for Single-Parameter Agents, no. MSR-TR-2004-40, May 2004

- C. Demetrescu, A.V. Goldberg, and D.S. Johnson, The Shortest Path Problem: Ninth DIMACS Implementation Challenge, AMS, 2009
- A.V. Goldberg, H. Kaplan, and R.F. Werneck, Reach for A*: Shortest Path Algorithms with Preprocessing, in The Shortest Path Problem: Ninth DIMACS Implementation Challenge, pp. 93–140, AMS, 2009
- A. V. Goldberg and Y. Zhou, Algorithmic Aspects in Information Management, Springer, 2009
- C. Demetrescu, A. V. Goldberg, and D. S. Johnson, Implementation Challenge for Shortest Paths, in Encyclopedia of Algorithms, Springer-Verlag, 2008
- C. Demetrescu, A.V. Goldberg, and D.S. Johnson, Implementation Challenge for Shortest Paths, in Encyclopedia of Algorithms

- Ittai Abraham, Daniel Delling, Andrew V. Goldberg, and Renato F. Werneck, Alternative Routes in Road Networks, in
*ACM Journal of Experimental Algorithmics*, vol. 18, no. 1, pp. 1–17, ACM, 2013 - Daniel Delling, Andrew V. Goldberg, Andreas Nowatzyk, and Renato F. Werneck, PHAST: Hardware-accelerated shortest path trees, in
*Journal of Parallel and Distributed Computing*, Elsevier, 2013 - Andrew V. Goldberg, Highway Dimension: From Practice to Theory and Back, in
*INFORMS OS Today*, vol. 2, no. 1, pp. 12--16, INFORMS, 2012 - D. Delling, A.V. Goldberg, and R.F. Werneck, Shortest Paths in Road Networks: From Practice to Theory and Back, in
*Information Technology*, vol. 53, no. 6, pp. 294-301, 2011 - G. Aggarwal, A. Fiat, A.V. Goldberg, J.D. Hartline, N. Immorlica, and M. Sudan, Derandomization of Auctions, in
*Games and Economic Behavior*, vol. 72, no. 1, pp. 1-11, 2011 - Boris V. Cherkassky, Loukas Georgiadis, Andrew V. Goldberg, Robert E. Tarjan, and Renato F. Werneck, Shortest-Path Feasibility Algorithms: An Experimental Evaluation, in
*ACM Journal of Experimental Algorithmics*, vol. 14, no. 2, pp. 2.7:1-2.7:37, Association for Computing Machinery, Inc., 2009 - A. V. Goldberg, A Practical Shortest Path Algorithm with Linear Expected Time, in
*SIAM J. Comp.*, vol. 37, pp. 1637-1655, 2008 - Andrew V. Goldberg, Jason D. Hartline, Anna R. Karlin, Michael Saks, and Andrew Wright, Competitive Auctions, in
*Games and Economic Behavior*, vol. 55, no. 2, pp. 242–269, Elsevier, May 2006 - A. V. Goldberg and A. V. Karzanov, Maximum Skew-Symmetric Flows and Matchings, in
*Math. Programming*, vol. 100, pp. 537-568, March 2004