Andrew V. Goldberg

According to our database1, Andrew V. Goldberg authored at least 125 papers between 1984 and 2017.

Collaborative distances:
  • Dijkstra number2 of three.
  • Erdős number3 of two.

Awards

ACM Fellow

ACM Fellow 2009, "For contributions to fundamental theoretical and practical problems in the design and analysis of algorithms.".

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Other 

Links

Homepages:

On csauthors.net:

Bibliography

2017
Customizable Route Planning in Road Networks.
Transportation Science, 2017

Minimum-Cost Flows in Unit-Capacity Networks.
Theory Comput. Syst., 2017

2016
Route Planning in Transportation Networks.
Proceedings of the Algorithm Engineering - Selected Results and Surveys, 2016

Implementation Challenge for Shortest Paths.
Encyclopedia of Algorithms, 2016

Hub Labeling (2-Hop Labeling).
Encyclopedia of Algorithms, 2016

Highway Dimension and Provably Efficient Shortest Path Algorithms.
J. ACM, 2016

On Dynamic Approximate Shortest Paths for Planar Graphs with Worst-Case Costs.
Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2016

2015
An exact combinatorial algorithm for minimum graph bisection.
Math. Program., 2015

Minimum Cost Flows in Graphs with Unit Capacities.
Proceedings of the 32nd International Symposium on Theoretical Aspects of Computer Science, 2015

On the Complexity of Hub Labeling (Extended Abstract).
Proceedings of the Mathematical Foundations of Computer Science 2015, 2015

Navigation made personal: inferring driving preferences from GPS traces.
Proceedings of the 23rd SIGSPATIAL International Conference on Advances in Geographic Information Systems, 2015

Faster and More Dynamic Maximum Flow by Incremental Breadth-First Search.
Proceedings of the Algorithms - ESA 2015, 2015

2014
Efficient maximum flow algorithms.
Commun. ACM, 2014

Hub Labels: Theory and Practice.
Proceedings of the Experimental Algorithms - 13th International Symposium, 2014

Robust Distance Queries on Massive Networks.
Proceedings of the Algorithms - ESA 2014, 2014

2013
Algorithm Engineering (Dagstuhl Seminar 13391).
Dagstuhl Reports, 2013

The Hub Labeling Algorithm.
Proceedings of the Experimental Algorithms, 12th International Symposium, 2013

Hub Label Compression.
Proceedings of the Experimental Algorithms, 12th International Symposium, 2013

Customizable Route Planning in Road Networks (Extended Abstract).
Proceedings of the Sixth Annual Symposium on Combinatorial Search, 2013

Separating Hierarchical and General Hub Labelings.
Proceedings of the Mathematical Foundations of Computer Science 2013, 2013

Algorithms for Hub Label Optimization.
Proceedings of the Automata, Languages, and Programming - 40th International Colloquium, 2013

Scalable similarity estimation in social networks: closeness, node labels, and random edge lengths.
Proceedings of the Conference on Online Social Networks, 2013

2012
HLDB: location-based services in databases.
Proceedings of the SIGSPATIAL 2012 International Conference on Advances in Geographic Information Systems (formerly known as GIS), 2012

Hierarchical Hub Labelings for Shortest Paths.
Proceedings of the Algorithms - ESA 2012, 2012

Exact Combinatorial Branch-and-Bound for Graph Bisection.
Proceedings of the 14th Meeting on Algorithm Engineering & Experiments, 2012

2011
Shortest Paths in Road Networks: From Practice to Theory and Back.
it - Information Technology, 2011

Customizable Route Planning.
Proceedings of the Experimental Algorithms - 10th International Symposium, 2011

A Hub-Based Labeling Algorithm for Shortest Paths in Road Networks.
Proceedings of the Experimental Algorithms - 10th International Symposium, 2011

Graph Partitioning with Natural Cuts.
Proceedings of the 25th IEEE International Symposium on Parallel and Distributed Processing, 2011

