31 Result(s)
within
Chapter
Andrew V. Goldberg
-
Chapter and Conference Paper
Optimization algorithms for large networks
-
Chapter and Conference Paper
On implementing push-relabel method for the maximum flow problem
We study efficient implementations of the push-relabel method for the maximum flow problem. The resulting codes are faster than the previous codes, and much faster on some problem families. The speedup is due ...
-
Chapter and Conference Paper
Maximum skew-symmetric flows
We introduce the maximum skew-symmetric flow problem which generalizes flow and matching problems. We develop a theory of skew-symmetric flows that is parallel to the classical flow theory. We use the newly de...
-
Chapter and Conference Paper
Negative-cycle detection algorithms
We study the problem of finding a negative length cycle in a network. An algorithm for the negative cycle problem combines a shortest path algorithm and a cycle detection strategy. We study various combination...
-
Chapter and Conference Paper
Implementations of Dijkstra’s Algorithm Based on Multi-Level Buckets
A 2-level bucket data structure [6] has been shown to perform well in a Dijkstra’s algorithm implementation [4]. In this paper we study how the implementation performance depends on the number of bucket levels...
-
Chapter and Conference Paper
Recent developments in maximum flow algorithms
-
Chapter and Conference Paper
An Implementation of a Combinatorial Approximation Algorithm for Minimum-Cost Multicommodity Flow
The minimum-cost multicommodity flow problem involves si- multaneously ship** multiple commodities through a single network so that the total flow obeys arc capacity constraints and has minimum cost. Multicommo...
-
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,...
-
Chapter and Conference Paper
A Simple Shortest Path Algorithm with Linear Average Time
We present a simple shortest path algorithm. If the input lengths are positive and uniformly distributed, the algorithm runs in linear time. The worst-case running time of the algorithm is O(m + n log C), where n
-
Chapter and Conference Paper
Competitive Auctions for Multiple Digital Goods
Competitive auctions encourage consumers to bid their utility values while achieving revenue close to that of fixed pricing with perfect market analysis. These auctions were introduced in [6] in the context of se...
-
Chapter and Conference Paper
Shortest Path Algorithms: Engineering Aspects
We review shortest path algorithms based on the multi-level bucket data structure [6] and discuss the interplayb etween theorya nd engineering choices that leads to efficient implementations. Our experimental res...
-
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 ...
-
Chapter and Conference Paper
A Lower Bound on the Competitive Ratio of Truthful Auctions
We study a class of single-round, sealed-bid auctions for a set of identical items. We adopt the worst case competitive framework defined by [6,3] that compares the profit of an auction to that of an optimal s...
-
Chapter and Conference Paper
Point-to-Point Shortest Path Algorithms with Preprocessing
This is a survey of some recent results on point-to-point shortest path algorithms. This classical optimization problem received a lot of attention lately and significant progress has been made. After an overv...
-
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...
-
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...
-
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...
-
Chapter and Conference Paper
Alternative Routes in Road Networks
We study the problem of finding good alternative routes in road networks. We look for routes that are substantially different from the shortest path, have small stretch, and are locally optimal. We formally de...
-
Chapter and Conference Paper
VC-Dimension and Shortest Path Algorithms
We explore the relationship between VC-dimension and graph algorithm design. In particular, we show that set systems induced by sets of vertices on shortest paths have VC-dimension at most two. This allows us ...
-
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...
