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:
<last_name><at>microsoft<dot>com

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

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 an ACM Fellow.

More information, including software downloads, is available here.

News

Costomizable Route Planning algorithms (see SEA 11 paper below) is now used by Bing Maps.
2011 Farkas Prize.
Our 2011 ICALP paper gives a relationsip between shortest paths and VC-dimension.
Microsoft-Yandex class on path and flow algorithms.
A new parallel algorithm for shortest paths in road networks (PHAST) can solve problems one could not solve before; see TR below. The paper won the best paper award at IPDPS 2011.
We developed an implementation of the labeling algorithm for shortest paths in road network. This is currently the fastest algorithm for the problem. See the SEA 11 paper.

Selected Presentations

The Hub Labeling Algorithm, (given at Cornell, Harvard, MIT).
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.

Conference Papers

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
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
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
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
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
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, 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
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, Two Level Push-Relabel Algorithm for the Maximum Flow Problem, in Proc. 5th Alg. Aspects in Info. Management, Springer, 2009
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
A. V. Goldberg, The Partial Augment-Relabel Algorithm for the Maximum Flow Problem, in Proc. 16th Europ. Symp. Alg., Springer-Verlag, 2008
Andrew V. Goldberg, Haim Kaplan, and Renato F. Werneck, Better Landmarks within Reach, in Workshop on Experimental Algorithms (WEA), Rome, Italy, June 2007
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, 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
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
Ittai Abraham, Cyril Gavoille, Andrew V. Goldberg, and Dahlia Malkhi, Routing in Networks with Low Doubling Dimension, IEEE Computer Society, Los Alamitos, CA, USA, 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
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
A. V. Goldberg and J. D. Hartline, Collusion-resistant mechanisms for single-parameter agents, in Proc. 16th Symp. on Discr. Alg., 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
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

Technical Reports

Daniel Delling, Andrew V. Goldberg, Ilya Razenshteyn, and Renato F. Werneck, Graph Partitioning with Natural Cuts, no. MSR-TR-2010-164, December 2010
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, 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

Books and Portions of Books

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
C. Demetrescu, A.V. Goldberg, and D.S. Johnson, The Shortest Path Problem: Ninth DIMACS Implementation Challenge, 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

Refereed Journals and Equivalent

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