PHAST: Hardware-Accelerated Shortest Path Trees.
Proceedings of the 25th IEEE International Symposium on Parallel and Distributed Processing, 2011

VC-Dimension and Shortest Path Algorithms.
Proceedings of the Automata, Languages and Programming - 38th International Colloquium, 2011

Maximum Flows by Incremental Breadth-First Search.
Proceedings of the Algorithms - ESA 2011, 2011

Faster Batched Shortest Paths in Road Networks.
Proceedings of the ATMOS 2011, 2011

2010
Alternative Routes in Road Networks.
Proceedings of the Experimental Algorithms, 9th International Symposium, 2010

Highway Dimension, Shortest Paths, and Provably Efficient Algorithms.
Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, 2010

2009
Quincy: fair scheduling for distributed computing clusters.
Proceedings of the 22nd ACM Symposium on Operating Systems Principles 2009, 2009

An Experimental Study of Minimum Mean Cycle Algorithms.
Proceedings of the Eleventh Workshop on Algorithm Engineering and Experiments, 2009

Two-Level Push-Relabel Algorithm for the Maximum Flow Problem.
Proceedings of the Algorithmic Aspects in Information and Management, 2009

2008
Implementation Challenge for Shortest Paths.
Proceedings of the Encyclopedia of Algorithms - 2008 Edition, 2008

A Practical Shortest Path Algorithm with Linear Expected Time.
SIAM J. Comput., 2008

The Partial Augment-Relabel Algorithm for the Maximum Flow Problem.
Proceedings of the Algorithms, 2008

Shortest Path Feasibility Algorithms: An Experimental Evaluation.
Proceedings of the Tenth Workshop on Algorithm Engineering and Experiments, 2008

2007
Better Landmarks Within Reach.
Proceedings of the Experimental Algorithms, 6th International Workshop, 2007

Experimental Evaluation of Parametric Max-Flow Algorithms.
Proceedings of the Experimental Algorithms, 6th International Workshop, 2007

Point-to-Point Shortest Path Algorithms with Preprocessing.
Proceedings of the SOFSEM 2007: Theory and Practice of Computer Science, 2007

2006
Competitive auctions.
Games and Economic Behavior, 2006

Routing in Networks with Low Doubling Dimension.
Proceedings of the 26th IEEE International Conference on Distributed Computing Systems (ICDCS 2006), 2006

Reach for A*: Shortest Path Algorithms with Preprocessing.
Proceedings of the Shortest Path Problem, 2006

Reach for A*: Efficient Point-to-Point Shortest Path Algorithms.
Proceedings of the Eighth Workshop on Algorithm Engineering and Experiments, 2006

2005
Derandomization of auctions.
Proceedings of the 37th Annual ACM Symposium on Theory of Computing, 2005

Collusion-resistant mechanisms for single-parameter agents.
Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2005

Computing the shortest path: A search meets graph theory.
Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2005

Computing Point-to-Point Shortest Paths from External Memory.
Proceedings of the Seventh Workshop on Algorithm Engineering and Experiments and the Second Workshop on Analytic Algorithmics and Combinatorics, 2005

2004
Maximum skew-symmetric flows and matchings.
Math. Program., 2004

A Lower Bound on the Competitive Ratio of Truthful Auctions.
Proceedings of the STACS 2004, 2004

2003
Competitiveness via consensus.
Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2003

Envy-free auctions for digital goods.
Proceedings of the Proceedings 4th ACM Conference on Electronic Commerce (EC-2003), 2003

On Memory-Bound Functions for Fighting Spam.
Proceedings of the Advances in Cryptology, 2003

2002
Competitive generalized auctions.
Proceedings of the Proceedings on 34th Annual ACM Symposium on Theory of Computing, 2002

Truthful and Competitive Double Auctions.
Proceedings of the Algorithms, 2002

2001
Cut Tree Algorithms: An Experimental Study.
J. Algorithms, 2001

Competitive auctions and digital goods.
Proceedings of the Twelfth Annual Symposium on Discrete Algorithms, 2001

