Algorithmic Aspects in Information and Management
5th International Conference, AAIM 2009, San Francisco, CA, USA, June 15-17, 2009. Proceedings
Chapter and Conference Paper
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,...
Chapter and Conference Paper
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 ...
Chapter and Conference Paper
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...
Chapter and Conference Paper
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...
Book and Conference Proceedings
5th International Conference, AAIM 2009, San Francisco, CA, USA, June 15-17, 2009. Proceedings
Chapter and Conference Paper
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...
Chapter and Conference Paper
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...
Chapter and Conference Paper
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...
Chapter and Conference Paper
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...
Chapter and Conference Paper
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...
Chapter and Conference Paper
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...
Chapter and Conference Paper
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...
Chapter and Conference Paper
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...
Chapter and Conference Paper
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...
Book and Conference Proceedings
15th International Symposium, SEA 2016, St. Petersburg, Russia, June 5-8, 2016, Proceedings