\documentstyle{dimacs} \setlength{\topmargin}{.25in} \setlength{\headheight}{0in} % height of the head \setlength{\headsep}{0in} % head to the top of the body \setlength{\textheight}{9.00in} % height of the body \setlength{\oddsidemargin}{0mm} % left edge of paper to body (less one inch) \setlength{\evensidemargin}{0mm} % ditto, even pages \setlength{\textwidth}{6.5in} % width of body \setlength{\topskip}{0in} % top of body to bottom of first line of text %\setlength{\footheight}{0.25in} % height of footer %\setlength{\footskip}{0.50in} % bottom of text to bottom of foot \begin{document} \pagestyle{empty} \begin{center} {\Large \bf DIMACS TECHNICAL REPORT 93-90}\\ \vspace{.3in} {\large \bf December, 1993} \vspace{1in} {\large \bf Workshop on\\ Parallel Algorithms: From Solving Combinatorial Problems to\\ Solving Grand Challenge Problems\\ November 17-19, 1993\\} \vspace{1in} Organizers:\\ \vspace{.3in} James Flanagan (CAIP-Rutgers)\\ Yossi Matias (AT\&T Bell Laboratories)\footnote{DIMACS permanent member\\ DIMACS is a cooperative project of Rutgers University, Princeton University, AT\&T Bell Laboratories and Bellcore.\\ DIMACS is an NSF Science and Technology Center, funded under contract STC-91-19999; and also receives support from the New Jersey Commission on Science and Technology.}\\ Vijaya Ramachandran (U. Texas at Austin)\\ \end{center} \newpage \begin{center} {\large \bf ABSTRACT} \end{center} In the context of the 1993-94 DIMACS Special Year on Massively Parallel Computation, a three-day workshop entitled ``Parallel Algorithms: From Solving Combinatorial Problems to Solving Grand Challenge Problems'' was held on November 17-19, 1994. The workshop focused on the general area of parallel algorithms. The scope included the study of basic problems in parallel computation on the one hand, and the relevance of parallel computation to various applications, including the so-called Grand Challenge Problems, on the other hand.\\ The workshop featured 38 speakers, which presented invited presentations, as well as contributed talks.\\ The workshop took place at the DIMACS Center on the Rutgers University campus in Piscataway, New Jersey. DIMACS is the National Science Foundation Science and Technology Center for Discrete Mathematics and Theoretical Computer Science. Co-organizers for this workshop were:\\ \hspace{1.5in} James Flanagan (CAIP-Rutgers) \hspace{1.5in} Yossi Matias (AT\&T Bell Laboratories) \hspace{1.5in} Vijaya Ramachandran (U. Texas at Austin)\\ This report contains the set of abstracts for the talks presented, and serves as the workshop proceedings.\\ This workshop is part of the DIMACS Special Year in Massively Parallel Computation, which receives significant support from the New Jersey Commission on Science and Technology as part of its commitment to promote excellence in High Performance Computing and Communication in the State of New Jersey.\\ \newpage \pagestyle{plain} \pagenumbering{roman} \begin{center} {\Large \bf Workshop Program}\end{center} {\large \bf Wednesday, November 17, 1993} \begin{tabular}{rl} \multicolumn {1} {l} {} & \multicolumn {1} {l} {}\\ 8:00 & Breakfast\\ 9:20 & Diane Souvaine, DIMACS \& Rutgers\\ & \em{Welcoming remarks from DIMACS}\\ 9:30 & Gary Miller, Carnegie-Mellon\\ & \em{Numeric and Combinatorial Aspects to Parallel Scientific Computation}\\ \medskip 10:00 & Break\\ 10:30 & Richard Cole, NYU\\ & \em{2-D Pattern Matching}\\ 11:00 & Uzi Vishkin, Maryland \& Tel Aviv\\ & \em{Efficient Labeling of Substrings}\\ 11:30 & Pierre Kelsen, U. British Columbia\\ & \em{Constant Time Parallel Indexing of Points in a Triangle}\\ 12:00 & Pangfeng Liu, DIMACS\\ & \em{Experiences with Parallel N-body Simulations}\\ \medskip 12:30 & Lunch\\ 2:00 & Victor Pan, CUNY\\ & \em{Efficient Parallel computations in Linear Algebra with Applications}\\ 2:30 & Roland Wunderling, Berlin\\ & \em{On the Impact of Communication Latencies on Distributed Sparse LU}\\ & {\em Factorization}\\ 2:50 & Ian Parberry, North Texas U.\\ & \em{Algorithms for Touring Knights}\\ \medskip 3:20 & Break\\ 3:50 & Phil Klein, Brown\\ & \em{A Linear-Processor Polylog-Time Parallel Algorithm for Shortest}\\ & {\em Paths in Planar Graphs}\\ 4:20 & Edith Cohen, AT\&T Bell Laboratories\\ & \em{Polylog-Time and Near-Linear Work Approximation Scheme for}\\ & {\em Undirected Shortest Paths}\\ 4:50 & Lin Chen, USC\\ & \em{Graph Isomorphism and Identification Matrices: Parallel Algorithms}\\ 5:30 & Wine and Cheese Reception \end{tabular} \newpage {\large \bf Thursday, November 18, 1993} \begin{tabular}{rl} \multicolumn {1} {l} {} & \multicolumn {1} {l} {}\\ 8:00 & Breakfast\\ 8:50 & John Board, Duke\\ & \em{Algorithms for Multipole-Accelerated Force Calculation in Molecular Dynamics}\\ 9:30 & Vijaya Ramachandran, U. Texas at Austin\\ & \em{Parallel Graph Algorithms: Theory and Implementation}\\ \medskip 10:00 & Break\\ 10:30 & Zvi Kedem, NYU\\ & \em{Towards High-Performance Fault-Tolerant Distributed Processing}\\ 11:00 & Torben Hagerup, Max Planck Institute\\ & \em{Fast Deterministic Compaction and its Applications}\\ 11:30 & Phil Gibbons, AT\&T Bell Laboratories\\ & \em{Efficient Low Contention Parallel Algorithms}\\ 12:00 & Paul Spirakis, Patras\\ & \em{Paradigms for Fast Parallel Approximations for Problems that are Hard to}\\ & {\em Parallelize}\\ \medskip 12:30 & Lunch\\ 2:00 & Olof Widlund, NYU\\ & \em{Some Recent Results on Schwarz Type Domain Decomposition Algorithms}\\ 2:40 & Jan Prins, U. North Carolina at CH\\ & \em{The Proteus System for the Development of Parallel Algorithms}\\ 3:10 & Yuefan Deng, SUNY at Stony Brook\\ & \em{Analysis and Prediction on Parallel Processors of Protein Binding on DNA:}\\ & \em{Pattern Recognition of Hydrogen Bonds}\\ \medskip 3:40 & Break\\ 4:10 & Rajeev Raman, Maryland\\ & \em{Optimal Randomized Parallel Algorithms for Computing the Row Maxima of a}\\ & \em{Totally Monotone Matrix}\\ 4:40 & Teresa Przytycka, Odense\\ & \em{Trade-offs in Parallel Computation of Huffman Tree and Concave Least}\\ & \em{ Weight Subsequence}\\ 5:10 & Vijay Vazirani, IIT Delhi \& DIMACS\\ & \em{A Primal-dual RNC Approximation Algorithm for (multi)-Set (multi)-Cover}\\ & \em{and Covering Integer Programs}\\ 5:40 & Wine and Cheese Reception \end{tabular} \newpage {\large \bf Friday, November 19, 1993} \begin{tabular}{rl} \multicolumn {1} {l} {} & \multicolumn {1} {l} {}\\ 8:00 & Breakfast\\ 8:50 & Mike Goodrich, Johns Hopkins\\ & \em{Parallel Methods for Computational Geometry}\\ 9:20 & Yossi Matias, AT\&T Bell Laboratories\\ & \em{Highly Parallel Randomized Algorithms - Some Recent Results}\\ 9:50 & Dina Kravets, NJIT\\ & \em{Optimal Hypercube Algorithm for the All-Nearest Smaller Values Problem}\\ \medskip 10:10 & Break\\ 10:40 & Mike Atallah, Purdue\\ & \em{Optimal Parallel Hypercube Algorithms for Polygon Problems}\\ 11:10 & Ernst Mayr, Munich\\ & \em{Optimal Tree Contraction on the Hypercube and Related Network}\\ 11:40 & David Haglin, Mankato State U.\\ & \em{Evaluating Parallel Approximation Algorithms}\\ 12:00 & Jesper Traff, Copenhagen\\ & \em{A Distributed Implementation of an Algorithm for the Maximum Flow Problem}\\ \medskip 12:20 & Lunch\\ 1:50 & Joseph J\'{a}J\'{a}, Maryland\\ & \em{Efficient Parallel Algorithms for Image Processing}\\ 2:20 & Rainer Feldmann, Paderborn\\ & \em{Game Tree Search on Massively Parallel Systems}\\ 2:50 & Stefan Tschoke, Paderborn\\ & \em{Efficient Parallelization of a Branch \& Bound Algorithm}\\ & \em{for the Symmetric Traveling Salesman Problem}\\ 3:10 & Erik Tarnvik, Umea, Sweden\\ & \em{Solving the 0-1 Knapsack Problem on a Distributed Memory Multicomputer}\\ \medskip 3:30 & Break\\ 4:00 & Aravind Srinivasan, Institute for Advanced Study \& DIMACS\\ & \em{Improved Parallel Algorithms via Approximating Probability Distributions}\\ 4:30 & Per Laursen, Copenhagen\\ & \em{Parallel Simulated Annealing Using Selection and Migration --}\\ & \em{an Approach Inspired by Genetic Algorithms}\\ 4:50 & Zvi Galil, Columbia U. \& Tel Aviv\\ & \em{From the CRCW-PRAM to the HCUBE via the CREW-PRAM and the}\\ & \em{EREW-PRAM or In the Defense of the PRAM}\\ 5:20 & Workshop ends\\ \end{tabular} \newpage \pagenumbering{arabic} \begin{center} {\Large \bf Numeric and Combinatorial Aspects to Parallel\\ Scientific Computation} \vspace{.3in} Gary L Miller\\ CMU\\ \tt{glmiller@cs.cmu.edu} \end{center} The simulation of 3-dimensional problems comprise many of the ``grand challenge problems''. Problems on the list include climate forecasting and turbulence. These problems require computer simulation of problems over highly unstructured domains. The size of a regular mesh may be exponentially larger than the corresponding quality unstructured mesh for the same problem. For the last several years we have been developing algorithms which will assist researchers in making these simulations on the next generation of parallel machines. In particular, we have made progress on three major aspects of the problem: formulatization/meshing, partitioning, and solving. We have shown that $d$-dimensional meshes and their corresponding combinatorial-graphs of size n that arise from the finite element method can be partitioned into two roughly equal size pieces with a boundary of size at most $O(n^{(d-1)/d})$. These results have at least four application in scientific computation: (1) for efficient direct methods to solve the associated linear system. (2) for the placement of these systems on machines with sublinear bisection width such as fat-tree or mesh-connected machines. (3) for the design and construction of meshes. (4) for the construction of preconditioners which are used in iterative system solvers. The running time of the geometric separator algorithm has been greatly improved by the use of Second Moments. We will discuss our new analysis of the moment method. It seems that one of the main stumbling blocks to complete automation of finite element method is mesh generation in 3-dimensions. We have been experimenting with an unstructured finite difference like method. We have been using variation of a method called Poisson Darts. This is a randomized method for placing points down in a domain which has previously been used in numeric integration and ray-tracing algorithms. The advantage with this unstructured finite difference method is that we do not need to generate unstructured meshes as used in the finite element method. We will show some numbers from preliminary experimentations with this method. They indicate that this method is competitive with finite element. Our methods should lend itself to problems which need a moving or changing mesh. We have also begun analyzing and experimenting with a combinatorial approach to finding preconditioner to improve convergence rates for iterative linear system solvers. In particular we have been considering weighted trees as preconditioners. We are using the separator structure to guide the construction. Joint work with Stan Eisenstat, Steve Guattery, Keith Gremban, Dafna Talmor, Shang-Hua Teng, Bill Thurston, and Steven Vavasis. \newpage \begin{center} {\Large \bf 2-D Pattern Matching} \vspace{.3in} Richard Cole\\ New York University\\ \tt{cole@cs.nyu.edu} \end{center} The input for the 2-D pattern matching problem comprises a preprocessed square text of size $n$ x $n$ and a square pattern of size $m$ x $m$, both drawn over the same alphabet $\Sigma$. The problem is to find every occurrence of the pattern in the text. In this talk a linear work constant time PRAM algorithm is described. Algorithms for the preprocessing of the text are also outlined; the latter also perform linear work but run in $\Theta(\log \log m)$ time, which is the best possible. Joint work with Crochemore, Galil, Gasieniec, Hariharan, Muthukrishnan, Park, Rytter. \newpage \begin{center} {\Large \bf Efficient labeling of substrings} \vspace{.3in} Uzi Vishkin\\ University of Maryland \& Tel Aviv University\\ \tt{vishkin@umiacs.umd.edu} \end{center} Suffix trees are the main data-structure in string matching algorithmics. There are several serial algorithms for suffix tree construction which run in linear time, but the number of operations in the only parallel algorithm available, due to Apostolico, Iliopoulos, Landau, Schieber and Vishkin, is proportional to $n$ log $n$. The algorithm is based on labeling substrings, similar to a classical serial algorithm, with the same operations bound, by Karp, Miller and Rosenberg. We show how to break symmetries that occur in the process of assigning labels using the Deterministic Coin Tossing (DCT) technique, by Cole and Vishkin, and thereby reduce the number of labeled substrings to linear. Joint work with Suleyman Cenk Sahinalp. \newpage \begin{center} {\Large \bf Constant Time Parallel Indexing of Points in a Triangle} \vspace{.3in} Pierre Kelsen\\ University of British Columbia\\ \tt{kelsen@cs.ubc.ca} \end{center} Consider a triangle whose three vertices are points on the unit grid. Let $k$ denote the number of grid points in the triangle. We describe an \emph{indexing} of the triangle: a bijective mapping from \{0,...,$k-1$\} to the grid points in the triangle. Computing such a mapping is a fundamental subroutine in fine-grained parallel computation arising in graphics applications such as ray-tracing. We describe a very fast indexing algorithm: after a preprocessing phase requiring time proportional to the number of bits in the vertices of the triangle, a grid point in the triangle can be computed in constant time from its index. The method requires only constant space. Joint work with Simon Kahan. \newpage \begin{center} {\Large \bf Experiences with Parallel N-body simulations}\footnote[1]{The work was supported by Thinking Machines Corporation, and grants from ONR, DARPA and NSF.} \vspace{.3in} Pangfeng Liu\\ DIMACS\\ \tt{pangfeng@bellcore.com} \end{center} N-body simulations are used to study a variety of physical phenomena, the evolution of galaxies for example. While these methods appear to be ``embarrassingly parallel,'' large scale simulations involve irregular and adaptive structures which have been considered inconvenient to implement efficiently. This talk will describe our ongoing experience on the TMC CM-5 with astrophysical simulations involving millions of bodies. We will describe our programming abstractions, experimental results, and techniques for implementing parallel dynamic adaptive computations. The talk will be self-contained. Joint work with Sandeep Bhatt (Bellcore). \newpage \begin{center} {\Large \bf Efficient Parallel computations in Linear Algebra with Applications} \vspace{.3in} Victor Pan\\ City University of New York\\ \tt{vpan@lcvax.lehman.cuny.edu} \end{center} We review some recent progress in designing parallel algorithms for linear algebra computations, focusing on processor efficiency of fast algorithms. Besides the major topic of solving linear systems of equations, computing matrix inverse and determinant, we consider computation of matrix rank and maximal linearly independent subset of a vector set, which has many applications to combinatorial computations. \newpage \begin{center} {\Large \bf On the Impact of Communication Latencies on Distributed Sparse LU Factorization} \vspace{.3in} Roland Wunderling\\ Konrad Zuse-Zentrum fuer Informationstechnik Berlin\\ \tt{wunderling@sc.zib-berlin.de} \end{center} Solving sparse linear systems Ax=b is a task of pivotal importance, not only in linear programming. In state of the art simplex codes, this task is solved by computing the factorization A=LU, where L and U are lower and upper triangular matrices respectively, and then solving the systems Ly=b and Ux=y by forward and backward substitution. This talk will deal with parallelizing the factorization part. This has been done efficiently on a network of transputers. However, most current commercially available parallel computers have a ratio of communication latency to time per floating point operation magnitudes larger then 1, making such an algorithm merly impossible. In this talk, I will show, how the problem of high latencies may be attacked by latency hiding through asynchronous communication, and latency minimizing through exploiting parallelism only at a coarser granularity and message fusion. The talk will be divided into 5 parts. The first part will briefly sketch our sequential algorithm. In the second part, parallelization opportunities will be shown and a brief survey on their exploitation will be given. After that, our parallel factorization algorithm will be described, with special emphasis on the design decisions due to communication latencies. These include, among others, data distribution and load balancing. Part four is devoted to a performance model for the algorithm, which is used to explicitly show the impact of latencies. In section five, our experimental results on an iPSC/860 are reported. Some conclusions will end the talk. \newpage \begin{center} {\Large \bf Algorithms for Touring Knights} \vspace{.3in} Ian Parberry\footnote[1]{Research supported by the National Science Foundation under grant number CCR-9302917, and by the Air Force Office of Scientific Research, Air Force Systems Command, USAF, under grant number F49620-93-1-0100.}\\ Department of Computer Sciences\\ University of North Texas\\ P.O. Box 13886\\ Denton, TX 76203-3886\\ \tt{ian@ponder.csci.unt.edu} \end{center} The effectiveness and efficiency of three algorithms for constructing knight's tours on an $n \times n$ board (for even $n \geq 6$) are compared and contrasted using a combination of experimental and theoretical techniques. The first algorithm is a Hopfield-style neural network recently proposed by Takefuji and Lee. The second is a random walk algorithm that combines two classical techniques due to Euler in 1759 and Warnsdorff in 1823. The third is a new divide-and-conquer algorithm that constructs a knight's tour for all even $n \geq 6$, variants of which can be used to construct quadrisected knight's tours for all even $n \geq 8$, tours that are invariant under a 180 degree rotation for all even $n \geq 8$, and tours that are invariant under a 90 degree rotation for all $n \geq 10$ congruent to 2 modulo 4. The neural network appears to take exponential time. The random walk algorithm also appears to run in exponential time, but is practical for a significantly larger range of $n$. The divide-and-conquer algorithm runs in $O(n^2)$ (i.e. linear) time on a sequential processor, and is particularly amenable to implementation on many different types of parallel computer: in time $O(n^2/p)$ by a bounded degree network with $p$ processors for all $p = O(n^2/ \log n)$, in time $O(n^2/p^2)$ by a $p \times p$ mesh for all $p \leq n^{2/3}$, in $O(1)$ time on an $n \times n$ mesh with multiple CREW buses, and in $O(1)$ time on a CREW PRAM with $O(n^2)$ processors. The sequential algorithm is very simple to implement and can be used to generate tours for reasonably large values of n in a matter of seconds. It can also be used to prove a lower bound of $\Omega(1.1^{n{^2}})$ on the number of knight's tours on an $n \times n$ board for all even $n \geq 6$, and a stronger lower bound of $\Omega(1.248^{n{^2}})$ when $n$ is of the form $6 \times 2^k$ for some $k \in$ \textsf{I}\hspace{-.025in}\textsf{N}. \newpage \begin{center} {\Large \bf A Linear-Processor Polylog-Time Algorithm for Shortest-Paths in Planar Graphs} \vspace{.3in} Philip Klein\\ Dept. of Computer Science\\ Brown University\\ Providence, RI 02912-1910\\ \tt{klein@cs.brown.edu} \end{center} Computing single-source shortest paths with nonnegative lengths, in addition to being a fundamental problem in its own right, arises frequently in solving other problems. The sequential algorithms for this problem are quite efficient; they require only slightly more than linear time. Unfortunately, we don't know how to solve this problem as efficiently in parallel. Polylog-time algorithms using a polynomial number of processors are known, but the processor bounds are large. We give an algorithm requiring polylog time and a linear number of processors to solve single-source shortest paths in directed planar graphs. More generally, the algorithm works for any graph provided with a decomposition tree constructed using size-$\sqrt{n}$ separators. Our method also yields a polylog-time algorithm requiring $m^2$ processors for arbitrary graphs with $m$ edges. Joint work with Sairam Subramanian. \newpage \begin{center} {\Large \bf Polylog-Time and Near-Linear Work Approximation Scheme for Undirected Shortest Paths} \vspace{.3in} Edith Cohen\\ AT\&T Bell Laboratories\\ Murray Hill, NJ 07974\\ \tt{edith@research.att.com} \end{center} Shortest paths computations constitute one of the most fundamental network problems. Nonetheless, known parallel shortest-paths algorithms are generally inefficient: they perform significantly more work (product of time and processors) than their sequential counterparts. This gap, known in the literature as the ``transitive closure bottleneck,'' poses a long-standing open problem. Our main result is an $O(mn^{\epsilon_{0}} + s(m + n^{1+\epsilon_{0}}))$ work polylog-time randomized algorithm that computes paths within $(1 + O(1/$ polylog $n))$ of shortest from $s$ source nodes to all other nodes in weighted undirected networks with $n$ nodes and $m$ edges (for any fixed $\epsilon_0 > 0)$. This work bound nearly matches the $\tilde{O}(sm)$ sequential time. In contrast, previous polylog-time algorithms required min$\{\tilde{O}(n^3), \tilde{O}(m^2)\}$ work (even when $s$ = 1), and previous near-linear work algorithms required near-$O(n)$ time. Another result is faster shortest-paths algorithms if accurate distances are required only between ``distant'' vertices: We obtain an $O((m + sn)n^{\epsilon_{0}})$ time algorithm that computes paths of weight $(1 + O(1/$ polylog $n$))dist $+ O(w_{\max}$ polylog $n$), where dist is the corresponding distance and $w_{\max}$ is the maximum edge weight. Our chief instrument, which is of independent interest, are efficient constructions of sparse {\em hop sets}. A $(d, \epsilon)$-hop set of a network $G = (V, E)$ is a set $E$* of new weighted edges such that minimum-weight $d$-edge paths in $(V, E \cup E*)$ have weight within $(1 + \epsilon)$ of the respective distances in $G$. We construct hop sets where $\epsilon = O(1/$ polylog $n$) and $d = O($polylog $n$). \newpage \begin{center} {\Large \bf Graph Isomorphism and Identification Matrices: Parallel Algorithms} \vspace{.3in} Lin Chen\\ Univ. Southern California\\ \tt{linchen@flash.usc.edu} \end{center} Let $M_1$ and $M_2$ be two matrices representing, respectively, two graphs $G_1$ and $G_2$ Of a certain class $\mathcal{C}$, according to a certain relation $\mathcal{R}$. Suppose $G_1$ and $G_2$ are isomorphic if and only if there exist two permutation matrices $P_1$ and $P_2$ such that $M_1 = P_1M_2P_2$ Then the matrices representing the graphs are said to be {\em identification matrices} for $\mathcal{C}$, with respect to $\mathcal{R}$. Here we exhibit part of the use of identification matrices in studying the graph isomorphism problem, a well-known long-standing open problem. We show that, given two graphs in the form of a certain identification matrix, isomorphism can be tested efficiently in parallel if at least one matrix satisfies the circular 1's property, and more efficiently in parallel if at least one matrix satisfies the consecutive 1's property. Graphs which have identification matrices satisfying the circular 1's property include, not exclusively, $\Theta$ circular arc graphs and $\Gamma$ circular arc graphs. The result presented here substantially broadens the class of graphs for which there are known efficient parallel isomorphism testing algorithms. \newpage \begin{center} {\Large \bf Scalable Implementations of Multipole-Accelerated Algorithms for Molecular Dynamics} \vspace{.3in} John A. Board, Jr.\\ Duke University\\ Department of Electrical Engineering\\ Box 90291, Durham NC 27708\\ \tt{jab@ee.duke.edu} \end{center} We consider efficient, scalable solutions to the long-range force computation problem in molecular dynamics (MD) simulation. Though a large variety of forces act between the individual atoms in a molecular dynamics system, the Coulomb force is perhaps the most troublesome to compute. Straightforward implementation of a Coulomb solver leads to an $\mathcal{O}$$(N^2)$ summation over all pairwise combinations of the $N$ atoms in a system; this quadratic complexity limits the size of systems that can be simulated to a few tens of thousands of atoms even when special-purpose parallel hardware is employed. Practical MD codes usually truncate the Coulomb interaction at some moderate interaction radius to limit the cost of the Coulomb force evaluation; this can potentially alter the dynamics of the simulated system. Our work permits inclusion of all pair interactions (i.e. no truncation) at a runtime cost which grows linearly in the size of the system. Our programs are based on the Fast Multipole Algorithm (FMA) of Greengard and Rokhlln and on similar multipole-accelerated algorithms. We have implemented the FMA and related multipole codes on a variety of uniprocessors and parallel and distributed computer systems. The serial FMA reduces the complexity of the $N$-body problem of electrostatics and gravitation to order $N$ while preserving controllable accuracy in the computation. The parallel FMA allows further reductions in simulation times for $N$-body problems; for uniform distributions of particles in cubic simulation volumes, nearly linear speedup is obtained on small ($\leq$ 32 processors) parallel systems. The approach taken scales easily to 64 processors and has been tested on up to 32 processors. Additional refinements to the multipole methods allow for the multipole series manipulations to be performed in the Fourier domain, further reducing the complexity of our force computations. Joint work with William J. Blanke, Daniel C. Gray, Ziyad S. Hakura, William D. Elliott (Duke) and James F. Leathrum, Jr. (Old Dominion). \newpage \begin{center} {\Large \bf Parallel Graph Algorithms: Theory and Implementation} \vspace{.3in} Vijaya Ramachandran\\ Department of Computer Sciences\\ The University of Texas at Austin\\ Austin, TX 78712\\ \tt{vlr@cs.utexas.edu} \end{center} The design and analysis of efficient parallel graph algorithms has been an area of extensive study over the past decade. In this talk we will describe a library of parallel graph algorithms that we have implemented, based on PRAM algorithms designed by us and other researchers. The library was implemented on the Maspar MP-1, which is a massively parallel SIMD machine with 16,384 processors, and we provide performance data on our code. Our library is modular and currently contains code for finding connected components, minimum spanning forest, ear decomposition, cut-edges, strong orientation and open car decomposition of an undirected graph. These algorithms work by calling a collection of basic parallel primitives such as prefix sums, list ranking and Euler tour on trees. Due to the modular nature of our code it can be extended in a fairly straightforward way to include other parallel graph algorithms based on ear decomposition or open ear decomposition, or other parallel algorithms that build on the basic parallel primitives we have implemented. Our experience with this implementation suggests that, overall, the PRAM is a good model for developing parallel algorithms. Joint work with Tsan-sheng Hsu and Nate Dean. \newpage \begin{center} {\Large \bf Towards High-Performance Fault-Tolerant Distributed Processing} \vspace{.3in} Zvi Kedem\\ New York University\\ \tt{kedem@cs.nyu.edu} \end{center} Methods for producing robust programs executing correctly and efficiently on fault-prone asynchronous computing systems are presented. The methods can be used to automatically transform given application programs written for ideal perfect synchronous machines into robust programs executing dependably on realistic machines. The robust programs will contain embedded software modules. During the execution, these modules will monitor the computation's progress and by employing thread scheduling algorithms will dynamically adapt the computation to the changing availability of resources. \newpage \begin{center} {\Large \bf Fast Deterministic Compaction and its Applications} \vspace{.3in} Torben Hagerup\\ Max Planck Institute for Computer Science\\ Germany\\ \tt{torben@mpi-sb.mpg.de} \end{center} The lower bound of Beame and H\aa stad seemed to quench all hope of really fast parallel algorithms for such fundamental problems as compaction. Although seldom expressed in so many words, we were effectively operating with the notion of a ``parity bottleneck'' of $\Theta(\log n/\log \log n)$. It therefore came as a big surprise when Matias and Vishkin demonstrated that approximate compaction can be carried out in $O$(log*$n$) expected time on a randomized CRCW PRAM. Later it was discovered that approximate compaction can in fact be done in $o(\log n/\log \log n)$ time even without the use of randomization. The talk describes the latter result and some of its applications, trying to cover as many ideas and as few details as possible. \newpage \begin{center} {\Large \bf Efficient Low Contention Parallel Algorithms} \vspace{.3in} Phillip B. Gibbons\\ AT\&T Bell Laboratories\\ Murray Hill, NJ 07974\\ \tt{gibbons@research.att.com} \end{center} We recently introduced the queue-read, queue-write (QRQW) PRAM model \cite{gibbons,gibbons2}, which permits concurrent reading and writing, but at a cost proportional to the number of readers/writers to a memory location in a given step. The QRQW reflects the contention properties of most parallel machines more accurately than either the well-studied EREW or CRCW models. Indeed, in machines with non-combining networks, concurrent reads or writes to a location queue up and are serviced one-at-a-time. The QRQW PRAM is strictly more powerful than the EREW PRAM, yet it can be as efficiently emulated with only {\em logarithmic} slowdown on Valiant's BSP model \cite{valiant} and on hypercube-type non-combining networks. In contrast, efficient emulations for the CRCW PRAM on such networks are only known with {\em polynomial} slowdown. The QRQW PRAM is the first formal complexity model for the design and analysis of low-contention parallel algorithms. We study the impact of the QRQW rules on algorithm design, devising new techniques for low-contention algorithms. Our results include fast and efficient algorithms for computing the OR, leader election, linear compaction, multiple compaction, integer sorting, CRCW simulation, and random permutation, as well as several lower bounds. For example, we have obtained the following results: \begin{itemize} \item An $\Omega(\sqrt{\log n})$ time separation between the QRQW PRAM and the weaker EREW PRAM. \item An $O(\sqrt{\log n})$ time, linear work w.h.p. QRQW algorithm for generating a random cyclic permutation; this contrasts with the best known $O(\log n)$ time, super-linear work EREW algorithm. \item An $O(\log n)$ time, linear work w.h.p. QRQW algorithm for the multiple compaction problem; in contrast, no $o(n \log n)$ work algorithm is known for the EREW. \end{itemize} Our results demonstrate the advantage of a low-contention model (QRQW) over a zero-contention model (EREW), particularly for randomized algorithms. Joint work with Yossi Matias (AT\&T Bell Laboratories) and Vijaya Ramachandran (University of Texas, Austin). \newpage \begin{thebibliography}{99} \bibitem{gibbons} P. B. Gibbons, Y. Matias, and V. Ramachandran. QRQW: Accounting for concurrency in PRAMs and Asynchronous PRAMs. Technical report, AT\&T Bell Laboratories, Murray Hill, NJ, March 1993. Revised version. \bibitem{gibbons2} P. B. Gibbons, Y. Matias, and V. Ramachandran. The QRQW PRAM: Accounting for contention in parallel algorithms. In {\em Proc. 5th ACM-SIAM Symp. on Discrete Algorithms}, January 1994. To appear. \bibitem{valiant} L. G. Valiant. A bridging model for parallel computation. {\em Communications of the ACM}, 33(8):103-111, 1990. \end{thebibliography} \newpage \begin{center} {\Large \bf Paradigms for fast parallel approximations for problems that are hard to parallelise} \vspace{.3in} Paul G. Spirakis\\ Computer Technology Institute\\ Patras University\\ P.O.B. 1122, 26110 Patras\\ Greece\\ \tt{spirakis@grpatvx1.bitnet} \end{center} We present here recent and new results on fast parallel approximations to problems that are hard to parallelise. We discuss five paradigms for efficient parallel approximations. (1) The dense graph properties paradigm where a particular algorithm that eliminates vertices of low degrees is shown to produce in NC constant ratio approximations for any graph problem satisfying a certain property of a certain class of extremal graph properties. (2) By suitably modifying the L-reductions of the class Max-SNP to be log-space , we show that any problem in SNP admits constant ratio NC approximations. (3) We discuss the primal-dual method of Luby and Nisan which shows that positive LP can be approximated in NC. (4) We present the scaling down method for problems whose hardness is due to sizes of numbers. We show that general Max Flow admits a fully RNC approximation scheme and an NC approximation scheme. We show the same for Maximum Matching. (5) We overview the method of decomposing in NC a planar graph into k-outerplanar components (for fixed k) and discuss the constant ratio approximations obtained for planar MIS and other planar graph problems by this decomposition. Joint work with J. Diaz , M. Serna , J. Toran and L. Kirousis. \newpage \begin{center} {\Large \bf Some Recent Results on Schwarz Type Domain Decomposition Algorithms} \vspace{.3in} Olof B. Widlund\\ Courant Institute of Mathematical Sciences\\ New York, New York\\ \tt{widlund@cs.nyu.edu} \end{center} Domain decomposition methods appear to offer the best promise for the efficient parallel solution of the large linear systems of equations that arise in finite element and finite difference discretizations of problems of continuum mechanics. There is growing experimental evidence that some of these algorithms map quite well onto relatively loosely coupled parallel computing systems. A domain decomposition methods was considered by Hermann Amandeus Schwarz as early as 1869, although for entirely different reasons. The classical Schwarz alternating method can be described in terms of subspaces, which are directly related to the subdomains into which the given region has been subdivided, and projections onto these subspaces. Many other domain decomposition methods for elliptic problems can be placed in a framework, which is closely related to this interpretation. The resulting theory has recently proven very successful in the systematic study of other iterative methods for partial differential equations such as multilevel and multigrid algorithms. As an introduction, the classical block Jacobi-conjugate gradient preconditioner for elliptic problems is considered. If the blocks correspond to subregions of diameter H, and that of the original region is on the order of 1, then it is easily shown that the number of iterations must be of order $1/H$. This corresponds to a condition number of order $1/H^2$. This simple preconditioner can be improved, and the condition number decreased to $C(1 + H/h)$, by augmenting it by a simple coarse problem. Here, $h$ is the mesh size of the finite element discretization of the given elliptic problem. It is also shown how the rate of convergence can be greatly enhanced by introducing overlap between the subregions. This will be followed by a discussion of some numerical experiments that show that these simple algorithms are quite useful even for very difficult elliptic problems. If time allows, there will also be a short discussion of a different type of domain decomposition algorithms, in particular one due to Barry Smith. \newpage \begin{center} {\Large \bf The Proteus System for the Development of Parallel Algorithms} \vspace{.3in} Jan F. Prins\\ University of North Carolina at Chapel Hill\\ \tt{prins@cs.unc.edu} \end{center} Fundamental variations in the organization and performance characteristics of current parallel computers give rise to a complex design space in which significant trade-offs exist in the development of practical parallel algorithms. Current parallel programming languages are too low-level and often too architecture-specific to support extensive exploration of this design space. On the other hand, highly abstracted models of parallel computation are often too high-level to express and analyze the performance implications of design changes. The Proteus system consists of a high-level parallel programming language named Proteus and a program transformation system that translates suitably restricted Proteus programs to low-level codes directly executable on parallel machines. Using the Proteus language, designs for parallel programs can be concisely expressed and refined over a broad spectrum of detail, and, through the use of a Proteus interpreter implementing the parallel semantics sequentially, executed and evaluated. Promising designs can be further refined and translated to executable code using the transformation engine. Taken together, these components support an exploratory or prototyping model of parallel program development. In this talk, the Proteus language and the translation of data-parallel Proteus programs to a low-level vector-model programming notation will be described. The exploration of decomposition strategies for the 3D adaptive fast-multipole algorithm for N-body calculations will be used to illustrate the development process supported by the Proteus system. (The papers below are available via anonymous ftp to cs.duke.edu and are located in directory /pub/proteus/reports.) Joint work with Peter Mills, Lars Nyland and John Reif. \vspace{2.0in} \begin{thebibliography}{99} \bibitem{nyland} Lars Nyland, Jan Prins, and John Reif. A Data-Parallel Implementation of the Adaptive Fast Multipole Algorithms. {\em In Proc. 2nd Symp. on Issues and Obstacles in the Practical} {\em Implementation of Parallel Algorithms and the Use of Parallel Machines (DAGS93)}, Dartmouth College, Hanover, NH, June 1993. \bibitem{prins} Jan Prins and D. Palmer. Transforming High-Level Data-Parallel Programs into Vector Operations. In {\em Proc. 4th ACM Symp. on Principles and Practice of Parallel Programming}, San Diego, Ca, May 1993. \bibitem{mills} Peter Mills, Jan Prins, and John Reif. Rate Control as a Language Construct for Parallel and Distributed Programming. In {\em Proc. of IEEE Workshop on Parallel and Distributed Real-Time Systems (IPPS'93)}, Newport Beach, CA, April 1993. \bibitem{mills2} Peter Mills, Lars Nyland, Jan Prins, and John Reif. Prototyping High-performance Parallel Computing Applications in Proteus. In {\em Proc. 1992 DARPA Software Technology Conference}, Meridian Press, 1992. \end{thebibliography} \newpage \begin{center} {\Large \bf Analysis and Prediction on Parallel Processors of Protein Binding on DNA: Pattern Recognition of Hydrogen Bonds}\\ \vspace{.3in} Yuefan Deng\\ Center for Scientific Computing\\ SUNY at Stony Brook\\ Stony Brook, NY 11794-3600\\ \tt{Yuefan.Deng@sunysb.edu} \end{center} The theme of this presentation is specificity, or DNA sequence selection, for protein binding on DNA. We introduce a simplified model for the binding energy based on hydrogen bonds alone. Based on this model, we present an optimized algorithm for geometric pattern recognition. The algorithm is implemented for use on parallel supercomputers. All applicable DNA-protein complexes in the BNL data bank with full atomic coordinates are analyzed by this algorithm, with satisfactory results in all cases. We conclude that the algorithm may be a useful screening tool for assessing DNA pattern selection by DNA-binding proteins and for efficient solution of the docking problem. We also conclude that hydrogen bonds appear to play significant role in binding specificity in all cases analyzed. The algorithm is also useful as a solution or preprocessing partial solution to the docking problem, as it provides a rapid estimation of the ``best'' relative alignment of two molecules in a complex. Energy minimization, even in this simplified model based on the geometry of hydrogen bonds, is complicated by an enormous number of local minima. These are understood combinatorially and screened efficiently using a geometric approach to match patterns approximately, based on a square well potential. The second part of the algorithm is a closed form solution for minimization based on a quadratic potential. A Monte Carlo method using a modified Lennard-Jones potential, as a third step, is used to prioritize further the best ranked approximately matched patterns. Joint work with G. Campbell, M. Eisenberg, J. Glimm, Y. Wang, and Q. Yu. \newpage \begin{center} {\Large \bf Optimal Randomized Parallel Algorithms for Computing the Row Maxima of a Totally Monotone Matrix} \vspace{.3in} Rajeev Raman\\ University of Maryland\\ \tt{raman@umiacs.umd.edu} \end{center} We consider the problem of finding the row maxima of a $n \times n$ {\em totally monotone} matrix, a problem with many applications to geometric and combinatorial problems. Although this problem can be solved in $O(n)$ time sequentially, all known poly-log time parallel algorithms for this problem have a time-processor product of $O(n \log n/ \log \log n)$ or worse. Finding work-optimal parallel algorithms for this problem has been a relatively long-standing open problem. We give randomized algorithms for this problem which run in $O(\log n)$ time and $O(\log \log n)$ time on the EREW and CRCW PRAMs respectively, and have a time-processor product of $O(n)$. The run-times are the best possible, even for randomized parallel algorithms. Joint work with Uzi Vishkin. \newpage \begin{center} {\Large \bf Trade-offs in Parallel Computation of Huffman Tree and Concave Least Weight Subsequence} \vspace{.3in} Teresa M. Przytycka\\ Department of Math. and Computer Science\\ Odense University\\ DK-5230 Odense M, Denmark\\ \tt{przytyck@imada.ou.dk} \end{center} During the last decade several important problems have been placed in the NC class. However, for many such problems the work function of the corresponding NC algorithm is greater by a polynomial factor than the time complexity of the best known sequential algorithm for the problem. This makes such algorithms unattractive for small (which may even mean linear) number of processors. This observation is also true for the previously known algorithms for the Concave Least Weight Subsequence (CLWS) problem - a problem to which many other interesting problems (including the classic Huffman tree problem) can be reduced. One way of dealing with the above problem is to search for an almost optimal solution rather than for the optimal one. This leads to the familiar trade-off: accuracy versus total work. Such a trad-off was examined in \cite{kirk} where a family of parallel NC algorithms that construct almost optimal solutions to the Huffman Tree problem was presented. Among other, there woas given an $O(k \log n$ log* $n)$-time $n$ processors algorithm that approximates k the Huffman tree with error bounded by $1/n^k$. An alternative approach is to develop algorithms, that exhibit a certain work-time trade-off: given a parameter $p$ the algorithm performs $O(w(n,p))$ work, in $t(n,p)$ time, where the $t(n,1) = \tilde{O}(w(n,1))$, and for a given $n, t(n,p)$ decreases with the value of $p$ while $w(n,p)$ can increase with the value of $p$. The first step in this direction was taken in \cite{lar} where an $O(\sqrt{n} \log n)$-time $n$-processor algorithm to the Concave Least Weight Subsequence problem was given. In this talk, we give parallel algorithms for Huffman Tree problem and the CLWS problem which exhibit the work-time trade-off defined above. Namely, we show an algorithm which a parameter $p$, solves the CLWS problem in $O(\frac{n}{\sqrt{p}} \log^2 n)$ time using $p$ processors. By the reduction of the Huffman Tree problem to the CLWS problem, we obtain the same complexity bounds for the Huffman Tree problem. However, as we show, for the later problem there exists a simpler (and, in fact, slightly better) algorithm that exhibits a similar trade-off: Namely, for a given parameter $p, p \geq 1$, the algorithm runs in $O(\frac{n}{\sqrt{p \log(p+1)}}(\log^2 p + \log(n - \sqrt{p \log p})))$ time using $p$ processors. In particular, for $p = 1$ our algorithm reduces to the classic sequential algorithm. \newpage Joint work with Christos Levcopoulos (Lund University). \begin{thebibliography}{99} \bibitem{kirk} D.G. Kirkpatrick and T.M. Przytycka. Parallel construction of binary trees with almost optimal weighted path length, {\em Proc. 2nd Symp. of Parallel Algorithms and Architectures} (1990). \bibitem{lar} L.L. Larmore and T.M. Przytycka, Parallel construction of trees with optimal weighted path length, {\em Proc. 3st Symp. on Parallel Algorithms and Architectures} (1991), pp. 71-81. \bibitem{lev} Christos Levcopoulos and T.M. Przytycka, A work-time trade-off in parallel computa- tion of Huffman Tree and Concave Least Weight Subsequence, manuscript. \end{thebibliography} \newpage \begin{center} {\Large \bf A Primal-dual RNC Approximation Algorithm for (multi)-Set (multi)-Cover} \vspace{.3in} Vijay Vazirani\\ IIT Delhi \& DIMACS\\ \tt{vijay@cs.princeton.edu} \end{center} We build on the classical greedy sequential set cover algorithm, in the spirit of the primal-dual schema, to obtain simple parallel approximation algorithms for the set cover problem and its generalizations. Our algorithms use randomization, and our randomized voting lemmas may be of independent interest. Fast parallel approximation algorithms were known before for set cover though not for any of its generalizations. Joint work with Sridhar Rajagopalan. \newpage \begin{center} {\Large \bf Parallel Methods for Computational Geometry} \vspace{.3in} Michael T. Goodrich\\ Department of Computer Science\\ Johns Hopkins University\\ Baltimore, MD 21218\\ \tt{goodrich@cs.jhu.edu} \end{center} In this talk I will survey general techniques for solving computational geometry problems in parallel, as well as focusing on parallel methods for solving specific problems. Techniques discussed will include geometric divide-and-conquer, parallel data structures, and derandomization. Specific problems addressed will include convex hulls in 2- and 3-dimensions, segment intersection, and some problems from computer graphics. \newpage \begin{center} {\Large \bf Highly Parallel Randomized Algorithms -- Some Recent Results} \vspace{.3in} Yossi Matias\\ AT\&T Bell Laboratories\\ Murray Hill, NJ 07974\\ \tt{matias@research.att.com} \end{center} Recent years have seen a dramatic increase in the number of nearly-constant time parallel algorithms discovered. Paradigms and techniques have been developed to exploit the power of randomization and obtain $O$(log* $n$) time (w.h.p.) randomized algorithms for quite a few problems, including hashing, generating random permutations, linear approximate compaction, load balancing and interval allocation. The last three problems can be viewed as much relaxed versions of the prefix sums computation-a fundamental problem in parallel computation that cannot be solved faster than $\Theta(\log n/ \log \log n)$ time, even when using polynomial number of processors. Recently it was discovered \cite{good} that the prefix sums can be closely approximated in $O$(log* $n$) time w.h.p., using $n/$ log* $n$ processors, which is optimal in terms of both work and running time. The approximate prefix sums are guaranteed to come within a factor of $(1 + \epsilon)$ of the values of the true sums in a ``consistent fashion'', where $\epsilon$ is $o(1)$. Some of the ideas behind this algorithm will be discussed. The log-star randomized algorithms that have been developed for the problems mentioned above run on most of the popular CRCW PRAM models which allow conflict in concurrent write. However, they are not known to run on the COMMON CRCW PRAM, one of the well studied CRCW models in the literature on parallel algorithms. The COMMON model requires processors writing simultaneously into the same memory cell to write the same value only. This restriction, which forbids conflicts in concurrent write, makes it difficult to claim resources at random-an operation which is at the heart of the fast randomized algorithms. We show \cite{berk} that in many cases this inherent difficulty can be circumvented and we present $O$(log* $n$) time (w.h.p.), $n/$ log* $n$-processor randomized algorithms on COMMON for the problems of linear approximate compaction, load balancing, and approximate prefix sums. Joint works with 0. Berkman (King's College), P. Gibbons (AT\&T Bell Laboratories), M. Goodrich (Johns Hopkins U.), and U. Vishkin (U. Maryland \& Tel Aviv U.). \newpage \begin{thebibliography}{99} \bibitem{good} M. T. Goodrich, Y. Matias, and U. Vishkin. Optimal parallel approximation algorithms for prefix sums and integer sorting. In {\em Proc. of the Fifth Annual ACM-SIAM Symposium on Discrete Algorithms}, Jan. 1994. To appear. \bibitem{berk} O. Berkman, P. B. Gibbons, and Y. Matias. On the power of randomization for the Common PRAM (hopping onto the log-star wagon). Manuscript, Nov. 1993. \end{thebibliography} \newpage \begin{center} {\Large \bf Optimal Hypercube Algorithm for the All-Nearest Smaller Values Problem} \vspace{.3in} Dina Kravets\\ New Jersey Institute of Technology\\ \tt{dina@lilac.njit.edu} \end{center} Given a sequence of $n$ elements, the {\em All-Nearest Smaller Values} (ANSV) problem is to find, for each element $x$ in the sequence, the nearest element to the left (right) of $x$ that is smaller than $x$, or to report that no such element exists. Berkman, Schieber, and Vishkin give a CREW-PRAM algorithm for this problem that takes $O$(lg $n$) time using $n/$ lg $n$ processors. We present a hypercube algorithm for the ANSV problem that runs in $O$(lg $n$) time using $n$ processors. Our algorithm belongs to the class of so-called ``normal'' hypercube algorithms, and thus achieves the same processor/time bounds on any of the bounded-degree variants of the hypercube (e.g., the butterfly, cube-connected cycles, and shuffle-exchange). We prove that $\Omega(n)$ processors are necessary for any normal hypercube algorithm to solve the ANSV problem in $O$(lg $n$) time. Under a stronger model of hypercube computation, in which each processor is allowed to use all of its edges in a single time-step, we demonstrate that the ANSV problem can be solved in $O$(lg $n$) time using $n/$ lg $n$ processors. We use our ANSV algorithm to give the first logarithmic-time hypercube algorithm for triangulating a monotone polygon, a routine used in the parallel algorithms for triangulating simple polygons. We also obtain a logarithmic-time hypercube algorithm for constructing a Cartesian tree. Joint work with Greg Plaxton. \newpage \begin{center} {\Large \bf Optimal Parallel Hypercube Algorithms for Polygon Problems} \vspace{.3in} Mikhail J. Atallah\\ Department of Computer Sciences\\ Purdue University\\ West Lafayette, IN 47907\\ \tt{ mja@cs.purdue.edu} \end{center} We present parallel techniques on hypercubes for solving optimally a class of polygon problems. We thus obtain optimal $O($log $n$)-time, $n$-processor hypercube algorithms for the problems of computing the portions of an $n$-vertex simple polygonal chain $C$ that are visible from a given source point, computing the convex hull of $C$, testing an $n$-vertex simple polygon $P$ for monotonicity, and other related problems as well. Previously it was not known how to achieve these complexity bounds on hypercubes, one of the main difficulties being that there is no known optimal sorting hypercube algorithm that achieves these bounds. In fact these are the first optimal geometric hypercube algorithms that do not assume that the input is given already sorted by $x$ or $y$ coordinates. The hypercube model we use is the standard one, with $O$(1) local memory per processor, and with one-port communication. Joint work with Danny Z. Chen (University of Notre Dame). \newpage \begin{center} {\Large \bf Optimal Tree Contraction on the Hypercube and Related Networks} \vspace{.3in} Ernst W. Mayr\\ Institut f\"{u}r Informatik\\ Technische Universit\"{a}t, M\"{u}nchen\\ \tt{mayr@informatik.tu-muenchen.de} \end{center} An optimal tree contraction algorithm for the boolean hypercube and the constant degree hypercubic networks, such as the shuffle exchange or the butterfly network, is presented. The algorithm is based on novel routing techniques and, for certain small subtrees, simulates optimal PRAM algorithms. For trees of size $n$, stored on a $p$ processor hypercube in in-order, the running time of the algorithm is $O(\frac{n}{p} \log p)$. The resulting speed-up of $O(p/ \log p)$ is optimal due to logarithmic communication overhead, as shown by a corresponding lower bound. Joint work with Ralph Werchner, Fachbereich Informatik, J.W. Goethe-Universit\"{a}t, Frankfurt am Main, werchner@informatik.uni-frankfurt.de \newpage \begin{center} {\Large \bf Evaluating Parallel Approximation Algorithms} \vspace{.3in} David J. Haglin\\ Computer and Information Sciences Department\\ Mankato State University\\ Mankato, MN 56002\\ Voice: (507) 389-2968\\ FAX: (507) 389-6376\\ haglin@epsilon.cs.mankato.msus.edu\ \end{center} Polynomial-time approximation algorithms have been widely studied, especially for $\mathcal{NP}$-complete problems. Many complexity classes have been developed that are based on how easily a problem can be approximated. There are problems that do not have $(1 - \epsilon)$- approximation algorithms, for some fixed ratio $\epsilon$, unless $\mathcal{P} = \mathcal{NP}$. Other problems have $(1 - \epsilon)$-approximation algorithms, for $O < (1 - \epsilon) \leq r$, but not for $(1 - \epsilon) > r$ (unless $\mathcal{P = NP})$. Here $r$ is the $\mathcal{P}$ - {\em optimal} value for the problem. Still other problems have $\epsilon$-approximation schemes. Bringing these ideas to the parallel processing realm requires some additional concepts to fully capture the essence of approximation algorithms. In the serial realm, an approximation scheme trades running time for relative error. In the parallel realm, there is more than one resource that may be increased to obtain a closer approximation: running time and number of processors. We define a {\em two-way} trade-off as an algorithm that uses more running time and processors to find a closer approximation. A {\em three-way} trade-off is an algorithm that uses either more running time or more processors to obtain a closer approximation. We investigate the deterministic maximum matching problem which exhibits an interesting phenomenon showing the different nature between the serial and parallel approximation realms. We present some matching results for bounded degree graphs that improve upon recent approximation schemes. We show how to find a {\em maximal} matching in a bipartite graph with highest degree $\Delta$ in $O(\Delta)$ time using $O(n)$ processors, which leads to an $O(1/(1 - \epsilon)^2 \cdot \log n)$ time, $O(n)$ processor algorithm for finding a matching whose relative error is $\epsilon$. This observation applied to bounded degree (general) graphs can improve upon the resource trade-off of a recent $\mathcal{NC}$-approximation scheme for general graphs. \newpage \setcounter{footnote}{0} \begin{center} {\Large \bf Distributed Implementation of an Algorithm for the Maximum Flow Problem} \vspace{.3in} Jesper Larsson Tr\"aff\\ DIKU - Department of Computer Science\\ University of Copenhagen\\ Universitetsparken 1, DK-2100 Copenhagen \O\\ Denmark\\ \tt{traff@rimfaxe.diku.dk} \end{center} We discuss an implementation of the maximum flow algorithm of Shiloach and Vishkin\footnote{Yossi Shiloach and Uzi Vishkin. An $O(n^2 \log n)$ parallel MAX-FLOW algorithm. {\em Journal of Algorithms}, 3:128-146,1982.} on a distributed system without shared memory. This algorithm is a clever variation of Karzanov's algorithm, and possesses features which make it an interesting candidate for distributed implementation. First, it is possible to arrange for many processors to perform flow operations (flow push and return) on different vertices simultaneously. Second, in contrast to Karzanov's algorithm, flow returns may be performed from vertices at different levels in the layered network simultaneously, which eliminates the need for expensive global synchronization of the flow return operations. The talk will outline the sequential algorithm and concentrate on implementation issues which are relevant regardless of the specifics of the distributed system at hand: distribution of data structures (graph, queue and stacks) and reduction of communication volume. For each layered network the algorithm proceeds in phases, in each balancing (flow push followed by flow return) a set of vertices which have flow excess. Each phase corresponds to a pass over a local queue, after which updates must be exchanged between all processors. With a {\em static} distribution of the graph empirical speed-up can be expected, although it is not possible to guarantee speed-up in the worst case. A new heuristic for ``increasing parallelism'' by creating more vertices which will appear in the queue during each phase will also be presented: for each vertex in the layered network the heuristic maintains a {\em potential flow} which is an upper bound on the flow that the vertex can transport to the sink. Potential flows serve to make pushes more precise, in particular to eliminate (some) pushes that cannot give rise to flow augmentations, thus reducing the number of flow return operations and as a consequence the number of phases. Results from (preliminary) experiments with the distributed algorithm on a small transputer system without as well as with the potential flow heuristic will be presented and discussed. While it is possible to achieve speed-up for smaller, dense graphs, a major problem in the basic implementation is the large fraction of the total time spent on synchronization and exchange of messages. In order to achieve speed-up when going beyond a few processors, means have to be found to hide synchronization time, possibly by making the algorithm more asynchronous. Furthermore, if the overall number of phases could be reduced, the time spent on synchronization would decrease. Whereas the first point is mainly implement ational, the {\em potential flow heuristic} attacks the latter problem. Indeed, with this heuristic speed-up of about 4 on 16 processors has been consistently achieved for the types of graphs used.\\ \noindent {\large \bf Preliminary experimental results} Below results from experiments with two different graphs are shown in order to illustrate problems and promises of the implementation. The implementation has been done in OC-CAM, experimentation on a 16 processor transputer system (T800) with randomly generated graphs\footnote{For each vertex an average degree is chosen and so many edges are generated. Since this has a tendency to lead to networks where the minimum cut lies either at the source or the sink, other ways of generating test graphs must be chosen for the detailed experiments.} with the following characteristics: \vspace{.2in} \begin{tabular}{cccccc} \multicolumn {1} {c} {$n$} & \multicolumn {1} {c} {degree} & \multicolumn {1} {c} {layers} & \multicolumn {1} {c} {phases} & \multicolumn {1} {c} {vertices} & \multicolumn {1} {c} {$|f|$}\\ \hline 200 & 99 & 4 & 62/16 & 1209/1077 & 469689\\ 2000 & 8-12 & 5 & 9937/81 &27980/18007 & 50885 \end{tabular} \vspace{.2in} All edges have randomly generated integer costs in the interval [1, 10000]. Column ``layers'' lists the number of layered networks that have to be constructed to find a maximum flow, and ``phases'' the total number of phases required without/with the potential flow heuristic. For the larger, sparse graph the difference is dramatic, and very significant since each phase entails a synchronization step for the distributed algorithm. Column ``vertices'' lists the total number of unbalanced vertices considered without/with the heuristic. The next tables list the actual running times achieved with 1, 2, 4, 8, and 16 processors. Column ``t'' lists the total time spent without/with the potential flow heuristic, ``s'' the time spent on synchronization. As can be seen, keeping the number of phases as low as possible is essential for achieving speed-up. \vspace{.2in} \begin{tabular}{r|c|cc|cc} \multicolumn {1} {r|} {proc.} & \multicolumn {1} {c|} {1} & \multicolumn {2} {c|} {2} & \multicolumn {2} {c} {4} \\ $n$ & t & t & s & t & s\\ \hline 200 & 9.5/15.2 & 4.2/5.9 & 0.6/0.7 &3.7/3.6 & 1.3/0.7\\ 2000 & 28.2/28.1 & 36.6/17.3 & 21.3/1.3 & 65.5/11.3 & 54.7/1.4\\ \end{tabular} \vspace{.2in} \begin{tabular}{r|cc|cc} \multicolumn {1} {r|} {proc.} & \multicolumn {2} {c|} {8} & \multicolumn {2} {c} {16}\\ $n$ & t & s & t & s\\ \hline 200 & 3.0/3.3 & 1.9/1.1 & 5.7/3.2 & 4.8/1.7\\ 2000 & 150.7/7.7 & 140.5/1.8 & 387.5/6.7 & 374.4/3.2\\ \end{tabular} \newpage \begin{center} {\Large \bf Efficient Parallel Algorithms for Image Processing} \vspace{.3in} Joseph J\'{a}J\'{a}\\ Dept. of Electrical Engineering\\ University of Maryland\\ \tt{joseph@src.umd.edu} \end{center} We present efficient algorithms for low and intermediate level image processing on the scan line array processor, a SIMD machine designed for real-time video and image processing. For low level processing, we present algorithms that run in real-time. By real-time, we mean that, if the required processing is based on neighborhoods of size $m \times m$, then the output lines are generated at a rate of $O(m)$ operations per line and a latency of $O(m)$ scan lines. For intermediate level processing, we present optimal or close to optimal algorithms for translation, histogram computation, scaling, rotation, connected components, and convex hulls of multiple figures. The algorithms for connected components and convex hulls are significantly simpler and easier to implement than those already reported in the literature for linear arrays. \newpage \begin{center} {\Large \bf Game Tree Search\\ on\\ Massively Parallel Systems} \vspace{.3in} Rainer Feldmann\\ University of Paderborn\\ Germany\\ \tt{chess@uni-paderborn.de} \end{center} Tree search algorithms play an important role in many applications in the field of artificial intelligence. For instance, theorem provers, expert systems, robot control systems and game playing programs contain tree searching algorithms as their basic part. Tree searching is used whenever decisions must be made that are based on complex knowledge, which cannot be implemented directly on a machine. Came playing programs provide an excellent test bed for search algorithms. For the problem to search game trees a very efficient sequential algorithm, the so called {\em alphabeta} - algorithm (or the Scout variant) is known. The {\em alphabeta} - algorithm traverses the game tree in a depth first manner. It allows to cut off large parts of the right subtrees of the game tree by using information already computed in the left subtrees. Thus, the {\em alphabeta} - algorithm was believed to be inherently sequential. Therefore, the efficiency of most of the parallel game tree search algorithms implemented so far is very poor, even if only a few processors are used. Mainly, there are three types of losses occurring in a parallel game tree search: \begin{enumerate} \item {\em Search overhead:}\\ A parallel algorithm often may not have available the information which allows to cut off a subtree. Thus, the processors are searching parts of the game tree which cannot influence the final result and which the sequential {\em alphabeta} - algorithm would not have searched. \item {\em Processor work load:}\\ A decomposition of the game tree which guarantees a good average work load is dif- ficult, because the sizes of the subtrees are unpredictable in advance. Therefore, any static mapping of subtrees onto processors will result in a poor processor work load. \item {\em Communication overhead:}\\ Processors have to communicate for two reasons: first to balance the work load and second to broadcast the information about the game tree computed by other processors. \end{enumerate} \newpage In this paper we present a parallel game tree search algorithm which shows high efficiency even on massively parallel systems. The main concept is a completely dynamic game tree decomposition. We implemented the ``Young Brothers Wait Concept'' which keeps the search overhead small but, additionally, does not decrease the processor work load too much. We present an efficient use of a distributed hash table in a distributed memory system, i.e. we simulate global memory in a distributed system. This distributed hash table is used to store the information computed by the processors and make them available to all of them. To achieve a good processor work load we implemented a combination of local, global, and medium range search for work, which allows a good load balancing for small communication costs only. Experimental results are presented for up to 1024 processors showing a speedup of more than 340. With this, our parallel game tree search algorithm is the most efficient one known so far. It is the basis of our distributed chess program {\em ZUGZWANG}, which became Vize World Champion at the World Computer Chess Championships, 1992, in Madrid, Spain. Joint work with Peter Mysliwietz and Burkhard Monien. \newpage \begin{center} {\Large \bf Efficient Parallelization of a Branch \& Bound Algorithm for the Symmetric Traveling Salesman Problem} \vspace{.3in} S. Tsch\"{o}ke\\ Department of Mathematics and Computer Science\\ University of Paderborn\\ Germany\\ \tt{sts@uni-paderborn.de} \end{center} The traveling salesman problem is one of the most studied NP-complete problems of combinatorial optimization. Our interest was to see whether parallelism can be fully exploited in solving TSPs. We present a general method to parallelize branch \& bound algorithms on transputer networks and an application of this method to solve symmetric traveling salesman problems by a best first branch \& bound strategy. The parallelization of the branch \& bound algorithm is fully distributed. Every processor performs the same algorithm but on a different part of the solution tree. The algorithm running on each processor consists of three parts, a local heap management, a communication process and the sequential branch \& bound part to generate and evaluate subproblems. To distribute subproblems among the processors and to keep all local heaps on a nearly equal level we use a nearest-neighbor load-balancing strategy, i.e. subproblems and load informations are only sent to direct neighbors in the processor network. No global communication is needed \cite{luling}. With this strategy we minimize idle times and search overhead (only necessary parts of the solution tree are explored). On the one hand we wanted to use an efficient sequential algorithm to solve the traveling salesman problem, but on the other hand we also wanted to provide a general method of parallelization applicable for other problems of combinatorial optimization. To achieve this we do not parallelize the sequential computation of the subproblems. The current best approach to solve TSPs is the branch \& cut algorithm by Padberg and Rinaldi [4]. In order to parallelize this efficiently one would have to parallelize the sequential computation of the subproblems because of the huge effort spent on a single subproblem in comparison to the number of subproblems. Thus we chose the improved 1-tree relaxation branch \& bound algorithm by Volgenant and Jonker \cite{volgenant} based on the lagrangean approach introduced by Held and Karp \cite{held}. On TSP instances with many subproblems we achieve an almost linear speedup. At present we can efficiently solve euclidean symmetric traveling salesman problems up to a \newpage \noindent size of 318 cities on a asynchronous multiprocessor network of up to 1024 nodes (T800 transputers). The problem instances are taken from the standard TSP library \cite{reinelt}. We can conclude that the problem of efficient parallelization is solved for branch \& bound algorithms with an appropriate ratio between the effort which is spent on a single subproblem and the number of subproblems computed. The results were presented on the European Workshop on Parallel Computing EWPC 1992 in Barcelona and on the EURO XXII/TIMS XXXI Joint International Conference Operational Research/ Management Science 1992 in Helsinki. \begin{thebibliography}{99} \bibitem{held} M. Held and R.M. Karp, {\em The traveling salesman problem and minimum spanning trees: part II}, Mathematical Programming 1 (1971), pp. 6-25 \bibitem{luling} R. L\"{u}ling, B. Monien, {\em Load Balancing for distributed Branch and Bound Algorithms}, Proc. of 6th Int. Parallel Processing Symposium 1992, pp. 543-549 \bibitem{luling2} R. L\"{u}ling, B. Monien, M. R\"{a}cke, S. Tsch\"{o}ke, {\em Efficient Parallelization of a Branch \& Bound Algorithm for the Symmetric Traveling Salesman Problem}, Proc. of European Workshop on Parallel Computing EWPC (1992), Barcelona \bibitem{padberg} M. Padberg, G. Rinaldi, {\em A Branch and Cut Algorithm for the Resolution of Large Scale Symmetric Traveling salesman problems}, SIAM Review 33 (1991), S. 60-100 \bibitem{reinelt}G. Reinelt, {\em TSPLIB - A Traveling Salesman Problem Library}, ORSA Journal on Computing 3 (1991), pp. 376-384 \bibitem {volgenant} T. Volgenant, R. Jonker, {\em A branch and bound algorithm for the symmetric traveling salesman problem based on the 1-tree relaxation}, European J. Operational Res. 9 (1982), pp. 83-89 \end{thebibliography} Joint work with R. L\"{u}ling, B. Monien, and M. R\"{a}cke. \newpage \begin{center} {\Large \bf Solving the 0-1 Knapsack Problem on a Distributed Memory Multicomputer} \vspace{.3in} Erik T\"{a}rnvik\\ Institute of Information Processing\\ University of Ume\aa\\ S-901 87 Ume\aa\\ Sweden\\ \tt{erikt@cs.umu.se} \end{center} This talk summarizes our observations from using a parallel branch and bound algorithm to solve the 0-1 knapsack problem on a distributed memory multicomputer. A branch and bound algorithm is essentially a tree search were a bounding function is used to exclude parts of the tree which can be shown not to include an optimal element. In searching the tree, we have used a depth-first search strategy. Searching algorithms of this type are hard to parallelize, since we cannot know beforehand which parts of the tree will be excluded. This means that we can not use a static distribution of the workload. In implementing the algorithm, we have used the Dynamo tool in order to use dynamic load balancing to achieve good parallel efficiency. The algorithm has been implemented on the iPSC/2 hypercube multicomputer using the Dynamo dynamic load balancing tool. Computational results for different classes of problem instances are presented. The computational results indicate that the complexity of the problem instances determine the amount of parallelism available. For instances of high complexity, the parallel algorithm shows a linear speedup behavior. We conclude the talk by showing how a parallel reduction algorithm can be employed in order to obtain higher parallel performance for instances of low complexity. \newpage \begin{center} {\Large \bf Improved Parallel Algorithms via Approximating Probability Distributions} \vspace{.3in} Aravind Srinivasan\\ Institute for Advanced Study \& DIMACS\\ \tt{aravind@math.ias.edu} \end{center} We present two new techniques for approximating probability distributions. The first is a new method for constructing the small-bias probability spaces introduced by Naor \& Naor; this leads to improved parallel algorithms for certain problems which can be solved deterministically using small-bias spaces, such as set-balancing, finding large cuts in graphs, finding heavy codewords in linear codes, and other problems. The second is an explicit construction of small probability spaces approximating general independent distributions, which are better than the constructions of Even, Goldreich, Luby, Nisan \& Velickovic; this is a further step toward a powerful tool for derandomizing sequential and parallel algorithms. Joint work with Suresh Chari and Pankaj Rohatgi (Cornell University). \newpage \begin{center} {\Large \bf Parallel Simulated Annealing using Selection and Migration--an Approach Inspired by Genetic Algorithms} \vspace{.3in} Per S. Laursen\\ Department of Computer Science, University of Copenhagen\\ Universitetsparken 1, 2100 Copenhagen $\O$, Denmark\\ \tt{svalle@diku.dk} \end{center} \noindent {\bf Introduction.} Parallelization of the generic Simulated Annealing algorithm is a difficult task, due to the inherent sequential nature of the algorithm. A popular alternative approach has therefore been to perform a number of independent annealings - typically one on each available processor - augmented by some variant of periodic ``coordination'' of the annealings. The generic coordination strategy is to periodically gather all current solutions, and pick the best current solution as the new starting point for all of the annealings, which then continue with this best current solution as their new current solution. Parallelization strategies of this kind are usually denoted {\em division strategies} in the literature. \noindent {\bf Alternative Parallelization of Simulated Annealing.} The above strategy for selecting a new starting point for the continued annealings can be perceived as a very primitive type of Genetic Algorithm, using an extreme elitist-strategy. The risk of premature convergence due to the hard selection also seems latent. We have therefore conjectured that a more refined strategy for selection of new starting points may lead to improved performance, in addition to rendering global control of the search unnecessary, the latter being advantageous if the algorithm is to be ported to large distributed systems. We have seeked inspiration for such strategies from certain types of Parallel Genetic Algorithms, more specifically those versions based on the so-called {\em island model}. In this model, populations of solutions ``live'' in isolated territories (which could e.g. be individual processors), and can interact with other populations through migration and selection. That is, a solution may at some point migrate to a neighbouring population, and there compete on equal footing with the domestic solutions for a place in the next ``generation'' of solutions. This strategy can also be used as a framework for a division-strategy based Parallel Simulated Annealing algorithm: Each processor maintains a number of individuals (solutions), and tries to improve the quality of these by performing Simulated Annealing iterations on each individual. After some fixed number of iterations, a number of individuals migrate to a neighbouring target processor, and subsequently participate in a selection on this target processor. The new generation of individuals is then again submitted to a number of Simulated Annealing iterations, followed by migration to new target processors, etc.. {\bf Experiments and Main Results.} We have implemented three versions of parallel Simulated Annealing based on division strategies; a version using no coordination at all, a version using ``traditional'' global coordination, and a version using local coordination based on principles from the island model. All versions were implemented on a 16-processor network consisting of T800 Transputers. First, the performance of the three versions was compared, using an annealing scheme with a fixed number of iterations, and a fixed coordination intensity. The three versions were applied to QAPs of size 30,40,60,80 and 100. With respect to solution quality, the version using local coordination outperformed the version using no coordination at all, in all five cases. For the smaller test problems, the version using traditional global coordination was outperformed by {\em both} of the other versions, while it was able to tie the solution quality of the version using local coordination, when applied to. the largest test problems. With respect to running time, it was observed that the local coordination strategy induced only very marginal increases in the running time - as compared to the version using no coordination - while global coordination induced more severe increases. Second, we varied the coordination intensity, while still retaining the total number of iterations. Here we only applied the three versions to QAPs of size 30 and 100. For the small QAPs, we observed that global coordination was consistently outperformed by local coordination, no matter the choice of coordination intensity. For the large QAPs, the picture was less clear. Still, local coordination succeeded in obtaining the best overall solution quality. Running time was observed to increase roughly linear with coordination intensity, implying substantially prolonged running times for the global coordination version, when using intense coordination. This may however be partly attributed to a non-optimal implementation of the global coordination strategy as such. We do on the other hand not think that a better tuned implementation would alter the conclusions radically. Third, we de- and increased the total number of interactions. This can be done in two ways; either by varying the number of Simulated Annealing iterations performed between each migration phase - while retaining the number of migration phases - or vice versa. Again, QAPs of size 30 and 100 were used. For the small problems, we observed that global coordination was consistently outperformed by the two other versions, no matter the variation strategy or number of iterations. For the large problems, global coordination on the other hand outperformed the other versions when the total number of iterations was small, while being outperformed again for long annealings. When comparing local coordination to no coordination, it was observed that the no-coordination version needed roughly twice the number of iterations to match the solution quality produced when using local coordination. This could be taken as a semi- quantitative measure of the effectiveness of this strategy. {\bf Conclusions.} The results indicate that the proposed local coordination strategy generally outperforms the two other versions, and that the proposed local coordination strategy itself does not inflict any significant increase in running time, while rendering global control of the search unnecessary. Application of the algorithm to other problem types will take place in the near future, to verify whether these observations have more general validity. This research is financed by grants from the Danish Natural Science Research Council. \newpage \begin{center} {\Large \bf From the CRCW-PRAM to the Hypercube via the\\ CREW-PRAM and the EREW-PRAM\\ or In the Defense of the PRAM} \vspace{.3in} Zvi Galil\\ Columbia University \& Tel-Aviv University\\ \tt{galil@cs.columbia.edu} \end{center} General simulations of powerful versions of PRAM by weaker versions or by an hypercube may incur a loss in time and in optimality. Going through the example of string matching, we identify conditions where such losses are avoidable. Starting with a CRCW-PRAM algorithm, a modified version of a known algorithm, we first eliminate concurrent write, obtaining a CREW-PRAM algorithm, then eliminate concurrent read, obtaining an EREW-PRAM algorithm, and finally implement the latter on the hypercube. We obtain optimally fast algorithms for all these models that are better than the ones obtained via the general simulations for both the pattern preprocessing and the text search. In all cases but one (text search on the CREW-PRAM), such algorithms were not known before. Joint work with Artur Czumaj, Leszek Gasieniec and Wojciech Plandowski. \newpage \begin{center} {\Large \bf Speaker Index}\\ \end{center} \noindent Mike Atallah, Purdue \dotfill 31\\ John Board, Duke \dotfill 12\\ Lin Chen, USC \dotfill 11\\ Edith Cohen, AT\&T Bell Laboratories \dotfill 10\\ Richard Cole, NYU \dotfill 2\\ Yuefan Deng, SUNY at Stony Brook \dotfill 22\\ Rainer Feldmann, Paderborn \dotfill 37\\ Zvi Galil, Columbia U. \& Tel Aviv \dotfill 45\\ Phil Gibbons, AT\&T Bell Laboratories \dotfill 16\\ Mike Goodrich, Johns Hopkins \dotfill 27\\ Torben Hagerup, Max Planck Institute \dotfill 15\\ David Haglin, Mankato State U \dotfill 33\\ Joseph J\'{a}J\'{a}, Maryland \dotfill 36\\ Zvi Kedem, NYU \dotfill 14\\ Pierre Kelsen, U. British Columbia \dotfill 4\\ Phil Klein, Brown \dotfill 9\\ Dina Kravets, NJIT \dotfill 30\\ Per Laursen, Copenhagen \dotfill 43\\ Pangfeng Liu, DIMACS \dotfill 5\\ Yossi Matias, AT\&T Bell Laboratories \dotfill 28\\ Ernst Mayr, Munich \dotfill 32\\ Gary Miller, Carnegie-Mellon \dotfill 1\\ Victor Pan, CUNY \dotfill 6\\ Ian Parberry, North Texas U \dotfill 8\\ Jan Prins, U. North Carolina at CH \dotfill 20\\ Teresa Przytycka, Odense \dotfill24\\ Vijaya Ramachandran, U. Texas at Austin \dotfill 13\\ Rajeev Raman, Maryland \dotfill 23\\ Paul Spirakis, Patras \dotfill 18\\ Aravind Srinivasan \dotfill 42\\ Erik Tarnvik, Umea, Sweden \dotfill 41\\ Jesper Traff, Copenhagen \dotfill 34\\ Stefan Tschoke, Paderborn \dotfill 39\\ Vijay Vazirani, IIT Delhi \& DIMACS \dotfill 26\\ Uzi Vishkin, Maryland \& Tel Aviv \dotfill 3\\ Olof Widlund, NYU \dotfill 19\\ Roland Wunderling, Berlin \dotfill 7\\ \newpage \vspace{-1in} \begin{center} {\Large \bf Co-Author Index}\\ \end{center} \noindent Sandeep Bhatt \dotfill 5\\ Omer Berkman \dotfill 28\\ William J. Blanke \dotfill 12\\ G. Campbell \dotfill 22\\ Suresh Chari \dotfill 42\\ Danny Z. Chen \dotfill 31\\ Maxime Crochemore \dotfill 2\\ Artur Czumaj \dotfill 45\\ Nate Dean \dotfill 13\\ J. Diaz \dotfill 18\\ M. Eisenberg \dotfill 22\\ Stan Eisenstat \dotfill 1\\ William D. Elliott \dotfill 12\\ Zvi Galil \dotfill 2\\ Leszek Gasieniec \dotfill 2, 45\\ Phil Gibbons \dotfill 28\\ J. Glimm \dotfill 22\\ Mike Goodrich \dotfill 28\\ Daniel C. Gray \dotfill 12\\ Keith Gremban \dotfill 1\\ Steve Guattery \dotfill 1\\ Ziyad S. Hakura \dotfill 12\\ Ramesh Hariharan \dotfill 2\\ Tsan-sheng Hsu \dotfill 13\\ Simon Kahan \dotfill 4\\ L. Kirousis \dotfill 18\\ James F. Leathrum, Jr. \dotfill 12\\ R. L\"{u}ling \dotfill 39\\ Yossi Matias \dotfill 16\\ Peter Mills \dotfill 20\\ Burkhard Monien \dotfill 37, 39\\ S. Muthukrishnan \dotfill 2\\ Peter Mysliwietz \dotfill 37\\ Lars Nyland \dotfill 20\\ Kunsoo Park \dotfill 2\\ Wojciech Plandowski \dotfill 45\\ Greg Plaxton \dotfill 30\\ M. R\"{a}cke \dotfill 39\\ Sridhar Rajagopalan \dotfill 26\\ Vijaya Ramachandran \dotfill 16\\ John Reif \dotfill 20\\ Pankaj Rohatgi \dotfill 42\\ Wojciech Rytter \dotfill 2\\ Suleyman Cenk Sahinalp \dotfill 3\\ M. Serna \dotfill 18\\ Sairam Subramanian \dotfill 9\\ Dafna Talmor \dotfill 1\\ Shang-Hua Teng \dotfill 1\\ Bill Thurston \dotfill 1\\ J. Toran \dotfill 18\\ Steven Vavasis \dotfill 1\\ Uzi Vishkin \dotfill 23, 28\\ Y. Wang \dotfill 22\\ Ralph Werchner \dotfill 32\\ Q. Yu \dotfill 22\\ \end{document}