Design and Performance Evaluation of Sequence Partition Algorithms

Tradeoffs between time complexities and solution optimalities are important when selecting algorithms for an NP-hard problem in different applications. Also, the distinction between theoretical upper bound and actual solution optimality for realistic instances of an NP-hard problem is a factor in selecting algorithms in practice. We consider the problem of partitioning a sequence of n distinct numbers into minimum number of monotone （increasing or decreasing） subsequences. This problem is NP-hard and the number of monotone subsequences can reach [√2n＋1/1-1/2]in the worst case. We introduce a new algorithm, the modified version of the Yehuda-Fogel algorithm, that computes a solution of no more than [√2n＋1/1-1/2]monotone subsequences in O（n^1.5） time. Then we perform a comparative experimental study on three algorithms, a known approximation algorithm of approximation ratio 1.71 and time complexity O（n^3）, a known greedy algorithm of time complexity O（n^1.5 log n）, and our new modified Yehuda-Fogel algorithm. Our results show that the solutions computed by the greedy algorithm and the modified Yehuda-Fogel algorithm are close to that computed by the approximation algorithm even though the theoretical worst-case error bounds of these two algorithms are not proved to be within a constant time of the optimal solution. Our study indicates that for practical use the greedy algorithm and the modified Yehuda-Fogel algorithm can be good choices if the running time is a major concern.     

Engineering the Divide-and-Conquer Closest Pair Algorithm

We improve the famous divide-and-conquer algorithm by Bentley and Shamos for the planar closest-pair problem. For n points on the plane, our algorithm keeps the optimal O（n log n） time complexity and, using a circle-packing property, computes at most 7n/2 Euclidean distances, which improves Ge et al.＇s bound of （3n log n）/2 Euclidean distances. We present experimental results of our comparative studies on four different versions of the divide-and-conquer closest pair algorithm and propose two effective heuristics.     

高效的求解TSP问题的近似算法

提出了一种基于矩阵变换的方法,将n阶TSP问题近似转化为n-1阶TSP问题,然后用递归运算得出最后解。此算法的时间复杂度为O（n³）。而后又对此算法做了进一步的改进,近似度有很大提高但时间复杂度增加为O（n⁴）。经过实验表明,此类算法求解的近似度很高,尤其是在满足三角不等式的问题中,误差更低。利用TSPLIB数据库中的数据进行测试,得到的结果误差最多不超过10%。     

A systolic-based parallel bin packing algorithm

A systolic based parallel approximation algorithm that obtains solutions to the I-D bin packing problem is presented. The algorithm has an asymptotic error bound of 1.5 and time complexity O(n). An experimental study demonstrates that the heuristic offers improved packing and execution performance over parallelizations of two well-known serial algorithms     

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     

Improved Approximate Detection of Duplicates for Data Streams Over Sliding Windows

Detecting duplicates in data streams is an important problem that has a wide range of applications. In general,precisely detecting duplicates in an unbounded data stream is not feasible in most streaming scenarios,and,on the other hand,the elements in data streams are always time sensitive. These make it particular significant approximately detecting duplicates among newly arrived elements of a data stream within a fixed time frame. In this paper,we present a novel data structure,Decaying Bloom Filter(DBF),as an extension of the Counting Bloom Filter,that effectively removes stale elements as new elements continuously arrive over sliding windows. On the DBF basis we present an efficient algorithm to approximately detect duplicates over sliding windows. Our algorithm may produce false positive errors,but not false negative errors as in many previous results. We analyze the time complexity and detection accuracy,and give a tight upper bound of false positive rate. For a given space G bits and sliding window size W,our algorithm has an amortized time complexity of O((G/W))~(1/2). Both analytical and experimental results on synthetic data demonstrate that our algorithm is superior in both execution time and detection accuracy to the previous results.     

Learning concepts in parallel based upon the strategy of versionspace

Applies the technique of parallel processing to concept learning. A parallel version-space learning algorithm based upon the principle of divide-and-conquer is proposed. Its time complexity is analyzed to be O(k log₂n) with n processors, where n is the number of given training instances and k is a coefficient depending on the application domains. For a bounded number of processors in real situations, a modified parallel learning algorithm is then proposed. Experimental results are then performed on a real learning problem, showing that our parallel learning algorithm works, and being quite consistent with the results of theoretical analysis. We conclude that when the number of training instances is large, it is worth learning in parallel because of its faster execution     

基因组Translocation排序问题的改进多项式算法

该文给出基因组Transhocation排序问题的一个改进多项式算法，原算法所有存储空间O（n)，时间复杂度为O(n^3)，文中改进算法仍采用O(n)存储空间，时间复杂度为O(n^2logn),具体地，将计算Translocation距离的时间复杂度由O(n^3)改进为O(n^2),将计算Translocation序列的时间复杂度由O(n^3)改进为O(n^2logn).     

快速霍夫变换算法