Shortest Path Algorithms: Engineering Aspects.
Proceedings of the Algorithms and Computation, 12th International Symposium, 2001

Competitive Auctions for Multiple Digital Goods.
Proceedings of the Algorithms, 2001

A Simple Shortest Path Algorithm with Linear Average Time.
Proceedings of the Algorithms, 2001

1999
Selecting Problems for Algorithm Evaluation.
Proceedings of the Algorithm Engineering, 1999

Combinatorial Algorithms Test Sets [CATS]: The ACM/EATCS Platform for Experimental Research.
Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms, 1999

Cut Tree Algorithms.
Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms, 1999

A Prototype Implementation of Archival Intermemory.
Proceedings of the Fourth ACM conference on Digital Libraries, 1999

Computational evaluation of hot queues.
Proceedings of the Data Structures, 1999

1998
Augment or Push: A Computational Study of Bipartite Matching and Unit-Capacity Flow Algorithms.
ACM Journal of Experimental Algorithmics, 1998

Recent Developments in Maximum Flow Algorithms (Invited Lecture).
Proceedings of the Algorithm Theory, 1998

An Implementation of a Combinatorial Approximation Algorithm for Minimum-Cost Multicommodity Flow.
Proceedings of the Integer Programming and Combinatorial Optimization, 1998

Towards an Archival Intermemory.
Proceedings of the IEEE Forum on Reasearch and Technology Advances in Digital Libraries, 1998

1997
Strategic directions in research in theory of computing.
SIGACT News, 1997

Global Price Updates Help.
SIAM J. Discrete Math., 1997

Scaling Methods for Finding a Maximum Free Multiflow of Minimum Cost.
Math. Oper. Res., 1997

On Implementing the Push-Relabel Method for the Maximum Flow Problem.
Algorithmica, 1997

Buckets, Heaps, Lists, and Monotone Priority Queues.
Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 1997

Experimental Study of Minimum Cut Algorithms.
Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 1997

Flows in Undirected Unit Capacity Networks.
Proceedings of the 38th Annual Symposium on Foundations of Computer Science, 1997

Beyond the Flow Decomposition Barrier.
Proceedings of the 38th Annual Symposium on Foundations of Computer Science, 1997

1996
Negative-Cycle Detection Algorithms.
Proceedings of the Algorithms, 1996

1995
An efficient cost scaling algorithm for the assignment problem.
Math. Program., 1995

On Implementing Push-Relabel Method for the Maximum Flow Problem.
Proceedings of the Integer Programming and Combinatorial Optimization, 1995

Maximum Skew-Symmetric Flows.
Proceedings of the Algorithms, 1995

1994
A Parallel Algorithm for Reconfiguring a Multibutterfly Network with Faulty Switches.
IEEE Trans. Computers, 1994

Path Problems in Skew-Symmetric Graphs.
Proceedings of the Fifth Annual ACM-SIAM Symposium on Discrete Algorithms. 23-25 January 1994, 1994

Improved Approximation Algorithms for Network Design Problems.
Proceedings of the Fifth Annual ACM-SIAM Symposium on Discrete Algorithms. 23-25 January 1994, 1994

Shortest Paths Algorithms: Theory and Experimental Evaluation.
Proceedings of the Fifth Annual ACM-SIAM Symposium on Discrete Algorithms. 23-25 January 1994, 1994

Optimization Algorithms For Large Networks.
Proceedings of the Algorithms, 1994

1993
Sublinear-Time Parallel Algorithms for Matching and Related Problems.
J. Algorithms, 1993

Approximating Matchings in Parallel.
Inf. Process. Lett., 1993

Scaling Algorithms for the Shortest Paths Problem.
Proceedings of the Fourth Annual ACM/SIGACT-SIAM Symposium on Discrete Algorithms, 1993

An efficient implementation of a scaling minimum-cost flow algorithm.
Proceedings of the 3rd Integer Programming and Combinatorial Optimization Conference, Erice, Italy, April 29, 1993

1992
Using Interior-Point Methods for Fast Parallel Algorithms for Bipartite Matching and Related Problems.
SIAM J. Comput., 1992

Finding minimum-cost flows by double scaling.
Math. Program., 1992

A Natural Randomization Strategy for Multicommodity Flow and Related Algorithms.
Inf. Process. Lett., 1992

1991
Потоковые Алгоритмы (Flow Algorithms) (G. M. Adel'son-Vel'ski, E. A. Dinits, and A. V. Karzanov).
SIAM Review, 1991

Compression and Ranking.
SIAM J. Comput., 1991

Use of dynamic trees in a network simplex algorithm for the maximum flow problem.
Math. Program., 1991

Combinatorial Algorithms for the Generalized Circulation Problem.
Math. Oper. Res., 1991

Processor-Efficient Implementation of a Maximum Flow Algorithm.
Inf. Process. Lett., 1991

Tight Bounds on the Number of Minimum-Mean Cycle Cancellations and Related Results.
Proceedings of the Second Annual ACM/SIGACT-SIAM Symposium on Discrete Algorithms, 1991

On Implementing Scaling Push-Relabel Algorithms for the Minimum-Cost Flow Problem.
Proceedings of the Network Flows And Matching, 1991

Implementing the Push-Relabel Method for the Maximum Flow Problem on a Connection Machine.
Proceedings of the Network Flows And Matching, 1991

1990
Finding Minimum-Cost Circulations by Successive Approximation.
Math. Oper. Res., 1990

1989
Finding minimum-cost circulations by canceling negative cycles.
J. ACM, 1989

A Parallel Algorithm for Finding a Blocking Flow in an Acyclic Network.
Inf. Process. Lett., 1989

Lower Bounds for Pseudorandom Number Generators
Proceedings of the 30th Annual Symposium on Foundations of Computer Science, Research Triangle Park, North Carolina, USA, 30 October, 1989

Interior-Point Methods in Parallel Computation
Proceedings of the 30th Annual Symposium on Foundations of Computer Science, Research Triangle Park, North Carolina, USA, 30 October, 1989

Network Decomposition and Locality in Distributed Computation
Proceedings of the 30th Annual Symposium on Foundations of Computer Science, Research Triangle Park, North Carolina, USA, 30 October, 1989

1988
Parallel Symmetry-Breaking in Sparse Graphs.
SIAM J. Discrete Math., 1988

A new approach to the maximum-flow problem.
J. ACM, 1988

Finding Minimum-Cost Circulations by Canceling Negative Cycles
Proceedings of the 20th Annual ACM Symposium on Theory of Computing, 1988

Sublinear-Time Parallel Algorithms for Matching and Related Problems
Proceedings of the 29th Annual Symposium on Foundations of Computer Science, 1988

Combinatorial Algorithms for the Generalized Circulation Problem
Proceedings of the 29th Annual Symposium on Foundations of Computer Science, 1988

1987
Efficient graph algorithms for sequential and parallel computers.
PhD thesis, 1987

Parallel ((Greek D)D+1)-Coloring of Constant-Degree Graphs.
Inf. Process. Lett., 1987

Solving Minimum-Cost Flow Problems by Successive Approximation
Proceedings of the 19th Annual ACM Symposium on Theory of Computing, 1987

Parallel Symmetry-Breaking in Sparse Graphs
Proceedings of the 19th Annual ACM Symposium on Theory of Computing, 1987

1986
A New Approach to the Maximum Flow Problem
Proceedings of the 18th Annual ACM Symposium on Theory of Computing, 1986

1985
Compression and Ranking
Proceedings of the 17th Annual ACM Symposium on Theory of Computing, 1985

Efficient Test Generation Algorithms.
Proceedings of the Proceedings International Test Conference 1985, 1985

1984
On Finding the Exact Solution of a Zero-One Knapsack Problem
Proceedings of the 16th Annual ACM Symposium on Theory of Computing, April 30, 1984


  Loading...