Andrew V. Goldberg

Affiliation

Microsoft Research  Silicon Valley
1065 La Avenida
Mountain View, CA 94043
USA
+1 650 6931787 (phone)
+1 650 6932005 (FAX)
< last name > at microsoft dot com
9th DIMACS Implementation Challenge  Shortest Paths

On now! Visit the Challenge
home page .
Current Professional Activities

Program committee member for EC '06.

ALENEX steering committee member.

ESA advisory committee member.
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 postscript.
 The html version has links to some of the papers.

Selected Recent Papers

Reach for A*: Efficient PointtoPoint Shortest Path Algorithms
by A. V. Goldberg, H. Kaplan, and R. Werneck,
Technical Report MSRTR2005132,
Microsoft Research, 2005.
We improve Gutman's reachbased 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
pointtopoint shortest path query time.
The algorithm combines with landmarkbased A* search, improving query times
even more.

Computing the Shortest Path: A* Search Meets Graph Theory
by A. V. Goldberg and C. Harrelson,
16th Annual ACMSIAM Symposium on Discrete Algorithms (SODA '05),
Vancouver, Canada, 2005.
Computing PointtoPoint Shortest Paths from External Memory
by A. V. Goldberg and R. Werneck,
SIAM Workshop on Algorithms Engineering and
Experimentation (ALENEX '05),
Vancouver, Canada 2005.
The above two papers introduce new pointtopoint shortest path
algorithms that use preprocessing with a limited amount of storage.
Our algorithms combine
A* search with distance bounds based on landmarks and triangle inequality.
Experiments show that this approach is very efficient on some graph
classes, including road networks.
We also describe an externalmemory implementation that can deal
with large graphs on small devices.

CollusionResistant Mechanisms for SingleParameter Agents
by A. V. Goldberg and J. D. Hartline,
16th Annual ACMSIAM Symposium on Discrete Algorithms (SODA '05),
Vancouver, Canada, 2005.
We consider the problem of designing mechanisms with the incentive
property that no coalition of agents can engage in a collusive
strategy that results in an increase in the combined utility of the
coalition, and get some positive and negative results.

Derandomization of Auctions,
by G. Aggarwal, A. Fiat, A. V. Goldberg, J. Hartline, N. Immorlica,
M. Sudan,
37th ACM Symposium on Theory of Computing (STOC '05).
The paper uses technique from compression theory do develop
develop deterministic auctions for problems where no deterministic
auctions were known previously.

Maximum SkewSymmetric Flows and Matchings
by A. V. Goldberg and A. V. Karzanov,
Math. Programming, Vol. 100, pages 537568, 2004.
The paper develops theory of and algorithms for the
skewsymmetric flow problem. Applications include the fastest
currently known algorithm for nonbipartite matching.
Resume

Available in
html
or postscript.
Research Interests
 Available in
html
or postscript.
Research Contributions
 Available in
html
or postscript.
Combinatorial Algorithms Test Sets (CATS)
(Not maintained)
CATS maximum flow page
Number of visitors since 1/1/02: