36 Result(s)

Chapter and Conference Paper

Optimization algorithms for large networks

Andrew V. Goldberg in Algorithms — ESA '94 (1994)

Article

Tight bounds on the number of minimum-mean cycle cancellations and related results

We prove a tight Θ(min(nm log(nC), nm²)) bound on the number of iterations of the minimum-mean cycle-canceling algorithm of Goldberg and Tarjan [13]. We do this by giving the lower bound and by improving the stro...

Tomasz Radzik, Andrew V. Goldberg in Algorithmica (1994)

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 ...

Boris V. Cherkassky, Andrew V. Goldberg in Integer Programming and Combinatorial Opti… (1995)

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...

Andrew V. Goldberg, Alexander V. Karzanov in Algorithms — ESA '95 (1995)

Chapter and Conference Paper

Recent developments in maximum flow algorithms

Andrew V. Goldberg in Algorithm Theory — SWAT'98 (1998)

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...

Andrew V. Goldberg, Jeffrey D. Oldham… in Integer Programming and Combinatorial Opti… (1998)

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)

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

Andrew V. Goldberg in Algorithms — ESA 2001 (2001)

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...

Andrew V. Goldberg, Jason D. Hartline in Algorithms — ESA 2001 (2001)

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...

Andrew V. Goldberg in Algorithms and Computation (2001)

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)

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...

Andrew V. Goldberg, Jason D. Hartline, Anna R. Karlin, Michael Saks in STACS 2004 (2004)

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...

Andrew V. Goldberg in SOFSEM 2007: Theory and Practice of Computer Science (2007)

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)

Reference Work Entry In depth

Implementation Challenge for Shortest Paths

Camil Demetrescu, Andrew V. Goldberg, David S. Johnson in Encyclopedia of Algorithms (2008)

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)

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)

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...

Ittai Abraham, Daniel Delling, Andrew V. Goldberg… in Experimental Algorithms (2010)

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 ...

Ittai Abraham, Daniel Delling, Amos Fiat… in Automata, Languages and Programming (2011)