An Efficient Parallel Algorithm for the Layered Planar Monotone Circuit Value Problem

A planar monotone circuit (PMC) is a Boolean circuit that can be embedded in the plane and that contains only AND and OR gates. A layered PMC is a PMC in which all input nodes are in the external face, and the gates can be assigned to layers in such a way that every wire goes between gates in successive layers. Goldschlager, Cook and Dymond, and others have developed NC ² algorithms to evaluate a layered PMC when the output node is in the same face as the input nodes. These algorithms require a large number of processors (Ω(n ⁶ ), where n is the size of the input circuit). In this paper we give an efficient parallel algorithm that evaluates a layered PMC of size n in time using only a linear number of processors on an EREW PRAM. Our parallel algorithm is the best possible to within a polylog factor, and is a substantial improvement over the earlier algorithms for the problem. Received April 18, 1994; revised April 7, 1995.     

A Survey of Parallel and Distributed Algorithms for the Steiner Tree Problem

Given a set of input points, the Steiner Tree Problem (STP) is to find a minimum-length tree that connects the input points, where it is possible to add new points to minimize the length of the tree. Solving the STP is of great importance since it is one of the fundamental problems in network design, very large scale integration routing, multicast routing, wire length estimation, computational biology, and many other areas. However, the STP is NP-hard, which shatters any hopes of finding a polynomial-time algorithm to solve the problem exactly. This is why the majority of research has looked at finding efficient heuristic algorithms. Additionally, many authors focused their work on utilizing the ever-increasing computational power and developed many parallel and distributed methods for solving the problem. In this way we are able to obtain better results in less time than ever before. Here, we present a survey of the parallel and distributed methods for solving the STP and discuss some of their applications.     

Parallel Algorithms for Large-scale Nonlinear Optimization

Multi-step, multi-directional parallel variable metric (PVM) methods for unconstrained optimization problems are presented in this paper. These algorithms generate several VM directions at each iteration, dierent line search and scaling strategies are then applied in parallel along each search direction. In comparison to some serial VM methods, computational results show that a reduction of 200% or more in terms of number of iterations and function/gradient evaluations respectively could be achieved by the new parallel algorithm over a wide range of 63 test problems. In particular, when the complexity, or the size of the problem increases, greater savings could be achieved by the proposed parallel algorithm. In fact, the speedup factors gained by our PVM algorithms could be as high as 28 times for some test problems.     

Efficient Parallel Algorithms for Planar st-Graphs

Planar st -graphs find applications in a number of areas. In this paper we present efficient parallel algorithms for solving several fundamental problems on planar st -graphs. The problems we consider include all-pairs shortest paths in weighted planar st -graphs, single-source shortest paths in weighted planar layered digraphs (which can be reduced to single-source shortest paths in certain special planar st -graphs), and depth-first search in planar st -graphs. Our parallel shortest path techniques exploit the specific geometric and graphic structures of planar st -graphs, and involve schemes for partitioning planar st -graphs into subgraphs in a way that ensures that the resulting path length matrices have a monotonicity property [1], [2]. The parallel algorithms we obtain are a considerable improvement over the previously best known solutions (when they are applied to these st -graph problems), and are in fact relatively simple. The parallel computational models we use are the CREW PRAM and EREW PRAM.     

Optimal Parallel Algorithms for Quadtree Problems

In this paper we describe optimal processor-time parallel algorithms for set operations such as union, intersection, comparison on quadtrees. The algorithms presented in this paper run in O(log N) time using N/log N processors on a shared memory model of computation that allows concurrent reads or writes. Consequently they allow us to achieve optimal speedups using any number of processors up to N/log N. The approach can also be used to derive optimal processor-time parallel algorithms for weaker models of parallel computation.     

Parallel Algorithms for Maximal Acyclic Sets

Given a graph G=(V,E), the well-known spanning forest problem of G can be viewed as the problem of finding a maximal subset F of edges in G such that the subgraph induced by F is acyclic. Although this problem has well-known efficient NC algorithms, its vertex counterpart, the problem of finding a maximal subset U of vertices in G such that the subgraph induced by U is acyclic, has not been shown to be in NC (or even in RNC) and is not believed to be parallelizable in general. In this paper we present NC algorithms for solving the latter problem for two special cases. First, we show that, for a planar graph with n vertices, the problem can be solved in time with O(n) processors on an EREW PRAM. Second, we show that the problem is solvable in NC if the input graph G has only vertex-induced paths of length polylogarithmic in the number of vertices of G. As a consequence of this result, we show that certain natural extensions of the well-studied maximal independent set problem remain solvable in NC. Moreover, we show that, for a constant-degree graph with n vertices, the problem can be solved in time with O(n ² ) processors on an EREW PRAM. Received July 3, 1995; revised April 1, 1996.     

