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 a Fellow of ACM and SIAM.

More information, including software downloads, is available here.

News

The HLDB paper got the best paper award (ACM SIGSPATIAL '12)
I am now a Founding Faculty Fellow at the Skolkovo Institute of Science and Technology
PC member for MFCS '13
Costomizable Route Planning algorithms (see SEA 11 paper below) is now used by Bing Maps

Selected Presentations

Highway and VC-Dimensions: from Practice to Theory and Back, updated version with new definitions and results (given at Northwestern, U. Chicago, MIT)
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.

Conference Papers

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
Daniel Delling, Andrew V. Goldberg, and Renato F. Werneck, Hub Label Compression, in Proc. 12th International Symposium on Experimental Algorithms, Springer Verlag, 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
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, 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, 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, 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
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, Ilya Razenshteyn, and Renato F. Werneck, Graph Partitioning with Natural Cuts, in 25th International Parallel and Distributed Processing Symposium (IPDPS'11), IEEE, 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, Andreas Nowatzyk, and Renato F. Werneck, PHAST: Hardware-Accelerated Shortest Path Trees, in 25th International Parallel and Distributed Processing Symposium (IPDPS'11), IEEE, 2011
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
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
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
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, 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
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
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 and Chris Harrelson, Computing the Shortest Path: A* Search Meets Graph Theory, in Proc. ACM_SIAM Symp. on Discrete Algorithms, ACM, 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

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
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

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

Refereed Journals and Equivalent

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, 2012
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