限制性的带核元划分问题

考虑了限制性的带核元划分问题,即将一个整数集合划分为2个子集,使得2个核元分别在不同的子集里且每个子集至多包含k个元素,这里n/2+1≤k≤n+1,目标使2个子集中元素之和的最小者达尽可能大.对一般的k,给出了全多项式时间近似方案(FPTAS).当k=n+1时,给出了线性时间内的多项式时间近似方案(PTAS)和全多项式时间近似方案(FPTAS).     

2k阶r-循环矩阵开平方的快速算法

对n(=2k,k≥1阶r-循环矩阵的开平方运算进行了研究.利用矩阵分块逐次降阶的方法,给出了一个快速算法,用来计算r-循环矩阵的同型平方根矩阵(平方根矩阵也为r-循环矩阵).证明了同型平方根矩阵的个数为2",计算一个同型平方根矩阵的时间复杂性为O(nlog2n),计算全部同型平方根矩阵时间复杂性为O(n2nlog 2n).     

基于关键词的RDF数据查询方法

在建立关键词倒排索引和路径索引的基础上,提出一个利用量化均衡规则和等距规则的启发式查询算法,并按照查询结果的大小排序返回最相关的前k个结果.通过建模RDF数据为RDF句子图,将文本信息封装到句子节点,同时将查询结果建模为包括所有查询关键词并且叶节点是关键词节点的无根树,将关键词查询问题转化为斯坦纳树问题.假设RDF句子图包括n个节点,最坏情况下索引占用的空间是3n2.假设关键词节点数为k,查询算法的时间复杂度为O(kn).该方法不需要依赖RDF数据的模式信息,支持对数据中的属性和关系名进行关键词查询.实验证明该方法能够快速而有效地实现RDF数据的关键词查询.     

超立方体中过k个指定点的最短路径

利用超立方体的拓扑结构,基于其内部节点编码的特点,分析研究得到在n维超立方体Qn中任意两节点s、t之间经过k(kn)个指定点的最短路径算法.该算法共包括了十个步骤,在最坏的情况下执行2n~2+2n(n~2+2)次运算,算法的时间复杂度为O(n~3),属于多项式计算.     

多序列比对问题的并行近似算法

基于中心方法的思想,采用分治策略,在SIMD-CREW模型上设计了一个使用O(k2m)个处理器(其中k为序列个数,m为最长的序列长度),时间复杂度为O(m logk)的并行近似算法.在实际情况中,由于logk远远小于m,相对于时间复杂度为O(m2k2)的串行中心方法,该算法在理论上达到线性加速.与现有的并行算法相比,它可以适用于任意情况,且易于分析时间复杂度.利用LARPBS模型的特点和并行求前缀和的方法,调用LARPBS模型上求和与最大(小)值的并行算法,首次给出了在LARPBS模型上的多序列比对问题的并行近似算法.该算法使用O(k2m)个处理器,时间复杂度为O(m log log D),其中D为序列两两比对的代价值的最大值.该算法同样适用于任何情况,由于log log D通常远小于m,所以它在理论上也是线性加速的.     

多面体面上任意两点间最短路径算法

提出计算多面体面上任意两点之间最短路径的算法:近似算法、最短路径或近似最短路径算法.近似算法的思想是采用将折线不断嵌入三角形串上的方法,而另2个算法则是通过特定法线寻找三角形串,而且将这些三角形旋转到同一平面上,从而得到最短路径.前者的时间复杂性为O(n),而后者的时间复杂性分别是O(n2)及低于O(2nn2).     

总延误问题的一个近似算法及其分析

对于一台机器的总延误问题,本文提出了一个近似算法,它具有以下性质:多项式复杂度,给出局部解(相应于后移邻域),有界的性能比。本文侧重给出一个论证方法,以得到该算法性能比的精确值。     

装箱问题的概率近似算法

研究了一维装箱问题的在线近似算法,给出了一种新的半在线算法：随机适应算法（简称RF算法）,说明了RF算法的时间复杂度是O（n^2）,一般情况下的性能比〈1.75。     

拉格朗日插值多项式的一种并行算法

提出在机群系统并行环境下的构造拉格朗日插值多项式的一种并行算法.该算法以n个节点(x0,y0),(x1,y1),…,(xn-1,yn-1)的拉格朗日插值多项式公式为基础.当处理机数量为n2时,它的时间复杂度为3log(n) O(1);当处理机数量为p2(p相似文献   

求解MEB问题的一种SMO-型方法

目的求解n维空间中m个点的最小闭包球(MEB)问题。方法基于序列最小优化(SMO)的方法,提出了一种近似算法,求解MEB问题的一个(1+ε)-近似。结果建立了此算法的计算复杂度为O(mn/ε),并且算法最终得到一个独立于m,n的大小为O(1/ε)的核心集。结论数值结果表明对于求解高精度的大规模问题,算法是很有效的。