二值图像的直线检测过程中,标准霍夫变换算法的计算量为O（N^3)。该文提出一种快速霍夫变换算法,其计算量仅为O（N^2log2N)。该快速算法可以并行实现;处理器阵列规模为O（N^2)时,计算量为O（log2N)。文中还分析得到快速算法的误差上界,并提出一种改进的快速霍夫变换算法以获得更高的计算精度。最后,给出算法的数值算例。理论分析及数值算例都表明,该文的快速霍夫变换算法在直线检测过程中有着更高的计算效率,并且具有良好的计算精度。     

An improved algorithm for implication testing involving arithmeticinequalities

Implication testing of arithmetic inequalities has been widely used in different areas in database systems and has received extensive research as well. Klug and Ullman (A. Klug, 1988; and J.D. Ullman, 1989) proposed an algorithm that determines whether S implies T, where T and S consist of inequalities of form (X op Y), X and Y are two variables, and opϵ {=<, ⩽, ≠, >, ⩾}. The complexity of the algorithm is O(n³), where n is the number of inequalities in S. We reduce the problem to matrix multiplication, thus improving the time bound to O(n^2.376). We also demonstrate an O(n² ) algorithm if the number of inequalities in T is bounded by O(n). Since matrix multiplication has been well studied, our reduction allows the possibility of directly adopting many practical results for managing matrices and their operations, such as parallel computation and efficient representation of sparse matrices     

线对象邻接关系快速重构算法

给定向量化坐标,计算n个线对象两两邻接关系,普通算法时间复杂度为O(n*n);理论最好时间复杂度为O(C),其中C是邻接关系的基数。基于散列桶,给出了建立线对象邻接关系的快速算法,其平均时间复杂度为O(n(1+1/r)),r为算法分配的桶数量与n的比,空间复杂度为O(n)。证明了若不允许使用额外空间,则不可能使用排序算法解决该问题;给出了允许使用额外空间条件下的两遍排序算法,时间复杂度为O(n(lbn+1+2/r))。应用表明快速算法比普通算法速度提高1~3个数量级。     

一种节省空间的排序算法

目前报道的一些排序算法，空间复杂度都比较大．提出了一种改进其空间复杂度的方法，其特点是算法简单、稳定，时间复杂度为O(n^2)，空间复杂度为2n，达到下界．与传统的排序算法用变量与变量比较的思路不同，本文提出的是一种用变量与其分布区间进行比较的新思路．本算法特别适合那些范围确定且分布基本均匀的待排数据，也适合一般数据对象的排序．     

兑换零钱问题的动态规划算法研究

兑换零钱问题是一个求解组合优化的问题。首先对兑换零钱问题进行了分析,证明了该问题满足动态规划的最优化原理,并给出了其动态规划解法;然后对本算法进行了时间复杂性和空间复杂性分析,得到时间复杂性由通常的动态规划算法的O（Mn2）提高到本算法的O（n3）,空间复杂性由通常的动态规划算法的O（Mn）提高到本算法的O（n2）,因此效率有了较大提高。最后通过实验对算法进行验证,证明了算法的高效性。该算法可以广泛应用于自动售货机。     

汉诺塔非递归算法研究

汉诺塔(Tower of Hanoi)问题是求在三个柱子之间移动圆盘的方法,它是递归程序设计的经典例子,已经证明其时间复杂度下限是O(2n),空间复杂度是O(n),实际使用时很容易溢出.给出汉诺塔问题的两个非递归算法:解集递推法和解集树法.解集递推法的时间复杂度和空间复杂度都是O(2n),该算法空间复杂度很大,无法实际使用,提出该算法的目的是为了引出解集树法.解集树法可以计算出指定的任意一步移动方法,时间复杂度和空间复杂度分别是O(n*2n)和O(1).并证明了汉诺塔问题的空间复杂度下限是O(1).     

CIM algorithm for approximating three-dimensional polygonal curves

The polygonal approximation problem is a primary problem in computer graphics,pattern recognition,CAD/CAM,etc.In R^2,the cone intersection method(CIM) is one of the most efficient algorithms for approximating polygonal curves,With CIM Eu and Toussaint,by imposing an additional constraint and changing the given error criteria,resolve the three-dimensional weighted minimum number polygonal approximation problem with the parallel-strip error criterion(PS-WMN)under L2 norm.In this paper,without any additional constraint and change of the error criteria,a CIM solution to the same problem with the line segment error criterion(LS-WMN)is presented,which is more frequently encountered than the PS-WMN is .Its time complexity is O(n^3),and the space complexity is O(n^2) .An approximation algorithm is also presented,which takes O(n^2) time and O(n) space.Results of some examples are given to illustrate the efficiency of these algorithms.     

Generalized algorithm for parallel sorting on product networks

