Andrew V. Goldberg's Home Page

Andrew V. Goldberg

Andrew Goldberg's research interests are in design, analysis, and computational evaluation of algorithms and data structures, computational game theory, electronic commerce, point-to-point networks, parallel and distributed algorithms, and complexity theory. His algorithms are widely used in industry and academia. Goldberg got his Ph.D. degree in Computer Science from MIT in 1987, where he was a Hertz Foundation Fellow. Before joining Microsoft Research in 2002, he worked at GTE Laboratories, Stanford University, NEC Research Institute, and InterTrust Technologies, Inc. Goldberg received a number of awards for his research contributions, including the NSF Presidential Young Investigator Award and the ONR Young Investigator Award.

Affiliation

Microsoft Research -- Silicon Valley
1065 La Avenida
Mountain View, CA 94043
USA

+1 650 693-1787 (phone)
+1 650 693-2005 (FAX)
< last name > at microsoft dot com

Current Professional Activities

Co-organizer, , Bertinoro, Italy, 2007.

Co-organizer, 9th DIMACS Implementation Challenge. .
Program committee member for CSR '07 (2nd International Computer Science Symposium in Russia).
Program committee member for WINE '07.
Program committee member for .
Program committee member for LATIN '08.
Program committee member for ANALCO '08.
Co-chair for AAIM '09.
ALENEX steering committee member.
ESA advisory committee member.

9th DIMACS Implementation Challenge - Shortest Paths

On now! Visit the Challenge home page .

Optimization Library

A library of network optimization software, including related papers and copyright information.

Publications

A list of selected publications is available in html or PDF .

The html version has links to some of the papers.

Selected Recent Papers

Routing in Networks with Low Doubling Dimension by I. Abraham, C. Gavoille, A. V. Goldberg, D. Malkhi, ICDCS '06, 2006.
This paper studies compact routing schemes for networks with low doubling dimension. Two variants are explored, name-independent routing and labelled routin. First, we provide a name-independent solution with constant stretch and polylogarithmic storage. Second, we obtain a truly scale-free solutions for three problem models: name-independent routing on graphs, labelled routing on metric spaces, and labelled routing on graphs. Third, we prove a lower bound requiring linear storage for stretch < 3 schemes.
Reach for A*: Efficient Point-to-Point Shortest Path Algorithms by A. V. Goldberg, H. Kaplan, and R. Werneck, Technical Report MSR-TR-2005-132, Microsoft Research, 2005.
(ALENEX version)
We improve Gutman's reach-based algorithm in several ways, including making it bidirectional and adding shortcut arcs to reduce vertex reaches. The resulting algorithm has reasonable preprocessing time and very fast point-to-point shortest path query time. The algorithm combines with landmark-based A* search, improving query times even more.