Quincy: Fair Scheduling for Distributed Computing Clusters (2010)
Michael Isard, Vijayan Prabhakaran, Jon Currey, Udi Wieder, Kunal Talwar, Andrew Goldberg
This paper addresses the problem of scheduling concurrent jobs on clusters where application data is stored on the computing nodes. This setting, in which scheduling computations close to their data...
Experimental Evaluation of Parametric Max-Flow Algorithms (2008)
Maxim Babenko, Jonathan Derryberry, Andrew Goldberg, Robert Tarjan, Yunhong Zhou
Abstract. The parametric maximum flow problem is an extension of the classical maximum flow problem in which the capacities of certain arcs are not fixed but are functions of a single parameter....
On the Weak mod m Representation of Boolean Functions (2007)
Pankaj Agarwal, Andrew Goldberg, Ketan Mulmuley, Eric Allender, Georg Gottlob, Gil Neiger, ...
one article at a time in L ATEX source form on the Internet. Pagination
Anil Kamath, A. Plotkin, Andrew Goldberg
that I have read this dissertation and that in my opinion it is fully
Andrew Goldberg, Jeffrey D. Oldham, Serge Plotkin, Cliff Stein
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 minimum cost....
– Revenue Coverage Optimization (2007)
Julie Ward, Krishna Venkatraman, Qi (annabelle Feng, Robert Tarjan, Yunhong Zhou, Jia Mao, ...
– Applied balancing method to non-parametric maximum flow problem with a general network topology. – Gave sufficient conditions for stopping.
Experimental evaluation of parametric max-flow algorithms (2007)
Maxim Babenko, Jonathan Derryberry, Andrew Goldberg, Robert Tarjan, Yunhong Zhou
Abstract. The parametric maximum flow problem is an extension of the classical maximum flow problem in which the capacities of certain arcs are not fixed but are functions of a single parameter....
TRANSIT: Ultrafast Shortest-Path Queries with Linear-Time Preprocessing (2006)
Bast, Holger, Funke, Stefan, Matijevic, Domagoj, Demetrescu, Camil, Goldberg, Andrew, Johnson, David
On Memory-Bound Functions for Fighting Spam (2003)
Cynthia Dwork, Andrew Goldberg, Moni Naor
Abstract. In 1992, Dwork and Naor proposed that e-mail messages be accompanied by easy-to-check proofs of computational effort in order to discourage junk e-mail, now known as spam. They proposed...
On Memory-Bound Functions for Fighting Spam (2003)
Cynthia Dwork, Andrew Goldberg, Moni Naor
In 1992, Dwork and Naor proposed that e-mail messages be accompanied by easy-tocheck proofs of computational effort in order to discourage junk e-mail, now known as spam.
On Memory-Bound Functions for Fighting Spam (2003)
Cynthia Dwork, Andrew Goldberg, Moni Naor
Abstract. In 1992, Dwork and Naor proposed that e-mail messages be accompanied by easy-to-check proofs of computational effort in order to discourage junk e-mail, now known as spam. They proposed...
On Memory-Bound Functions for Fighting Spam (2003)
Cynthia Dwork, Andrew Goldberg, Moni Naor
Abstract. In 1992, Dwork and Naor proposed that e-mail messages be accompanied by easy-to-check proofs of computational effort in order to discourage junk e-mail, now known as spam. They proposed...
Community Prosecution in (2001)
Barbara Boland, John Ashcroft, Barbara Boland, Andrew Goldberg
worked to expand their capacity to respond to neighborhood public safety complaints. In this respect, Washington’s community prosecution effort is similar to those in other cities initiated by...
Competitive auctions and digital goods (2001)
Andrew Goldberg, Jason Hartline, Andrew Wright, Jason D. Hartline
Abstract 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...
Competitive Auctions for Multiple Digital Goods (2001)
Andrew Goldberg, Jason, 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 Goldberg, Jason Hartline, Andrew Wright
September1999(RevisedApril2001) Abstract Westudyaclassofsingleround,sealedbidauctionsforitemsinunlimitedsupplysuchasdigitalgoods....
Competitive auctions and digital goods (2001)
Andrew Goldberg, Jason Hartline, Andrew, 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...
Shortest Path Algorithms: Engineering Aspects (2001)
We review shortest path algorithms based on the multi-level bucket data structure [6] and discuss the interplay between theory and engineering choices that leads to e#cient implementations. Our...
Andrew Goldberg, Jason Hartline, Andrew, 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 prototype implementation of archival intermemory (1999)
Yuan Chen, Jan Edler, Andrew Goldberg, Allan Gottlieb, Sumeet Sobti, Peter Yianilos
An Archival Intermemory solves the problem of highly survivable digital data storage in the spirit of the Internet. In this paper we describe a prototype implementation of Intermemory, including an...
Andrew Goldberg, Jeffrey D. Oldham, Serge Plotkin, Cliff Stein
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 minimum cost....
Implementing the Push-Relabel Method for the Maximum Flow Problem on a Connection Machine. (1997)
Alizadeh, Farid, Goldberg, Andrew
This paper describes an implementation of the Push-Relabel method for the Maximum Flow problem on a Connection Machine and gives computation times of the implementation on several classes of problems.
A Heuristic Improvement of the Bellman-Ford Algorithm, (1997)
Goldberg, Andrew, Radzik, Tomasz
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.
Scaling Algorithms for the Shortest Paths Problem, (1997)
We give an O((square root of n)m log N) algorithm for the single-source shortest paths problem with integral arc lengths. (Here n and m is the number of nodes and arcs in the input network and N is...
A Parallel Algorithm for Reconfiguring a Multibutterfly Network with Faulty Switches, (1997)
Goldberg, Andrew, Maggs, Bruce, Plotkin, Serge
This paper describes a deterministic algorithm for reconfiguring a multibutterfly network with faulty switches. Unlike previous reconfiguration algorithms, the algorithm is performed entirely by the...
Symmetric Logspace is Closed Under Complement (1995)
Noam Nisan, Abadi Greg, Frederickson John Mitchell, Pankaj Agarwal, Andrew Goldberg, Ketan Mulmuley, ...
We present a Logspace, many-one reduction from the undirected Abstract-1 st connectivity problem to its complement. This shows that SL = coSL. 1 Introduction This paper deals with the complexity...
On the Weak mod m Representation of Boolean Functions (1995)
Vince Grolmusz, Abadi Greg, Frederickson John Mitchell, Pankaj Agarwal, Andrew Goldberg, Ketan Mulmuley, ...
Let P be a polynomial over the ring of mod m integers. P weakly represents Boolean function f : f0; 1g n ! f0; 1g if there is a subset S ` f0; 1; : : : ; m \Gamma 1g such that f(x) = 0 if and only if...
Probabilistically Checkable Debate Systems and Nonapproximability of PSPACE-Hard Functions (1995)
Pankaj Agarwal, Joan Feigenbaum, Carsten Lund, And Peter W. Shor, Andrew Goldberg, Ketan Mulmuley, ...
We initiate an investigation of probabilistically checkable debate systems (PCDS), a natural generalization of probabilistically checkable proof systems (PCPS). A PCDS for a language L consists of a...
Nils Klarlund, Dexter Kozen, Pankaj Agarwal, Andrew Goldberg, Ketan Mulmuley, Eric Allender, ...
Rabin conditions are a general class of properties of infinite sequences that encompass most known automata-theoretic acceptance conditions and notions of fairness. In this paper, we introduce a...
Symmetric Logspace is Closed under Complement (1995)
Pankaj Agarwal, Andrew Goldberg, Ketan Mulmuley, Eric Allender, Georg Gottlob, Gil Neiger, ...
We present a Logspace, many-one reduction from the undirected Abstract-1 s--t connectivity problem to its complement. This shows that SL = coSL.
[ii] Chicago Journal of Theoretical Computer Science 1995-3Rabin Measures (1995)
Pankaj Agarwal, Andrew Goldberg, Ketan Mulmuley, Eric Allender, Georg Gottlob, Gil Neiger, ...
Published one article at a time in LATEX source form on the Internet. Pagination
A Parallel Algorithm for Reconfiguring a Multibutterfly Network with Faulty Switches (1994)
Andrew Goldberg, Bruce M. Maggs, Serge A. Plotkin
This paper describes a deterministic algorithm for reconfiguring a multibutterfly network with faulty switches. Unlike previous reconfiguration algorithms, the algorithm is performed entirely by the...
Topics in Analysis of Algorithms (1992)
Andrew Goldberg, Serge Plotkin
Contents 1 Preliminaries 4 1.1 The Fundamental Theorem of Linear Inequalities : : : : : : : : : : : : : : : : : : 4 1.1.1 Definitions : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :...