Parallel clustering algorithms

Clustering techniques play an important role in exploratory pattern analysis, unsupervised learning and image segmentation applications. Many clustering algorithms, both partitional clustering and hierarchical clustering, require intensive computation, even for a modest number of patterns. This paper presents two parallel clustering algorithms. For a clustering problem with N = 2ⁿ patterns and M = 2^m features, the time complexity of the traditional partitional clustering algorithm on a single processor computer is O(MNK), where K is the number of clusters. The proposed algorithm on anSIMD computer with MN processors has a time complexity O(K(n + m)). The time complexity of the proposed single-link hierarchical clustering algorithm is reduced from O(MN²) of the uniprocessor algorithm to O(nN) with MN processors.     

On space-efficient algorithms for certain NP-complete problems

Some recent results claimed the existence of a class of algorithms for certain NP-complete problems, with running time O(n^{1g k} 2^n/2) and storage requirements O(k 2^n/k), for 2 kn. In this note we show that those results do not hold, implying that an algorithm with time O(n 2^n/2) and space O(2^n/4) is still the best-known solution for such class of NP-complete problems.     

A parallel two-list algorithm for the knapsack problem

An n-element knapsack problem has 2ⁿ possible solutions to search over, so a task which can be accomplished in 2″ trials if an exhaustive search is used. Due to the exponential time in solving the knapsack problem, the problem is considered to be very hard. In the past decade, much effort has been done in order to find techniques which could lead to practical algorithms with reasonable running time. In 1994, Chang et al. proposed a brilliant parallel algorithm, which needs O(2^n/8) processors to solve the knapsack problem in O(2^n/2) time; that is, the cost of Chang et al.'s parallel algorithm is O(2^5n/8). In this paper, we propose a parallel algorithm to improve Chang et al.'s parallel algorithm by reducing the time complexity to be O(2^3n/8) under the same O(2^n/8) processors available. Thus, the proposed parallel algorithm has a cost of O(2^n/2). It is an improvement over previous literature. We believe that the proposed parallel algorithm is pragmatically feasible at the moment when multiprocessor systems become more and more popular.     

Learning counting functions with queries

We investigate the problem of learning disjunctions of counting functions, which are general cases of parity and modulo functions, with equivalence and membership queries. We prove that, for any prime number p, the class of disjunctions of integer-weighted counting functions with modulus p over the domain Z_qⁿ (or Zⁿ) for any given integer q 2 is polynomial time learnable using at most n + 1 equivalence queries, where the hypotheses issued by the learner are disjunctions of at most n counting functions with weights from Z_p. In general, a counting function may have a composite modulus. We prove that, for any given integer q 2, over the domain Z₂ⁿ, the class of read-once disjunctions of Boolean-weighted counting functions with modulus q is polynomial-time learnable with only one equivalence query and O(n^q) membership queries.     

Boundary matching algorithm for connected component labelling using linear quadtrees

A computationally fast top-down recursive algorithm for connected component labelling using linear quadtrees is presented. The input data structure used is a linear quadtree representing only black leaf nodes. The boundary matching approach used ensures that at most two adjacencies of any black leaf node are considered. Neighbour searching is carried out within restricted subsets of the input quadtree. The time and space complexities of the algorithm are O(Bn) and O(B) respectively for a linear quadtree with B black leaves constructed from a binary array of size 2ⁿ × 2ⁿ. Simulations show the algorithm to be twice as fast as an existing algorithm that uses an identical input data structure. The top-down algorithm presented can also be used to efficiently generate a linear quadtree representing all nodes — ‘grey’, ‘black’ and ‘white’ — in preorder when given an input linear quadtree representing only ‘black’ leaf nodes. The boundary matching algorithm is computationally fast and has low static and dynamic storage costs, making it useful for applications where linear quadtrees are held in main memory.     

Distribution of black nodes at various levels in a linear quadtree

The distribution of black leaf nodes at each level of a linear quadtree is of significant interest in the context of estimation of time and space complexities of linear quadtree based algorithms. The maximum number of black nodes of a given level that can be fitted in a square grid of size 2ⁿ × 2ⁿ can readily be estimated from the ratio of areas. We show that the actual value of the maximum number of nodes of a level is much less than the maximum obtained from the ratio of the areas. This is due to the fact that the number of nodes possible at a level k, 0≤k≤n − 1, should consider the sum of areas occupied by the actual number of nodes present at levels k + 1, k + 2, …, n − 1.     

Extended Games–Chan algorithm for the 2-adic complexity of FCSR-sequences

