一类可分离SAT问题的O(1.890n)精确算法

布尔可满足性问题（SAT）是指对于给定的布尔公式,是否存在一个可满足的真值指派.这是第1个被证明的NP完全问题,一般认为不存在多项式时间算法,除非P=NP.学者们大都研究了子句长度不超过k的SAT问题（k-SAT）,从全局搜索到局部搜索,给出了大量的相对有效算法,包括随机算法和确定算法.目前,最好算法的时间复杂度不超过O（（2-2/k）ⁿ）,当k=3时,最好算法时间复杂度为O（1.308ⁿ）.而对于更一般的与子句长度k无关的SAT问题,很少有文献涉及.引入了一类可分离SAT问题,即3-正则可分离可满足性问题（3-RSSAT）,证明了3-RSSAT是NP完全问题,给出了一般SAT问题3-正则可分离性的O（1.890ⁿ）判定算法.然后,利用矩阵相乘算法的研究成果,给出了3-RSSAT问题的O（1.890ⁿ）精确算法,该算法与子句长度无关.     

矩阵条件数及高斯算法平滑分析的进一步研究

算法的复杂度平滑分析是对许多算法在实际应用中很有效但其最坏情况复杂度却很糟这一矛盾给出的更合理的解释.高性能计算机被广泛用于求解大规模线性系统及大规模矩阵的分解.求解线性系统的最简单且容易实现的算法是高斯消元算法(高斯算法).用高斯算法求解n个方程n个变量的线性系统所需要的算术运算次数为O(n³).如果这些方程中的系数用m位表示,则最坏情况下需要机器位数mn位来运行高斯算法.这是因为在消元过程中可能产生异常大的中间项.但大量的数值实验表明,在实际应用中,需要如此高的精度是罕见的.异常大的矩阵条件数和增长因子是导致矩阵A病态,继而导致解的误差偏大的主要根源.设-A为任意矩阵,A是-A受到微小幅度的高斯随机扰动所得到的随机矩阵,方差σ²≤1.Sankar等人对矩阵A的条件数及增长因子进行平滑分析,证明了Pr[K(A)≥α]≤(3.64n(1+4√log(α)))/ασ.在此基础上证明了运行高斯算法输出具有m位精度的解所需机器位数的平滑复杂度为m+71og₂(n)+3log₂(1/σ)+log₂log₂n+7.在上述结果的证明过程中存在错误,将其纠正后得到以下结果:m+71og₂n+3log₂(1/σ)+4√2+log₂n+log₂(1/σ)+7.367.通过构造两个分别关于矩阵范数和随机变量乘积的不等式,将关于矩阵条件数的平滑分析结果简化到Pr[K(A)≥α]≤(6√2n²)/α·σ.部分地解决了Sankar等人提出的猜想:Pr[K(A)≥α]≤O(n/α·σ).并将运行高斯算法输出具有m位精度的解所需机器位数的平滑复杂度降低到m+81og₂n+3log₂(1/σ)+7.实验结果表明,所得到的平滑复杂度更好.     

无存储器冲突的并行快速排序算法*

本文在一个EREW PRAM(exclusive read exclusive write paralled random accessmachine)上提出一个并行快速排序算法，这个算法用k个处理器可将n个项目在平均O((n/k+logn)logn)时间内排序．所以平均来说算法的时间和处理器数量的乘积对任何k≤n/logn是 O(nlogn)．     

P2-Packing问题参数算法的改进

P₂-Packing问题是一个典型的NP难问题.目前这个问题的最好结果是时间复杂度为O^*(2^5.301k)的参数算法,其核的大小为15k.通过对P₂-packing问题的结构作进一步分析,提出了改进的核心化算法,得到大小为7k的核,并在此基础上提出了一种时间复杂度为O^*(2^4.142k)的参数算法,大幅度改进了目前文献中的最好结果.     

三维空间中的最短路问题