Selection Algorithms for Parallel Disk Systems

With the widening gap between processor speeds and disk access speeds, the I/O bottleneck has become critical. Parallel disk systems have been introduced to alleviate this bottleneck. In this paper we present deterministic and randomized selection algorithms for parallel disk systems. The algorithms to be presented, in addition to being asymptotically optimal, have small underlying constants in their time bounds and hence have the potential of being practical.     

Memetic Algorithms for Parallel Code Optimization

Discovering the optimum number of processors and the distribution of data on distributed memory parallel computers for a given algorithm is a demanding task. A memetic algorithm (MA) is proposed here to find the best number of processors and the best data distribution method to be used for each stage of a parallel program. Steady state memetic algorithm is compared with transgenerational memetic algorithm using different crossover operators and hill-climbing methods. A self-adaptive MA is also implemented, based on a multimeme strategy. All the experiments are carried out on computationally intensive, communication intensive, and mixed problem instances. The MA performs successfully for the illustrative problem instances.     

Scalable Parallel Algorithms for FPT Problems

Algorithmic methods based on the theory of fixed-parameter tractability are combined with powerful computational platforms to launch systematic attacks on combinatorial problems of significance. As a case study, optimal solutions to very large instances of the NP-hard vertex cover problem are computed. To accomplish this, an efficient sequential algorithm and various forms of parallel algorithms are devised, implemented, and compared. The importance of maintaining a balanced decomposition of the search space is shown to be critical to achieving scalability. Target problems need only be amenable to reduction and decomposition. Applications in high throughput computational biology are also discussed.     

并行数据库上的并行CMD_Join算法

并行数据库在多处理机之间的分布方法(简称数据分布方法)对并行数据操作算法的性能影响很大.如果在设计并行数据操作算法时充分利用数据分布方法的特点,可以得到十分有效的并行算法.本文研究如何充分利用数据分布方法的特点,设计并行数据操作算法的问题,提出了基于CMD多维数据分布方法的并行CMD_Join算法.理论分析和实验结果表明,并行CMD_Join算法的效率高于其它并行Join算法.     

Distribution-Independent Hierarchical Algorithms for the N-body Problem

The N-body problem is to simulate the motion of N particles under the influence of mutual force fields based on an inverse square law. Greengards algorithm claims to compute the cumulative force on each particle in O(N) time for a fixed precision irrespective of the distribution of the particles. In this paper, we show that Greengards algorithm is distribution dependent and has a lower bound of ­(N log 2 N) in two dimensions and ­(N log 4 N) in three dimensions. We analyze the Greengard and Barnes-Hut algorithms and show that they are unbounded for arbitrary distributions. We also present a truly distribution independent algorithm for the N-body problem that runs in O(N log N) time for any fixed dimension.     

Approximation Algorithms for the Unsplittable Flow Problem

We present approximation algorithms for the unsplittable flow problem (UFP) in undirected graphs. As is standard in this line of research, we assume that the maximum demand is at most the minimum capacity. We focus on the non-uniform capacity case in which the edge capacities can vary arbitrarily over the graph. Our results are: We obtain an approximation ratio for UFP, where n is the number of vertices, is the maximum degree, and is the expansion of the graph. Furthermore, if we specialize to the case where all edges have the same capacity, our algorithm gives an approximation. For certain strong constant-degree expanders considered by we obtain an approximation for the uniform capacity case. For UFP on the line and the ring, we give the first constant-factor approximation algorithms. All of the above results improve if the maximum demand is bounded away from the minimum capacity. The above results either improve upon or are incomparable with previously known results for these problems. The main technique used for these results is randomized rounding followed by greedy alteration, and is inspired by the use of this idea in recent work.     

Fast Algorithms for the Density Finding Problem

