Andrew Goldberg
PRINCIPAL RESEARCHER
.
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
Short Bio
Andrew V. Goldberg is a Senior 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, and the Mathematical Programming Society A.W. Tucker Prize.
More information, including software downloads, is available here.
News
- Data Structures and Algorithms School (а.к.а. MIDAS, Структуры Данных и Алгоритмы), August 8--14, 2010, St. Petersburg, Russia. Details comming soon.
- Our paper on highway dimension has been accepted to SODA and can be found below. This paper gives a theory to explain performance of the recent shortest path algorithms for road networks.
Publications
Below is my work published since I joined Microsoft. More can be found here.
Conference Papers
- 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
- 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
- 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
- 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 C. Harrelson, Computing the Shortest Path: A* Search Meets Graph Theory, in 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '05), Vancouver, Canada, January 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
- 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
- Maxim Babenko and Andrew V. Goldberg, Experimental Evaluation of a Parametric Flow Algorithm, no. MSR-TR-2006-77, June 2006
- 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
- 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