在包含一组相互分离凸多面体的三维空间中为任意两点寻找最短路的问题是NP问题.当凸多面体的个数k任意时,它为指数时间复杂度;而当k=1时,为O(n²)（n为凸多面体的顶点数）.文章主要研究了k=2情形下的最短路问题,提出一个在O(n²)时间内解决该问题的算法.所得结果大大优于此情形下迄今为止最好的结果——O(n^{3相似文献}   

双向选择排序算法

为丰富O(n²)阶排序算法的种类,以更好地服务于教学科研和日常应用,提出了一种新的排序算法-双向选择排序算法.通过数学方法分析得知:该算法的时间复杂度为O(n²),空间复杂度为O(1).通过实验对比得知:在相同条件下,该算法的运行时间平均为冒泡排序的27%、简单选择排序的62%、直接插入排序的88%.     

半动态矩形交查询算法

本文讨论了动态矩形交查询算法.文中介绍了两个半动态矩形查询的新算法，它们分别基于一维数据结构和二维数据结构.一维查询算法的查询时间复杂度是O（logM＋k′），更新时间复杂度是O（logMlogn），空间复杂度是O（nlogM/）.二维查询算法的查询时间复杂度是O（log²M＋k），更新时间复杂度是O（log²Mlogn），空间复杂度是O（nlog²M）.本文分别实现了这两个算法，通过对它们的性能进行比较，发现一维查询算法是一种高效、实用的算法.     

一种基于拓扑势的网络社区发现方法

从数据场思想出发,提出了一种基于拓扑势的社区发现算法.该方法引入拓扑势描述网络节点间的相互作用,将每个社区视为拓扑势场的局部高势区,通过寻找被低势区域所分割的连通高势区域实现网络的社区划分.理论分析与实验结果表明,该方法无须用户指定社区个数等算法参数,能够揭示网络内在的社区结构及社区间具有不确定性的重叠节点现象.算法的时间复杂度为O(m+n^3/γ)～O(n²),n为网络节点数,m为边数,2<γ<3为一个常数.     

求解大规模谱聚类的近似加权核k-means算法

谱聚类将聚类问题转化成图划分问题,是一种基于代数图论的聚类方法.在求解图划分目标函数时,一般利用Rayleigh熵的性质,通过计算Laplacian矩阵的特征向量将原始数据点映射到一个低维的特征空间中,再进行聚类.然而在谱聚类过程中,存储相似矩阵的空间复杂度是O(n²),对Laplacian矩阵特征分解的时间复杂度一般为O(n³),这样的复杂度在处理大规模数据时是无法接受的.理论证明,Normalized Cut图聚类与加权核k-means都等价于矩阵迹的最大化问题.因此,可以用加权核k-means算法来优化Normalized Cut的目标函数,这就避免了对Laplacian矩阵特征分解.不过,加权核k-means算法需要计算核矩阵,其空间复杂度依然是O(n²).为了应对这一挑战,提出近似加权核k-means算法,仅使用核矩阵的一部分来求解大数据的谱聚类问题.理论分析和实验对比表明,近似加权核k-means的聚类表现与加权核k-means算法是相似的,但是极大地减小了时间和空间复杂性.     

加权3-Set Packing 的改进算法

Packing 问题构成了一类重要的NP 难问题.对于加权3-Set Packing 问题,把问题转化成加权3-Set Packing Augmentation 问题进行求解,即主要讨论如何从一个已知的最大加权k-packing 求得一个权值最大的(k+1)-packing. 通过对问题结构的分析,结合Color-Coding 技术,首先给出了一种时间复杂度为O^*(10.6^3k)的参数算法,极大地改进了目前文献中的最好结果O^*(12.8^3k).通过对(k+1)-packing 结构的进一步分析,利用集合划分技术将上述结果降到O^*(7.56^3k).     

An Improved (and Practical) Parameterized Algorithm for the Individual Haplotyping Problem MFR with Mate-Pairs

The Individual Haplotyping MFR problem is a computational problem that, given a set of DNA sequence fragment data of an individual, induces the corresponding haplotypes by dropping the minimum number of fragments. Bafna, Istrail, Lancia, and Rizzi proposed an algorithm of time O(2^2k m ² n+2^3k m ³) for the problem, where m is the number of fragments, n is the number of SNP sites, and k is the maximum number of holes in a fragment. When there are mate-pairs in the input data, the parameter k can be as large as 100, which would make the Bafna-Istrail-Lancia-Rizzi algorithm impracticable. The current paper introduces a new algorithm PM-MFR of running time , where k ₁ is the maximum number of SNP sites that a fragment covers (k ₁ is smaller than n), and k ₂ is the maximum number of fragments that cover a SNP site (k ₂ is usually about 10). Since the time complexity of the algorithm PM-MFR is not directly related to the parameter k, the algorithm solves the Individual Haplotyping MFR problem with mate-pairs more efficiently and is more practical in real biological applications. This research was supported in part by the National Natural Science Foundation of China under Grant Nos. 60433020 and 60773111, the Program for New Century Excellent Talents in University No. NCET-05-0683, the Program for Changjiang Scholars and Innovative Research Team in University No. IRT0661, and the Scientific Research Fund of Hunan Provincial Education Department under Grant No. 06C526.     

单体型组装MEC问题的参数化算法研究

单体型组装MEC问题指如何利用个体的DNA测序片断数据,翻转最少的SNP位点值以确定该个体单体型的计算问题。根据片段数据的特点提出了一个时间复杂度为 O（nk₂2^k₂+mlogm+mk₁）的参数化算法,其中m为片段数,n为单体型的SNP位点数,k1为一个片断覆盖的最大SNP位点数（通常小于10）,k₂为覆盖同一SNP位点的片段的最大数（通常不大于10）。对于实际DNA测序中的片段数据,即使m和n都相当大,该算法也可以在较短的时间得到MEC问题的精确解,具有良好的可扩展性和较高的实用价值。     

Exact Algorithms for the Bottleneck Steiner Tree Problem

Given n points, called terminals, in the plane ℝ² and a positive integer k, the bottleneck Steiner tree problem is to find k Steiner points from ℝ² and a spanning tree on the n+k points that minimizes its longest edge length. Edge length is measured by an underlying distance function on ℝ², usually, the Euclidean or the L ₁ metric. This problem is known to be NP-hard. In this paper, we study this problem in the L _p metric for any 1≤p≤∞, and aim to find an exact algorithm which is efficient for small fixed k. We present the first fixed-parameter tractable algorithm running in f(k)⋅nlog ² n time for the L ₁ and the L _∞ metrics, and the first exact algorithm for the L _p metric for any fixed rational p with 1<p<∞ whose time complexity is f(k)⋅(n ^k +nlog n), where f(k) is a function dependent only on k. Note that prior to this paper there was no known exact algorithm even for the L ₂ metric.     

A Practical Exact Algorithm for the Individual Haplotyping Problem MEC/GI

Haplotypes play an important role in genetic association studies of complex diseases. Recently, computational techniques helping to determine human haplotypes were studied extensively. Given the genotype and the aligned single nucleotide polymorphism (SNP) fragments of an individual, Minimum Error Correction with Genotype Information (MEC/GI) is an important computational model to infer a pair of haplotypes compatible with the genotype by correcting minimum number of SNPs in the given SNP fragments. The MEC/GI problem has been proven NP-hard, for which there is no practical exact algorithm. Despite the rapid advances in molecular biological techniques, modern high-throughput sequencers cannot sequence directly a DNA fragment that contains more than 1200 nucleotide bases. With low SNP density, current available data reveal that the number k of SNP sites that a DNA fragment covers is usually smaller than 10. Based on the above fact, we develop a new dynamic programming algorithm with running time O(mk2 ^k +mlog m+mk), where m is the number of fragments. Since k is small in real biological applications, the algorithm is practical and efficient.     

An efficient top-down search algorithm for learning Boolean networks of gene expression

Boolean networks provide a simple and intuitive model for gene regulatory networks, but a critical defect is the time required to learn the networks. In recent years, efficient network search algorithms have been developed for a noise-free case and for a limited function class. In general, the conventional algorithm has the high time complexity of O(2^{2k mn k+1}) where m is the number of measurements, n is the number of nodes (genes), and k is the number of input parents. Here, we suggest a simple and new approach to Boolean networks, and provide a randomized network search algorithm with average time complexity O ^{(mn k+1}/ (log m)^(k−1)). We show the efficiency of our algorithm via computational experiments, and present optimal parameters. Additionally, we provide tests for yeast expression data. Editor: David Page     

A simplified complexity analysis of mcdiarmid and reed's variant of bottom-up-heapsort

McDiarmid and Reed (1989) presented a variant of BOTTOM-UP-HEAPSORT which requires nlog₂ n+n element comparisons (for n= 2 ^h+1-1) in the worst case, but requires an extra storage of n bits. Ingo Wegener (1992) has analyzed the average and worst case complexity of the algorithm which is very complex and long. In this paper we present a simplified complexity analysis of the same algorithm from a different viewpoint. For n= 2 ^h+1-1, we show that it requires nlog₂ n+n element comparisons in the worst case and nlog₂ n+0.42n comparisons on the average     

Applying Modular Decomposition to Parameterized Cluster Editing Problems

A graph G is said to be a bicluster graph if G is a disjoint union of bicliques (complete bipartite subgraphs), and a cluster graph if G is a disjoint union of cliques (complete subgraphs). In this work, we study the parameterized versions of the NP-hard Bicluster Graph Editing and Cluster Graph Editing problems. The former consists of obtaining a bicluster graph by making the minimum number of modifications in the edge set of an input bipartite graph. When at most k modifications are allowed (Bicluster(k) Graph Editing problem), this problem is FPT, and can be solved in O(4 ^k nm) time by a standard search tree algorithm. We develop an algorithm of time complexity O(4 ^k +n+m), which uses a strategy based on modular decomposition techniques; we slightly generalize the original problem as the input graph is not necessarily bipartite. The algorithm first builds a problem kernel with O(k ²) vertices in O(n+m) time, and then applies a bounded search tree. We also show how this strategy based on modular decomposition leads to a new way of obtaining a problem kernel with O(k ²) vertices for the Cluster(k) Graph Editing problem, in O(n+m) time. This problem consists of obtaining a cluster graph by modifying at most k edges in an input graph. A previous FPT algorithm of time O(1.92 ^k +n ³) for this problem was presented by Gramm et al. (Theory Comput. Syst. 38(4), 373–392, 2005, Algorithmica 39(4), 321–347, 2004). In their solution, a problem kernel with O(k ²) vertices is built in O(n ³) time.     

A Fast Algorithm for k-Nearest Neighbor Problem on a Reconfigurable Mesh Computer

Given a set S of m points stored on a reconfigurable mesh computer of size n×n, one point per processing element (PE). In this paper we present a parallel method for solving the k-Nearest Neighbor problem (k-NN). This method permits each point of S to know its k-NN (0<k<m). The corresponding algorithm requires that each PE must have 2k registers where it stores the (x,y) coordinates of its k-NN in a given order. This algorithm has a complexity of O(logh+k ²) times, where h is a maximal number of points within a row of the mesh. This complexity is reduced to O(k ²) times, using an appropriate procedure which demonstrates the power of the reconfiguration operations carried out by the processors, and the polymorphic properties of the mesh.     

Complexity of Computing the Local Dimension of a Semialgebraic Set

The paper describes several algorithms related to a problem of computing the local dimension of a semialgebraic set. Let a semialgebraic set V be defined by a system of k inequalities of the formf  ≥  0 with f  R [ X₁, ,X_n ], deg(f)  < d , andx   V . An algorithm is constructed for computing the dimension of the Zariski tangent space to V at x in time (kd)^O(n). Let x belong to a stratum of codimension l_xin V with respect to a smooth stratification ofV . Another algorithm computes the local dimension dim_x(V) with the complexity (k(l_x +  1)d)^O(l_x2n). Ifl  = max_x  Vl_x, and for every connected component the local dimension is the same at each point, then the algorithm computes the dimension of every connected component with complexity (k(l +  1)d)^O(l2n). If V is a real algebraic variety defined by a system of equations, then the complexity of the algorithm is less thankd^O(l2n) , and the algorithm also finds the dimension of the tangent space to V at x in time kd^O(n). Whenl is fixed, like in the case of a smooth V , the complexity bounds for computing the local dimension are (kd)^O(n)andkd^O(n) respectively. A third algorithm finds the singular locus ofV in time (kd)^O(n2).     

Complexity and Approximations for Multimessage Multicasting

We consider multimessage multicasting over thenprocessor complete (or fully connected) static network (MM_C). First we present a linear time algorithm that constructs for every degreedproblem instance a communication schedule with total communication time at mostd², wheredis the maximum number of messages that each processor may send or receive. Then we present degreedproblem instances such that all their communication schedules have total communication time at leastd². We observe that our lower bound applies when the fan-out (maximum number of processors receiving any given message) is huge, and thus the number of processors is also huge. Since this environment is not likely to arise in the near future, we turn our attention to the study of important subproblems that are likely to arise in practice. We show that when each message has fan-outk=1 theMM_Cproblem corresponds to the makespan openshop preemptive scheduling problem which can be solved in polynomial time and show that fork?2 our problem is NP-complete and remains NP-complete even when forwarding is allowed. We present an algorithm to generate a communication schedule with total communication time 2d−1 for any degreedproblem instance with fan-outk=2. Our main result is anO(q·d·e) time algorithm, wheree?nd(the input length), with an approximation bound ofqd+k^1/q(d−1), for any integerqsuch thatk>q?2. Our algorithms are centralized and require all the communication information ahead of time. Applications where all of this information is readily available include iterative algorithms for solving linear equations, and most dynamic programming procedures. The Meiko CS-2 machine and computer systems with processors communicating via dynamic permutation networks whose basic switches can act as data replicators (e.g.,nbynBenes network with 2 by 2 switches that can also act as data replicators) will also benefit from our results at the expense of doubling the number of communication phases.