We study the problem of finding a specific density subsequence of a sequence arising from the analysis of biomolecular sequences. Given a sequence A=(a ₁,w ₁),(a ₂,w ₂),…,(a _n ,w _n ) of n ordered pairs (a _i ,w _i ) of numbers a _i and width w _i >0 for each 1≤i≤n, two nonnegative numbers ℓ, u with ℓ≤u and a number δ, the Density Finding Problem is to find the consecutive subsequence A(i ^*,j ^*) over all O(n ²) consecutive subsequences A(i,j) with width constraint satisfying ℓ≤w(i,j)=∑ _r=i ^j w _r ≤u such that its density is closest to δ. The extensively studied Maximum-Density Segment Problem is a special case of the Density Finding Problem with δ=∞. We show that the Density Finding Problem has a lower bound Ω(nlog n) in the algebraic decision tree model of computation. We give an algorithm for the Density Finding Problem that runs in optimal O(nlog n) time and O(nlog n) space for the case when there is no upper bound on the width of the sequence, i.e., u=w(1,n). For the general case, we give an algorithm that runs in O(nlog ² m) time and O(n+mlog m) space, where and w _min=min  _r=1 ⁿ w _r . As a byproduct, we give another O(n) time and space algorithm for the Maximum-Density Segment Problem. Grants NSC95-2221-E-001-016-MY3, NSC-94-2422-H-001-0001, and NSC-95-2752-E-002-005-PAE, and by the Taiwan Information Security Center (TWISC) under the Grants NSC NSC95-2218-E-001-001, NSC95-3114-P-001-002-Y, NSC94-3114-P-001-003-Y and NSC 94-3114-P-011-001.     

Approximation Algorithms for the Class Cover Problem

We introduce the class cover problem, a variant of disk cover with forbidden regions, with applications to classification and facility location problems. We prove similar hardness results to disk cover. We then present a polynomial-time approximation algorithm for class cover that performs within a ln?n+1 factor of optimal, which is nearly tight under standard hardness assumptions. In the special case that the points lie in a d-dimensional space with Euclidean norm, for some fixed constant d, we obtain a polynomial time approximation scheme.     

基于阶段并行模型的算法设计研究

NOWs正成为并行计算领域的一个新的发展热点,以太网构成的微机集群系统是NOWs的一种重要实现形式。阶段并行模型是BSP模型的改进,它更接近于表述实际的机器行为,同时具有编程简单、独立于体系结构和执行性能可预测等特点。文章研究了群集系统中阶段并行模型上的并行算法设计,以FFT算法为例,进行了设计和分析,并给出了测试结果。     

Combinatorial Algorithms for the Unsplittable Flow Problem

We provide combinatorial algorithms for the unsplittable flow problem (UFP) that either match or improve the previously best results. In the UFP we are given a (possibly directed) capacitated graph with n vertices and m edges, and a set of terminal pairs each with its own demand and profit. The objective is to connect a subset of the terminal pairs each by a single flow path subject to the capacity constraints such that the total profit of the connected pairs is maximized.We consider three variants of the problem. First is the classical UFP in which the maximum demand is at most the minimum edge capacity. It was previously known to have an O(√m) approximation algorithm; the algorithm is based on the randomized rounding technique and its analysis makes use of the Chernoff bound and the FKG inequality.We provide a combinatorial algorithm that achieves the same approximation ratio and whose analysis is considerably simpler. Second is the extended UFP in which some demands might be higher than edge capacities. Our algorithm for this case improves the best known approximation ratio. We also give a lower bound that shows that the extended UFP is provably harder than the classical UFP. Finally, we consider the bounded UFP in which the maximum demand is at most 1/K times the minimum edge capacity for some K > 1. Here we provide combinatorial algorithms that match the currently best known algorithms. All of our algorithms are strongly polynomial and some can even be used in the online setting.     

Algorithms for the Homogeneous Set Sandwich Problem

A homogeneous set is a non-trivial module of a graph, i.e. a non-empty, non-unitary, proper subset of a graph's vertices such that all its elements present exactly the same outer neighborhood. Given two graphs the Homogeneous Set Sandwich Problem (HSSP) asks whether there exists a sandwich graph which has a homogeneous set. In 2001 Tang et al. published an all-fast algorithm which was recently proven wrong, so that the HSSP's known upper bound would have been reset thereafter at the former determined by Cerioli et al. in 1998. We present, notwithstanding, new deterministic algorithms which have it established at We give as well two even faster randomized algorithms, whose simplicity might lend them didactic usefulness. We believe that, besides providing efficient easy-to-implement procedures to solve it, the study of these new approaches allows a fairly thorough understanding of the problem.