Andrew V. Goldberg

Abstract Reach for A ∗: Efficient Point-to-Point Shortest Path Algorithms (2008)

Gagan Aggarwal, Jason D. Hartline, Nicole Immorlica, Andrew V. Goldberg

We study the point-to-point shortest path problem in a setting where preprocessing is allowed. We improve the reach-based approach of Gutman [17] in several ways. In particular, we introduce a...

General Terms (2008)

We study the problem of designing seller-optimal auctions, i.e. auctions where the objective is to maximize revenue. Prior to this work, the only auctions known to be approximately optimal in the...

Point-to-Point Shortest Path Algorithms with Preprocessing (2008)

Competitive Generalized Auctions Amos Fiat (2008)

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

Jason D. Hartline, A. Alfred Taubman, Andrew V. Goldberg, Anna R. Karlin

God help us if we ever take the theater out of the auction business or anything else. It would be an awfully boring world.

Abstract Reach for A ∗: Efficient Point-to-Point Shortest Path Algorithms (2008)

Competitive Generalized Auctions Amos Fiat (2008)

We study the point-to-point shortest path problem in a setting where preprocessing is allowed. We improve the reach-based approach of Gutman [17] in several ways. In particular, we introduce a...

Jason D. Hartline, A. Alfred Taubman, Andrew V. Goldberg, Anna R. Karlin

God help us if we ever take the theater out of the auction business or anything else. It would be an awfully boring world.

Abstract (2008)

Andrew V. Goldberg, Jason D. Hartline, Michael Saks, Andrew Wright, Anna R. Karlin