Binary sequences generated by feedback shift registers with carry operation (FCSR) share many of the important properties enjoyed by sequences generated by linear feedback shift registers. We present an FCSR analog of the (extended) Games–Chan algorithm, which efficiently determines the linear complexity of a periodic binary sequence with period length T = 2ⁿ or pⁿ, where p is an odd prime and 2 is a primitive element modulo p². The algorithm to be presented yields an upper bound for the 2-adic complexity, an FCSR analog of the linear complexity, of a pⁿ-periodic binary sequence.     

An exact exponential time algorithm for counting bipartite cliques

We present a simple exact algorithm for counting bicliques of given size in a bipartite graph on n   vertices. We achieve running time of O(1.2491ⁿ)$O({1.2491}^n)$, improving upon known exact algorithms for finding and counting bipartite cliques.     

Four-moduli set (2, 2−1, 2+2−1, 2+2−1) simplies the residue to binary converters based on CRT II

A multiplier-free residue to binary converter architecture based on the Chinese remainder theorem II (CRT II) [1] is presented. The paper also includes a binary to residue converter. This is achieved by introducing a new moduli set (2, 2ⁿ − 1, 2ⁿ + 2ⁿ⁻¹ − 1, 2ⁿ⁺¹ + 2ⁿ − 1) for RNS application. The complexity of conversion has been greatly reduced using CRT II with the new moduli set. The proposed hardware architecture replaces the necessary multiplication by shift-left operations. A similar hardware architecture is presented for the binary to residue conversion.     

Solving Computation Slicing Using Predicate Detection

Given a distributed computation and a global predicate, predicate detection involves determining whether there exists at least one consistent cut (or global state) of the computation that satisfies the predicate. On the other hand, computation slicing is concerned with computing the smallest subcomputation (with the least number of consistent cuts) that contains all consistent cuts of the computation satisfying the predicate. In this paper, we investigate the relationship between predicate detection and computation slicing and show that the two problems are actually equivalent. Specifically, given an algorithm to detect a predicate b in a computation C, we derive an algorithm to compute the slice of C with respect to b. The time complexity of the (derived) slicing algorithm is O(n|E|T), where n is the number of processes, E is the set of events, and O(T) is the time complexity of the detection algorithm. We discuss how the "equivalence" result of this paper can be utilized to derive a faster algorithm for solving the general predicate detection problem in many cases. Slicing algorithms described in our earlier papers are all offline in nature. In this paper, we also present two online algorithms for computing the slice. The first algorithm can be used to compute the slice for a general predicate. Its amortized time complexity is O(n(c + n)T) per event, where c is the average concurrency in the computation and O(T) is the time complexity of the detection algorithm. The second algorithm can be used to compute the slice for a regular predicate. Its amortized time complexity is only O(n²) per event.     

Integration of polynomials over n-dimensional linear polyhedra

This paper is concerned with explicit integration formulae for computing integrals of n-variate polynomials over linear polyhedra in n-dimensional space ⁿ. Two different approaches are discussed; the first set of formulae is obtained by mapping the polyhedron in n-dimensional space ⁿ into a standard n-simplex in ⁿ, while the second set of formulae is obtained by reducing the n-dimensional integral to a sum of n − 1 dimensional integrals which are n + 1 in number. These formulae are followed by an application example for which we have explained the detailed computational scheme. The symbolic integration formulae presented in this paper may lead to an easy and systematic incorporation of global properties of solid objects, such as, for example, volume, centre of mass, moments of inertia etc., required in engineering design problems.     

All nearest smaller values on the hypercube

Given a sequence of n elements, the All Nearest Smaller Values (ANSV) problem is to find, for each element in the sequence, the nearest element to the left (right) that is smaller, or to report that no such element exists. Time and work optimal algorithms for this problem are known on all the PRAM models but the running time of the best previous hypercube algorithm is optimal only when the number of processors p satisfies 1⩽p⩽n/((lg³ n)(lg lg n)²). In this paper, we prove that any normal hypercube algorithm requires Ω(M) processors to solve the ANSV problem in O(lg n) time, and we present the first normal hypercube ANSV algorithm that is optimal for all values of n and p. We use our ANSV algorithm to give the first O(lg n)-time n-processor normal hypercube algorithms for triangulating a monotone polygon and for constructing a Cartesian tree     

The unbounded single machine parallel batch scheduling problem with family jobs and release dates to minimize makespan

In this paper we consider the unbounded single machine parallel batch scheduling problem with family jobs and release dates to minimize makespan. We show that this problem is strongly NP-hard, and give an O(n(n/m+1)^m) time dynamic programming algorithm and an O(mk^k+1P^2k−1) time dynamic programming algorithm, where n is the number of jobs, m is the number of families, k is the number of distinct release dates and P is the sum of the processing times of all families. We further give a heuristic with a performance ratio 2. We also give a polynomial-time approximation scheme for the problem.     

求解SAT问题的拟人退火算法

该文利用一个简单的变换，将可满足性（SAT）问题转换为一个求相应目标函数最小值的优化问题，提出了一种用于跳出局部陷阱的拟人策略，基于模拟退火算法和拟人策略，为SAT问题的高效近注解得出了拟人退火算法（PA），该方法不仅具有模拟退火算法的全局收敛性质，而且具有一定的并行性，继承性。数值实验表明，对于本文随机产生的测试问题例，采用拟人策略的模拟退火算法的结果优于局部搜索算法，模拟退火算法以及近来国际上流行的WALKSAT算法，因此拟人退火算法是可行的和有效的。     

Parallel algorithms for relational coarsest partition problems

Relational Coarsest Partition Problems (RCPPs) play a vital role in verifying concurrent systems. It is known that RCPPs are P-complete and hence it may not be possible to design polylog time parallel algorithms for these problems. In this paper, we present two efficient parallel algorithms for RCPP in which its associated label transition system is assumed to have m transitions and n states. The first algorithm runs in O(n^1+ϵ) time using m/n^ϵ CREW PRAM processors, for any fixed ϵ<1. This algorithm is analogous to and optimal with respect to the sequential algorithm of P.C. Kanellakis and S.A. Smolka (1990). The second algorithm runs in O(n log n) time using m/n CREW PRAM processors. This algorithm is analogous to and nearly optimal with respect to the sequential algorithm of R. Paige and R.E. Tarjan (1987)     

Fast and simple algorithms to count the number of vertex covers in an interval graph

This study provides the following fast and simple algorithms for an interval graph: (1) an algorithm for counting the number of vertex covers, and (2) an algorithm for counting the number of minimal vertex covers.     

On the state complexity of reversals of regular languages

We compare the number of states between minimal deterministic finite automata accepting a regular language and its reversal (mirror image). In the worst case the state complexity of the reversal is 2ⁿ for an n-state language. We present several classes of languages where this maximal blow-up is actually achieved and study the conditions for it. In the case of finite languages the maximal blow-up is not possible but still a surprising variety of different growth types can be exhibited.     

A new parallel and distributed shortest path algorithm forhierarchically clustered data networks

This paper presents new efficient shortest path algorithms to solve single origin shortest path problems (SOSP problems) and multiple origins shortest path problems (MOSP problems) for hierarchically clustered data networks. To solve an SOSP problem for a network with n nodes, the distributed version of our algorithm reaches the time complexity of O(log(n)), which is less than the time complexity of O(log ² (n)) achieved by the best existing algorithm. To solve an MOSP problem, our algorithm minimizes the needed computation resources, including computation processors and communication links for the computation of each shortest path so that we can achieve massive parallelization. The time complexity of our algorithm for an MOSP problem is O(m log(n)), which is much less than the time complexity of O(M log² (0)) of the best previous algorithm. Here, M is the number of the shortest paths to be computed and m is a positive number related to the network topology and the distribution of the nodes incurring communications, m is usually much smaller than M. Our experiment shows that m is almost a constant when the network size increases. Accordingly, our algorithm is significantly faster than the best previous algorithms to solve MOSP problems for large data networks     

Efficient algorithms for globally optimal trajectories

We present serial and parallel algorithms for solving a system of equations that arises from the discretization of the Hamilton-Jacobi equation associated to a trajectory optimization problem of the following type. A vehicle starts at a prespecified point x_o and follows a unit speed trajectory x(t) inside a region in ℛ^m until an unspecified time T that the region is exited. A trajectory minimizing a cost function of the form ∫₀^T r(x(t))dt+q(x(T)) is sought. The discretized Hamilton-Jacobi equation corresponding to this problem is usually solved using iterative methods. Nevertheless, assuming that the function r is positive, we are able to exploit the problem structure and develop one-pass algorithms for the discretized problem. The first algorithm resembles Dijkstra's shortest path algorithm and runs in time O(n log n), where n is the number of grid points. The second algorithm uses a somewhat different discretization and borrows some ideas from a variation of Dial's shortest path algorithm (1969) that we develop here; it runs in time O(n), which is the best possible, under some fairly mild assumptions. Finally, we show that the latter algorithm can be efficiently parallelized: for two-dimensional problems and with p processors, its running time becomes O(n/p), provided that p=O(√n/log n)     

Embedding a complete binary tree into the supercube

Consider a complete binary tree with 2ⁿ − 1 nodes and a supercube with the same number of nodes. We present a new embedding method to map the complete binary tree into the supercube with dilation 1. Our simple mapping method is quite competitive with the previous result.