We generalize the well-known odd-even merge sorting algorithm, originally due to Batcher (1968), and show how this generalized algorithm can be applied to sorting on product networks. If G is an arbitrary factor graph with N nodes, its r-dimensional product contains N^r nodes. Our algorithm sorts N^r keys stored in the r-dimensional product of G in O(r^rF(N)) time, where F(N) depends on G. We show that, for any factor graph G, F(N) is, at most, O(N), establishing an upper bound of O(r² N) for the time complexity of sorting N^r keys on any product network. For product networks with bounded r(e.g. for grids), this leads to the asymptotic complexity of O(N) to sort N^r keys, which is optimal for several instances of product networks. There are factor graphs for which F(N)=O(log² N), which leads to the asymptotic running time of O(log² N) to sort N^r keys. For networks with bounded N (e.g. in the hypercube N=2, fixed), the asymptotic complexity becomes O(r²). We show how to apply the algorithm to several cases of well-known product networks, as well as others introduced recently. We compare the performance of our algorithm to well-known algorithms developed specifically for these networks, as well as others. The result of these comparisons led us to conjecture that the proposed algorithm is probably the best deterministic algorithm that can be found in terms of the low asymptotic complexity with a small constant     

Optimal parallel algorithms for finding proximate points, withapplications

Consider a set P of points in the plane sorted by the x-coordinate. A point p in P is said to be a proximate point if there exists a point q on the x-axis such that p is the closest point to q over all points in P. The proximate point problem is to determine all the proximate points in P. Our main contribution is to propose optimal parallel algorithms for solving instances of size n of the proximate points problem. We begin by developing a work-time optimal algorithm running in O(log log n) time and using n/loglogn Common-CRCW processors. We then go on to show that this algorithm can be implemented to run in O(log n) time using n/logn EREW processors. In addition to being work-time optimal, our EREW algorithm turns out to also be time-optimal. Our second main contribution is to show that the proximate points problem finds interesting, and quite unexpected, applications to digital geometry and image processing. As a first application, we present a work-time optimal parallel algorithm for finding the convex hull of a set of n points in the plane sorted by x-coordinate; this algorithm runs in O(log log n) time using n/logn Common-CRCW processors. We then show that this algorithm can be implemented to run in O(log n) time using n/logn EREW processors. Next, we show that the proximate points algorithms afford us work-time optimal (resp, time-optimal) parallel algorithms for various fundamental digital geometry and image processing problems     

挖掘滑动窗口中的数据流频繁项算法

滑动窗口是一种对最近一段时间内的数据进行挖掘的有效的技术,本文提出一种基于滑动窗口的流数据频繁项挖掘算法.算法采用了链表队列策略大大简化了算法,提高了挖掘的效率.对于给定的阈值S、误差ε和窗口长度n,算法可以检测在窗口内频度超过Sn的数据流频繁项,且使误差在εn以内.算法的空间复杂度为O(ε-1),对每个数据项的处理和查询时间均为O(1).在此基础上,我们还将该算法进行了扩展,可以通过参数的变化得到不同的流数据频繁项挖掘算法,使得算法的时间和空间复杂度之间得到调节.通过大量的实验证明,本文算法比其它类似算法具有更好的精度以及时间和空间效率.     

Mobile Search for a Black Hole in an Anonymous Ring

In this paper we address the problem of mobile agents searching for a highly harmful item (called a black hole) in a ring network. The black hole is a stationary process that destroys visiting agents upon their arrival without leaving any observable trace of such a destruction. The task is to have at least one surviving agent able to unambiguously report the location of the black hole. We consider different scenarios and in each situation we answer some computational as well as complexity questions. We first consider agents that start from the same home base (co-located). We prove that two such agents are necessary and sufficient to locate the black hole; in our algorithm the agents perform O(n log n) moves (where n is the size of the ring) and we show that such a bound is optimal. We also consider time complexity and show how to achieve the optimal bound of 2n - 4 units of time using n - 1 agents. We generalize our technique to establish a trade-off between time and number of agents. We then consider the case of agents that start from different home bases (dispersed) and we show that if the ring is oriented, two dispersed agents are still necessary and sufficient. Also in this case our algorithm is optimal in terms of number of moves (Θ(n log n)). We finally show that if the ring is unoriented, three agents are necessary and sufficient; an optimal algorithm follows from the oriented case.     

背包问题无存储冲突的并行三表算法

背包问题属于经典的NP难问题，在信息密码学和数论等研究中具有极重要的应用，将求解背包问题著名的二表算法的设计思想应用于三表搜索中，利用分治策略和无存储冲突的最优归并算法，提出一种基于EREW-SIMD共享存储模型的并行三表算法，算法使用O（2^n/4）个处理机单元和O（2^3n/8）的共享存储空间，在O（2^3n/8）时间内求解n维背包问题．将提出的算法与已有文献结论进行的对比分析表明：文中算法明显改进了现有文献的研究结果，是一种可在小于O（2^n/2）的硬件资源上，以小于O（2n/2）的计算时问求解背包问题的无存储冲突并行算法。