We study a class of single-round, sealed-bid auctions for items in unlimited supply, such as digital goods. We introduce the notion of competitive auctions. A competitive auction is truthful (i.e.,...

General Terms (2008)

Gagan Aggarwal, Jason D. Hartline, Nicole Immorlica, Andrew V. Goldberg

We study the problem of designing seller-optimal auctions, i.e. auctions where the objective is to maximize revenue. Prior to this work, the only auctions known to be approximately optimal in the...

Abstract (2008)

Andrew V. Goldberg, Andrew Wright, Jason D. Hartline, Michael Saks, Anna R. Karlin

We study a class of single-round, sealed-bid auctions for items in unlimited supply, such as digital goods. We introduce the notion of competitive auctions. A competitive auction is truthful (i.e.,...

ABSTRACT Envy-Free Auctions for Digital Goods (2008)

We study auctions for a commodity in unlimited supply, e.g., a digital good. In particular we consider three desirable properties for auctions: • Competitive: the auction achieves a constant...

1 (2008)

Abstract Competitiveness via Consensus (2008)

1 Introduction Consider an airplane flight where passengers have individual movie screens and can choose to view one out of a dozen movies that are broadcast simultaneously. The flight is only long...

Shortest Path Feasibility Algorithms: An Experimental Evaluation (2008)

We introduce the following consensus estimate problem. Several processors hold private and possibly different lower bounds on a value. The processors do not communicate with each other, but can...

Boris V. Cherkassky, Loukas Georgiadis, Andrew V. Goldberg, Robert E. Tarjan, Renato F. Werneck

This is an experimental study of algorithms for the shortest path feasibility problem: Given a directed weighted graph, find a negative cycle or present a short proof that none exists. We study...

AND (2007)

Combinatorial Optimization (Lecture Notes) (2007)

Abstract. We study path problems in skew-symmetric graphs. These problems generalize the standard graph reachability and shortest paths problems. We develop duality theory for the skew-symmetric...

Andrew V. Goldberg, Jeffrey D. Oldham, Serge Plotkin, Cliff Stein

Contents Preface 7 Lecture I. The Stable Marriage and Stable Roommates Problems 8 1. The Stable Marriage Problem 8 1.1. Definition of the Stable Marriage Problem 8 1.2. The Gale-Shapley Algorithm 9...

2 (2007)

Abstract. The minimum-cost multicommodity flow problem involves simultaneously shipping multiple commodities through a single network so that the total flow obeys arc capacity constraints and has...

Craig Silverstein (2007)

Kaustubh Deshmukh, Andrew V. Goldberg, Jason D. Hartline, Anna R. Karlin

A 2-level bucket data structure has been shown to perform well in a Dijkstra's algorithm implementation [4, 5]. In this paper we study how the implementation performance depends on the number of...

2 (2007)

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

Competitive Generalized Auctions Amos Fiat (2007)

Andrew V. Goldberg, Jason D. Hartline, Anna R. Karlin

God help us if we ever take the theater out of the auction business or anything else. It would be an awfully boring world. | A. Alfred Taubman, Chairman, Sotheby Galleries.

3 (2007)

Andrew V. Goldberg, Jerey D. Oldham, Serge Plotkin, Cli Stein

Abstract. The minimum-cost multicommodity ow problem involves simultaneously shipping multiple commodities through a single network so that the total ow obeys arc capacity constraints and has minimum...

Submitted to Games and Economic Behavior Competitive Auctions (2007)

Andrew V. Goldberg, Jason D. Hartline, Anna R. Karlin, Andrew Wright

We study a class of single-round, sealed-bid auctions for items in unlimited supply, such as digital goods. We introduce the notion of competitive auctions. A competitive auction is truthful (i.e.,...

Reach for A ∗ : Efficient point-to-point shortest path algorithms (2006)

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

Routing in networks with low doubling dimension (2006)

We study the point-to-point shortest path problem in a setting where preprocessing is allowed. We improve the reach-based approach of Gutman [16] in several ways. In particular, we introduce a...

Ittai Abraham, Cyril Gavoille, Andrew V. Goldberg, Dahlia Malkhi

This paper studies compact routing schemes for networks with low doubling dimension. Two variants are explored, name-independent routing and labeled routing. The key results obtained for this model...

Routing in networks with low doubling dimension (2006)

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

Ittai Abraham, Cyril Gavoille, Andrew V. Goldberg, Dahlia Malkhi

This paper studies compact routing schemes for networks with low doubling dimension. Two variants are explored, name-independent routing and labeled routing. The key results obtained for this model...

Experimental evaluation of a parametric flow algorithm (2006)

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

Maxim A. Babenko, Andrew V. Goldberg

We study a practical implementation of the parametric flow algorithm of Gallo, Grigoriadis, and Tarjan. We describe an efficient implementation of the algorithm and compare it with a simpler...

Knapsack Auctions (2006)

Gagan Aggarwal, Amos Fiat, Andrew V. Goldberg, Jason D. Hartline, Nicole Immorlica, Madhu Sudan

We study the problem of designing seller optimal auctions. Prior to this work, the only previously known auctions that are approximately optimal in worst case employ randomization. Our main result is...

Finding Minimum-Cost Circulations by Successive Approximation. (2005)

We study the real algorithm for the point-to-point shortest path problem. It combines A ∗ search search, landmark-based lower bounds, and reach-based pruning. We suggest several improvements to the...

Collusion-Resistant Mechanisms for Single-Parameter Agents (2005)

We develop a new approach to solving minimum cost circulation problems. Our approach combines methods for solving the maximum flow problems with successive approximation techniques based on cost...

Collusion-Resistant Mechanisms for Single-Parameter Agents (2005)

We consider the problem of designing mechanisms with the incentive property that no coalition of agents can engage in a collusive strategy that results in an increase in the combined utility of the...

Computing the shortest path: A* search meets graph theory (2005)

We consider the problem of designing mechanisms with the incentive property that no coalition of agents can engage in a collusive strategy that results in an increase in the combined utility of the...

Andrew V. Goldberg, Chris Harrelson

We study the problem of finding a shortest path between two vertices in a directed graph. This is an important problem with many applications, including that of computing driving directions. We allow...

Microsoft (2005)

Ittai Abraham, Cyril Gavoille, Andrew V. Goldberg, Dahlia Malkhi

This paper studies compact routing schemes for networks with low doubling dimension. Two variants are explored, name-independent routing and labelled routing. The key results obtained for this model...

A Lower Bound on the Competitive Ratio of Truthful Auctions (2004)

Andrew V. Goldberg, Jason D. Hartline, Anna R. Karlin, Michael Saks

Abstract 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 [1,2] that compares the profit of an auction to...

A Lower Bound on the Competitive Ratio of Truthful Auctions (2004)

Andrew V. Goldberg, Jason D. Hartline, Anna R. Karlin, Michael Saks

Abstract 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 [1,2] that compares the profit of an auction to...

Maximum Skew-Symmetric Flows and Matchings (2004)

Computing the Shortest Path: A* Search Meets Graph Theory (2004)

The maximum integer skew-symmetric ow problem (MSFP) generalizes both the maximum ow and maximum matching problems. It was introduced by Tutte [28] in terms of self-conjugate ows in antisymmetrical...

Andrew V. Goldberg, Chris Harrelson

this paper we study one of the most common variants of the problem, where the goal is to nd a point-to-point shortest path in a directed graph. We refer to this problem as the P2P problem. We assume...

Maximum Skew-Symmetric Flows and Matchings (2003)

Goldberg, Andrew V., Karzanov, Alexander V.

The maximum integer skew-symmetric flow problem (MSFP) generalizes both the maximum flow and maximum matching problems. It was introduced by Tutte in terms of self-conjugate flows in antisymmetrical...

Envy-free auctions for digital goods (2003)

Envy-free auctions for digital goods (2003)

We study auctions for a commodity in unlimited supply, e.g., a digital good. In particular we consider three desirable properties for auctions: Competitive: the auction achieves a constant fraction...

Competitiveness via consensus (2003)

We study auctions for a commodity in unlimited supply, e.g., a digital good. In particular we consider three desirable properties for auctions: Competitive: the auction achieves a constant fraction...

Parallel (Delta + 1) Coloring of Constant-Degree Graphs, (2002)

We introduce the following consensus estimate problem. Several processors hold private and possibly different lower bounds on a value. The processors do not communicate with each other, but can...

Goldberg,Andrew V., Plotkin,Serge A.

This paper presents parallel algorithms for coloring a constant-degree graph with a maximum degree of delta in (delta + 1) colors and for finding a maximal independent set in a constant-degree graph....

Efficient Parallel Algorithms for (5+1)-Coloring and Maximal Independent Set Problems. (2002)

Goldberg,Andrew V., Plotkin,Serge A.

We described an efficient technique for breaking symmetry in parallel. The technique works especially well on rooted trees and on graphs with a small maximum degree. In particular, we can find a...

Competitive Auctions (2002)

Andrew V. Goldberg, Jason D. Hartline, Anna R. Karlin, Andrew Wright, Michael Saks

We study a class of single-round, sealed-bid auctions for items in unlimited supply, such as digital goods. We introduce the notion of competitive auctions. A competitive auction is truthful (i.e.,...

Kaustubh Deshmukh, Andrew V. Goldberg, Jason D. Hartline, Anna R. Karlin

1 Introduction Dynamic pricing mechanisms, and specifically auctions with multiple buyers and sellers, are becoming increasing popular in electronic commerce. We consider double auctions in which...

Kaustubh Deshmukh, Andrew V. Goldberg, Jason D. Hartline, Anna R. Karlin

1 Introduction Dynamic pricing mechanisms, and specifically auctions with multiple buyers and sellers, are becoming increasing popular in electronic commerce. We consider double auctions in which...

Kaustubh Deshmukh, Andrew V. Goldberg, Jason D. Hartline, Anna R. Karlin

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

Competitive Generalized Auctions (2002)

Amos Fiat, Andrew V. Goldberg, Jason D. Hartline, Anna R. Karlin, A. Alfred Taubman

We describe mechanisms for auctions that are simultaneously truthful (alternately known as strategy-proof or incentive -compatible) and guarantee high "net" profit. We make use of...

Competitiveness via Consensus (2002)

Competitiveness via Consensus (2002)

We introduce the following consensus estimate problem. Several processors hold private and possibly different lower bounds on a value. The processors do not communicate with each other, but can...

this paper we study auctions, which are an important class of mechanisms. We consider auctions for a set of identical items. We assume that each consumer has a private utility value, i.e., the...

Kaustubh Deshmukh, Andrew V. Goldberg, Jason D. Hartline, Anna R. Karlin

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

A simple shortest path algorithm with linear average time (2001)

Competitive Auctions for Multiple Digital Goods (2001)

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

Andrew Goldberg, Hartline May, Andrew V. Goldberg, Jason D. Hartline

Abstract Competitive auctions encourage consumers to bid their utility values while achieving revenueclose to that of fixed pricing with perfect market analysis. These auctions were introduced in [4]...

Competitive auctions and digital goods (2001)

Andrew V. Goldberg, Jason D. Hartline, Andrew Wright

We study a class of single round, sealed bid auctions for items in unlimited supply such as digital goods. We focus on auctions that are truthful and competitive. Truthful auctions encourage bidders...

Competitive auctions and digital goods (2001)

Andrew Goldberg, Jason Hartline, Andrew V. Goldberg, Jason D. Hartline, Andrew Wright

We study a class of single round, sealed bid auctions for items in unlimited supply such as digital goods. We focus on auctions that are truthful and competitive. Truthful auctions encourage bidders...

A Practical Shortest Path Algorithm with Linear Expected Time (2001)

A simple shortest path algorithm with linear average time (2001)

We present an improvement of the multi-level bucket shortest path algorithm of Denardo and Fox [9] and justify this improvement, both theoretically and experimentally. We prove that if the input arc...

Andrew Goldberg, Jason Hartline, Andrew V. Goldberg, Jason D. Hartline, Andrew Wright

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

Abstract (2000)

We study a class of single round, sealed bid auctions for items in unlimited supply such as digital goods. We focus on auctions that are truthful and competitive. Truthful auctions encourage bidders...

Competitive Auctions for Multiple Digital Goods (2000)

Cut Tree Algorithms (1999)

Competitive auctions encourage consumers to bid their utility values while achieving revenue close to that of xed pricing with perfect market analysis. These auctions were introduced in [6] in the...

Andrew Goldberg Nec, Andrew V. Goldberg, Kostas Tsioutsiouliklis

This is an experimental study of algorithms for the cut tree problem. We study the Gomory-Hu and Gusfield's algorithms as well as heuristics aimed to make the former algorithm faster. We develop...

Competitive Auctions and Digital Goods (1999)

Andrew V. Goldberg, Jason D. Hartline, Andrew Wright

We study a class of single round, sealed bid auctions for items in unlimited supply such as digital goods. We focus on auctions that are stable and competitive. Stable auctions encourage bidders to...

Cut Tree Algorithms (1999)

Andrew V. Goldberg, Kostas Tsioutsiouliklis

This is an experimental study of algorithms for the cut tree problem. We study the Gomory-Hu and Gusfield's algorithms as well as heuristics aimed to make the former algorithm faster. We develop...

Flows In Undirected Unit Capacity Networks (1999)

Andrew V. Goldberg, Satish Rao

.<F3.808e+05> We describe an<F3.485e+05><F3.808e+05><F3.485e+05> O(min(m, n<F2.756e+05><F2.512e+05><F2.756e+05> 3/2<F3.808e+05><F3.485e+05>...

Maximum Skew-Symmetric Flows and Their Applications to B-Matchings (1999)

Finding Minimum-Cost Circulations by Canceling Negative Cycles. (1998)

We introduce the maximum integer skew-symmetric flow problem (MSFP) which generalizes both the maximum flow and maximum matching problems. We establish analogs of the classical flow decomposition,...

Finding Minimum-Cost Circulations by Canceling Negative Cycles, (1998)

A classical algorithm for finding a minimum cost circulation consists of repeatedly finding a residual cycle of negative cost and canceling it by pushing enough flow around the cycle to saturate an...

Finding Minimum-Cost Circulations by Successive Approximation, (1998)

A classical algorithm for finding a minimum-cost circulation consists of repeatedly finding a residual cycle of negative cost and canceling it by pushing enough flow around the cycle to saturate an...

Combinatorial Algorithms for the Generalized Circulation Problem. (1998)

This document develops a new approach to solving minimum-cost circulation problems. This approach combines methods for solving the maximum flow problem with successive approximation techniques based...

Goldberg, Andrew V., Plotkin, Serge A., Tardos, Eva

We consider a generalization of the maximum network flow problem in which the amounts of flow entering and leaving an arc are linearly related. More precisely, if x(e) units of flow enter an arc e,...

Sublinear-Time Parallel Algorithms for Matching and Related Problems. (1998)

Goldberg, Andrew V., Plotkin, Serge A., Vaidya, Pravin

This paper presents the first sublinear-time deterministic parallel algorithms for bipartite matching and several related problems, including maximal node-disjoint paths, depth-first search, and...

Parallel Symmetry-Breaking in Sparse Graphs. (1998)

Goldberg, Andrew V., Plotkin, Serge A., Shannon, Gregory E.

This document describes efficient deterministic techniques for breaking symmetry in parallel. These techniques work well on rooted trees and graphs of constant degree or genus. The authors' primary...

Finding Minimum-Cost Flows by Double Scaling, (1998)

Ahuja, Ravindra K., Goldberg, Andrew V., Orlin, James B., Tarjan, Robert E.

Several researchers have recently developed new techniques that give fast algorithms for the minimum-cost flow problem. In this paper we combine several of these techniques to yield an algorithm...

Network Flow Algorithms, (1998)

Goldberg, Andrew V., Tardos, Eva, Tarjan, Robert E.

Network flow problems are central problems in operations research, computer science, and engineering and they arise in many real world applications. Starting with early work in linear programming and...

Efficiency of the Network Simplex Algorithm for the Maximum Flow Problem, (1998)

Goldberg, Andrew V., Grigoriadis, Michael D., Tarjan, Robert E.

Goldfarb and Hao have proposed a network simplex algorithm that will solve a maximum flow problem on an n-vertex, m-arc network in at most nm pivots and O(n squared m) time. In this paper we describe...

A Parallel Algorithm for Finding a Blocking Flow in an Acyclic Network, (1998)

A Natural Randomization Strategy for Multicommodity Flow and Related Algorithms, (1998)

We suppose a simple parallel algorithm for finding a blocking flow in an acyclic network. On an n-vertex, m-arc network, our algorithm runs in O(n log n) time and O(nm) space using an m-processor...

Towards an archival Intermemory (1998)

We consider the approximation algorithm of Leighton et. al. for the multicommodity flow problem. We give a more natural randomization strategy that is simpler than the one in the original algorithm...

Andrew V. Goldberg, Peter N. Yianilos

We propose a self-organizing archival Intermemory. That is, a noncommercial subscriber-provided distributed information storage service built on the existing Internet. Given an assumption of...

Augment or push: A computational study of bipartite matching and unit-capacity flow algorithms (1998)

Boris V. Cherkassky, Andrew V. Goldberg, Paul Martin, Jo~ao C. Setubal, Jorge Stolfi

This TR is a revision of the TR #97-127. The original TR was based on implementations written in different languages, different style, and using somewhat different low-level data structures. After...

Recent Developments in Maximum Flow Algorithms (1998)

Processor-Efficient Implementation of a Maximum Flow Algorithm, (1997)

Introduction The maximum flow problem is a classical optimization problem with many applications; see e.g. [1, 18, 39]. Algorithms for this problem have been studied for over four decades. Recently,...

Interior-Point Methods in Parallel Computation, (1997)

This paper describes two processor-efficient implementation of the Maximum Distance Discharge algorithm for the maximum flow problem. The maximum flow problem is a classical combinatorial...

Goldberg, Andrew V., Plotkin, Serge A., Shmoys, David B., Tardos, Eva

In this paper we use interior-point methods for linear programming, developed in the context of sequential computation, to obtain a parallel algorithm for the bipartite matching problem. Our...

Experimental Evaluation of the Push-Relabel Method for the Minimum-Cost Flow Problem (Extended Abstract), (1997)

Goldberg, Andrew V., Kharitonov, Michael

The generalized cost-scaling method is theoretically superior to other methods for solving the minimum-cost flow problem, in the sense that it leads to the best running time bounds currently known...

Experimental study of minimum cut algorithms (1997)

Chandra S. Chekuri, Andrew V. Goldberg, David R. Karger, Matthew S. Levine, Cliff Stein

Recently, several new algorithms have been developed for the minimum cut problem. These algorithms are very different from the earlier ones and from each other and substantially improve worst-case...

Augment or Push? A computational study of Bipartite Matching and Unit Capacity Flow Algorithms (1997)

Boris V. Cherkassky, Andrew V. Goldberg, Paul Martin, J.C. Setubal, Jo~ao C. Setubal, Jorge Stolfi

We conduct a computational study of unit capacity flow and bipartite matching algorithms. Our goal is to determine which variant of the push-relabel method is most efficient in practice and to...

Experimental Study of Minimum Cut Algorithms (1997)

Chandra S. Chekuri, Andrew V. Goldberg, David R. Karger, Matthew S. Levine, Cliff Stein

Recently, several new algorithms have been developed for the minimum cut problem. These algorithms are very different from the earlier ones and from each other and substantially improve the...

Computational Evaluation of Hot Queues (1997)

Andrew V. Goldberg, Craig Silverstein

The heap-on-top (hot) priority queue data structure [6] improves on the best known times for Dijkstra's shortest path algorithm. It also has very good practical performance and is robust over a...

Buckets, Heaps, Lists, and Monotone Priority Queues (1997)

Boris Cherkassky, Krasikova St, Andrew V. Goldberg

We introduce the heap-on-top (hot) priority queue data structure that combines the multi-level bucket data structure of Denardo and Fox and a heap. We use the new data structure to obtain an O(m +...

Global Price Updates Help (1997)

Andrew V. Goldberg, Robert Kennedy

. Periodic global updates of dual variables have been shown to yield a substantial speed advantage in implementations of push-relabel algorithms for the maximum flow and minimum cost flow problems....

Buckets, Heaps, Lists, and Monotone Priority Queues (1997)

Boris Cherkassky, Krasikova St, Andrew V. Goldberg

We introduce the heap-on-top (hot) priority queue data structure that combines the multi-level bucket data structure of Denardo and Fox and a heap. Our data structure improves operation bounds. We...

Flows in Undirected Unit Capacity Networks (1997)

Andrew V. Goldberg, Satish Rao

We describe an O(min(m; n 3=2 )m 1=2 )-time algorithm for finding maximum flows in undirected networks with unit capacities and no parallel edges. This improves upon the previous bound of Karzanov...

Experimental Study of Minimum Cut Algorithms (1997)

Chandra S. Chekuri, Andrew V. Goldberg, David R. Karger, Matthew S. Levine, Cliff Stein

Recently, several new algorithms have been developed for the minimum cut problem. These algorithms are very different from the earlier ones and from each other and substantially improve worst-case...

Experimental Study of Minimum Cut Algorithms (1997)

Chandra Chekuri, Andrew V. Goldberg, David R. Karger, Matthew S. Levine, Cliff Stein

Recently, several new algorithms have been developed for the minimum cut problem. These algorithms are very different from the earlier ones and from each other and substantially improve worst-case...

Length Functions for Flow Computations (1997)

Andrew V. Goldberg, Satish Rao

We introduce a new approach to the maximum flow problem. This approach is based on assigning arc lengths based on the residual flow value and the residual arc capacities. Our approach leads to an...

Heap-on-Top Priority Queues (1996)

Boris V. Cherkassky, Krasikova St, Andrew V. Goldberg

We introduce the heap-on-top (hot) priority queue data structure that combines the multi-level bucket data structure of Denardo and Fox [9] and a heap. We use the new data structure to obtain an...

Expected Performance of Dijkstra's Shortest Path Algorithm (1996)

Andrew Goldberg Nec, Andrew V. Goldberg, Robert E. Tarjan

We show that the expected number of decrease-key operations in Dijkstra's shortest path algorithm is O(n log(1 + m=n)) for an n-vertex, m-arc graph. The bound holds for any graph structure; the...

Negative-Cycle Detection Algorithms (1996)

Boris V. Cherkassky, Krasikova St, Andrew V. Goldberg

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

Expected Performance of Dijkstra's Shortest Path Algorithm (1996)

Andrew V. Goldberg, Robert E. Tarjan

We show that the expected number of decrease-key operations in Dijkstra's shortest path algorithm is O(n log(1+m=n)) for an n-vertex, m-arc graph. The bound holds for any graph structure; the...

By (1995)

Andrew V. Goldberg, Serge Plotkin

ii

Maximum Skew-Symmetric Flows (1995)

On Implementing Push-Relabel Method For The Maximum Flow Problem (1994)

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

Boris V. Cherkassky, Andrew V. Goldberg

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

Sublinear-Time Parallel Algorithms for Matching and Related Problems (1993)

Andrew V. Goldberg, Serge A. Plotkin, Pravin M., Pravin M. Vaidya

This paper presents the first sublinear-time deterministic parallel algorithms for bipartite matching and several related problems, including maximal node-disjoint paths, depth-first search, and...

Transitive Fork Environments And Minimum Cost Multiflows (1993)

An Efficient Cost Scaling Algorithm For The Assignment Problem (1993)

. The following minimum cost maximum multiflow problem is the focus of the paper: () given an undirected graph G = (V G; EG), a subset T 2 V G (of terminals), and functions c : EG ! ZZ + (of...

Andrew V. Goldberg, Robert Kennedy

. The cost scaling push-relabel method has been shown to be efficient for solving minimum-cost flow problems. In this paper we apply the method to the assignment problem. We investigate...

Shortest Paths Algorithms: Theory And Experimental Evaluation (1993)

Boris Cherkassky, Andrew V. Goldberg, Tomasz Radzik

. We conduct an extensive computational study of shortest paths algorithms, including some very recent algorithms. We also suggest new algorithms motivated by the experimental results and prove...

A Heuristic Improvement Of The Bellman-Ford Algorithm (1993)

Andrew V. Goldberg, Tomasz Radzik

. We describe a new shortest paths algorithm. Our algorithm achieves the same O(nm) worst-case time bound as Bellman-Ford algorithm but is superior in practice. 1. Introduction The Bellman-Ford...

Shortest Paths Algorithms: Theory And Experimental Evaluation (1993)

Boris V. Cherkassky, Andrew V. Goldberg, Tomasz Radzik

. We conduct an extensive computational study of shortest paths algorithms, including some very recent algorithms. We also suggest new algorithms motivated by the experimental results and prove...

An Efficient Implementation Of A Scaling Minimum-Cost Flow Algorithm (1992)

Using Interior Point Methods for Fast Parallel Algorithms for Bipartite Matching and Related Problems (1992)

. The scaling push-relabel method is an important theoretical development in the area of minimum-cost flow algorithms. We study practical implementations of this method. We are especially interested...

Andrew V. Goldberg, Serge A. Plotkin, David B. Shmoys, Éva Tardos, Eva Tardos

In this paper we use interior-point methods for linear programming, developed in the context of sequential computation, to obtain a parallel algorithm for the bipartite matching problem. Our...

Finding Minimum-Cost Flows by Double Scaling (1992)

Ravindra K. Ahuja, Ravindra K. Ahuja, Ravindra K. Ahuja, Andrew V. Goldberg, Andrew V. Goldberg, Andrew V. Goldberg, ...

Several researchers have recently developed new techniques that give fast algorithms for the minimum-cost flow problem. In this paper we combine several of these techniques to yield an algorithm...

Combinatorial Algorithms for the Generalized Circulation Problem (1991)

Andrew V. Goldberg, Serge A. Plotkin, Eva Tardos

We consider a generalization of the maximum flow problem in which the amounts of flow entering and leaving an arc are linearly related. More precisely, if x(e) units of flow enter an arc e, x(e)fl(e)...

Combinatorial Algorithms (1991)

For The Generalized, Andrew V. Goldberg, Serge A. Plotkin, Eva Tardos

We consider a generalization of the maximum flow problem in which the amounts of flow entering and leaving an arc are linearly related. More precisely, if x(e) units of flow enter an arc e, x(e)#(e)...

Network Decomposition and Locality in Distributed Computation (Extended Abstract) (1989)

Baruch Awerbuch, Andrew V. Goldberg, Michael Luby, Serge A. Plotkin

) Baruch Awerbuch Department of Mathematics and Laboratory for Computer Science M.I.T. Cambridge, MA 02139 Andrew V. Goldberg y Department of Computer Science Stanford University Stanford, CA 94305...

Network Decomposition and Locality in Distributed Computation (1989)

Baruch Awerbuch Andrew, Andrew V. Goldberg, Michael Luby, Serge A. Plotkin

We introduce a concept of network decomposition, a partitioning of an arbitrary graph into smalldiameter connected components, such that the graph created by contracting each component into a single...

A new approach to the maximum flow problem (1988)

Andrew V. Goldberg, Robert E. Tarjan

Abstract. All previously known efftcient maximum-flow algorithms work by finding augmenting paths, either one path at a time (as in the original Ford and Fulkerson algorithm) or all shortest-length...

Efficient graph algorithms for sequential and parallel computers /--by Andrew Vladislav Goldberg. (1987)

Efficient graph algorithms for sequential and parallel computers /--Andrew Vladislav Goldberg. (1987)

Supervised by Charles E. Leiserson.

Parallel Symmetry-Breaking in Sparse Graphs (1987)

Caption title.

Andrew V. Goldberg, Serge A. Plotkin, Gregory E. Shannon

We describe efficient deterministic techniques for breaking symmetry in parallel. These techniques work well on rooted trees and graphs of constant degree or genus. Our primary technique allows us to...

Contact Information RESUME (1987)