Using Sticky Bits for Wait-Free Synchronization 1 (2007)
In this paper we consider implementation of atomic wait-free objects in the context of a shared-memory multiprocessor. We introduce a new primitive object, the "Sticky-Bit", and...
School of Operations Research, (2007)
James B. Orlin, Serge A. Plotkin, Eva Tardos
We show how to use polynomial and strongly polynomial capacity scaling algorithms for the transshipment problem to design a polynomial dual network simplex pivot rule. Our best pivoting strategy...
Serge A. Plotkin, David B. Shmoys, Eva Tardos
This paper presents fast algorithms that find approximate solutions for a general class of problems, which we call fractional packing and covering problems. The only previously known algorithms for...
Parallel (Delta + 1) Coloring of Constant-Degree Graphs, (2002)
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...
Approximating the Size of a Dynamically Growing Asynchronous Distributed Network. (1998)
Awerbuch, Baruch, Plotkin, Serge A.
We show how to approximate up to a constant factor the size of a dynamically growing asynchronous distributed network. The technique presented in this paper has an amortized message complexity of...
Combinatorial Algorithms for the Generalized Circulation Problem. (1998)
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...
Graph-Theoretic Techniques for Parallel, Distributed, and Sequential Computation. (1998)
Parallel computation presents problems which are either nonexistent or trivial in the context of sequential computation. Thus, design of efficient algorithms for parallel and distributed computation...
Polynomial Dual Network Simplex Algorithms, (1998)
Orlin, James B., Plotkin, Serge A., Tardos, Eva
We show how to use polynomial and strongly polynomial capacity scaling algorithms for the transshipment problem to design a polynomial dual network simplex pivot rule. Our best pivoting strategy...
Interior-Point Methods in Parallel Computation, (1997)
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...
Approximation algorithms for Steiner and directed multicuts (1997)
Philip N. Klein, Serge A. Plotkin, Satish Rao, Eva Tardos
In this paper we consider the steiner multicut problem. This is a generalization of the minimum multicut problem where instead of separating node pairs, the goal is to find a minimum weight set of...
Approximation Algorithms for Steiner and Directed Multicuts (1997)
Philip N. Klein, Serge A. Plotkin, Satish Rao, Eva Tardos, Éva Tardosz, Steiner Multicuts
In this paper we consider the steiner multicut problem. This is a generalization of the minimum multicut problem where instead of separating node pairs, the goal is to find a minimum weight set of...
Fast Approximation Algorithms for Fractional Packing and Covering Problems (1995)
Serge A. Plotkin, David B. Shmoys, Éva Tardos, Eva Tardos
This paper presents fast algorithms that find approximate solutions for a general class of problems, which we call fractional packing and covering problems. The only previously known algorithms for...
A Sublinear Parallel Algorithm for Stable Matching (1994)
Tomás Feder, Nimrod Megiddo, Serge A. Plotkin
. Parallel algorithms for various versions of the stable matching problem are presented. The algorithms are based on the primal-dual interior pathfollowing method for linear programming. The main...
A Sublinear Parallel Algorithm for Stable Matching (1994)
Tom'as Feder Nimrod, Nimrod Megiddo, Serge A. Plotkin
this paper we consider networks made of gates of constant size. We focus of non-expansive networks (to be defined below). The problems of evaluating the gate to which a network converges, and of...
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...
Minimum-Cost Spanning Tree as a Path-Finding Problem (1994)
Bruce M. Maggs, Serge A. Plotkin
In this paper we show that minimum-cost spanning tree is a special case of the closed semiring path-finding problem. This observation gives us a non-recursive algorithm for finding minimumcost...
A Sublinear Parallel Algorithm for Stable Matching (1994)
Tom'as Feder, Nimrod Megiddo, Serge A. Plotkin
this paper we consider networks made of gates of constant size. We focus of non-expansive networks (to be defined below). The problems of evaluating the gate to which a network converges, and of...
A Sublinear Parallel Algorithm for Stable Matching (1994)
Tom'as Feder Nimrod, Tomas Feder, Nimrod Megiddo, Serge A. Plotkin
this paper we consider networks made of gates of constant size. We focus of non-expansivenetworks (to be defined below). The problems of evaluating the gate to which a network converges, and of...
A sublinear parallel algorithm for stable matching (1994)
Tomas Feder, Nimrod Megiddo, Serge A. Plotkin, Communicated F. Yao
A parallel algorithm for the stable matching problem is presented. The algorithm is based on the primal-dual interior path-following method for linear programming. The main result is that a stable...
ARTICLE NO. AL960833 Approximation Algorithms for Steiner and Directed (1994)
Philip N. Klein, Serge A. Plotkin, Satish Rao, Eva Tardos
In this paper we consider the Steiner multicut problem. This is a generalization of the minimum multicut problem where instead of separating node pairs, the goal is to find a minimum weight set of...
Bounds on the Max-Flow Min-Cut Ratio for Directed Multicommodity Flows (1993)
Philip N. Klein, Serge A. Plotkin, Satish Rao, Éva Tardos, Eva Tardos, Eva Tardos
The most well-known theorem in combinatorial optimization is the classical max-flow min-cut theorem of Ford and Fulkerson. This theorem serves as the basis for deriving efficient algorithms for...
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...
Excluded Minors, Network Decomposition, and Multicommodity Flow (1993)
Philip Klein, Serge A. Plotkin, Satish Rao
In this paper we show that, given a graph and parameters ffi and r, we can find either a Kr;r minor or an edge-cut of size O(mr=ffi) whose removal yields components of weak diameter O(r 2 ffi); i.e.,...
Using separation algorithms in fixed dimension (1992)
Carolyn Haibt Norton, Serge A. Plotkin, Eva Tardos
Consider a convex set in d dimensions. Assume that we are given a separation subroutine which, given a point, tells us whether this point is in the set. Moreover, if the point is not in the set, the...
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...
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...
Cover title.
Supervised by Charles E. Leiserson.
Parallel Symmetry-Breaking in Sparse Graphs (1987)
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...