Skip to main content

15 Result(s)

within Andrew V. Goldberg Remove this filter Numeric Computing Remove this filter

and

  1. No Access

    Chapter and Conference Paper

    Selecting Problems for Algorithm Evaluation

    In this paper we address the issue of develo** test sets for computational evaluation of algorithms. We discuss both test families for comparing several algorithms and selecting one to use in an application,...

    Andrew V. Goldberg in Algorithm Engineering (1999)

  2. No Access

    Chapter and Conference Paper

    Truthful and Competitive Double Auctions

    In this paper we consider the problem of designing a mechanism for double auctions where bidders each bid to buy or sell one unit of a single commodity. We assume that each bidder’s utility value for the item ...

    Kaustubh Deshmukh, Andrew V. Goldberg, Jason D. Hartline… in Algorithms — ESA 2002 (2002)

  3. No Access

    Chapter and Conference Paper

    Better Landmarks Within Reach

    We present significant improvements to a practical algorithm for the point-to-point shortest path problem on road networks that combines A* search, landmark-based lower bounds, and reach-based pruning. Through re...

    Andrew V. Goldberg, Haim Kaplan, Renato F. Werneck in Experimental Algorithms (2007)

  4. No Access

    Chapter and Conference Paper

    The Partial Augment–Relabel Algorithm for the Maximum Flow Problem

    The maximum flow problem is a classical optimization problem with many applications. For a long time, HI-PR, an efficient implementation of the highest-label push-relabel algorithm, has been a benchmark due to...

    Andrew V. Goldberg in Algorithms - ESA 2008 (2008)

  5. No Access

    Book and Conference Proceedings

    Algorithmic Aspects in Information and Management

    5th International Conference, AAIM 2009, San Francisco, CA, USA, June 15-17, 2009. Proceedings

    Andrew V. Goldberg, Yunhong Zhou in Lecture Notes in Computer Science (2009)

  6. No Access

    Chapter and Conference Paper

    Two-Level Push-Relabel Algorithm for the Maximum Flow Problem

    We describe a two-level push-relabel algorithm for the maximum flow problem and compare it to the competing codes. The algorithm generalizes a practical algorithm for bipartite flows. Experiments show that the...

    Andrew V. Goldberg in Algorithmic Aspects in Information and Management (2009)

  7. No Access

    Chapter and Conference Paper

    Maximum Flows by Incremental Breadth-First Search

    Maximum flow and minimum s-t cut algorithms are used to solve several fundamental problems in computer vision. These problems have special structure, and standard techniques perform worse than the special-purpose...

    Andrew V. Goldberg, Sagi Hed, Haim Kaplan, Robert E. Tarjan… in Algorithms – ESA 2011 (2011)

  8. No Access

    Chapter and Conference Paper

    Hierarchical Hub Labelings for Shortest Paths

    We study hierarchical hub labelings for computing shortest paths. Our new theoretical insights into the structure of hierarchical labels lead to faster preprocessing algorithms, making the labeling approach pr...

    Ittai Abraham, Daniel Delling, Andrew V. Goldberg… in Algorithms – ESA 2012 (2012)

  9. No Access

    Chapter and Conference Paper

    The Hub Labeling Algorithm

    Given a weighted graph, a distance oracle takes as an input a pair of vertices and returns the distance between them. The labeling approach to distance oracle design is to precompute a label for every vertex s...

    Andrew V. Goldberg in Experimental Algorithms (2013)

  10. No Access

    Chapter and Conference Paper

    Separating Hierarchical and General Hub Labelings

    In the context of distance oracles, a labeling algorithm computes vertex labels during preprocessing. An s,t query computes the corresponding distance using the labels of s and t only, without looking at the inpu...

    Andrew V. Goldberg, Ilya Razenshteyn… in Mathematical Foundations of Computer Scien… (2013)

  11. No Access

    Chapter and Conference Paper

    Hub Label Compression

    The hub labels (HL) algorithm is the fastest known technique for computing driving times on road networks, but its practical applicability can be limited by high space requirements relative to the best competi...

    Daniel Delling, Andrew V. Goldberg, Renato F. Werneck in Experimental Algorithms (2013)

  12. No Access

    Chapter and Conference Paper

    Hub Labels: Theory and Practice

    The Hub Labeling algorithm (HL) is an exact shortest path algorithm with excellent query performance on some classes of problems. It precomputes some auxiliary information (stored as a label) for each vertex, and...

    Daniel Delling, Andrew V. Goldberg, Ruslan Savchenko… in Experimental Algorithms (2014)

  13. No Access

    Chapter and Conference Paper

    Robust Distance Queries on Massive Networks

    We present a versatile and scalable algorithm for computing exact distances on real-world networks with tens of millions of arcs in real time. Unlike existing approaches, preprocessing and queries are practica...

    Daniel Delling, Andrew V. Goldberg, Thomas Pajor… in Algorithms - ESA 2014 (2014)

  14. No Access

    Chapter and Conference Paper

    On the Complexity of Hub Labeling (Extended Abstract)

    Hub Labeling (HL) is a data structure for distance oracles. Hierarchical HL (HHL) is a special type of HL, that received a lot of attention from a practical point of view. However, theoretical questions such as N...

    Maxim Babenko, Andrew V. Goldberg… in Mathematical Foundations of Computer Scien… (2015)

  15. No Access

    Book and Conference Proceedings

    Experimental Algorithms

    15th International Symposium, SEA 2016, St. Petersburg, Russia, June 5-8, 2016, Proceedings

    Andrew V. Goldberg, Alexander S. Kulikov in Lecture Notes in Computer Science (2016)