k-Median近似计算复杂度与局部搜索近似算法分析

k-Median问题的近似算法研究一直是计算机科学工作者关注的焦点,现有研究结果大多是关于欧式空间和Metric空间的,一般距离空间k-Median的结果多年来一直未见.考虑一般距离空间k-Median问题,设d_max/d_min表示k-Median实例中与客户点邻接的最长边长比最短边长的最大者.首先证明d_max/d_min≤ω+ε的k-Median问题不存在近似度小于1+ω-1/e的多项式时间近似算法,除非,由此推出Metric k-Median问题不可近似到1+2/e,除非NP(∈)DTME(N^{O(log logn)}).然后给出k-Median问题的一个局部搜索算法,分析表明,若有d_max/d_min≤ω,则算法的近似度为1+ω-1/2.该结果亦适用于Metric k-Median,ω≤5时,局部搜索算法求解Metric k-Median的近似度为3,好于现有结果3+2/P.通过计算机实验,进一步研究了k-Median局部搜索求解算法的实际计算效果和该算法的改进方法.     

一般设施定位问题计算复杂度和近似算法研究

设施定位问题即UFL问题是NP-hard的组合优化问题,是聚类问题领域的热点问题之一,在数据挖掘和分类识别方面有着重要应用.多年来其近似算法研究一直是计算机科学工作者关注的焦点,然而现有研究结果大多关于Metric空间,一般距离空间中该问题结果始终未见.针对最大连接费用至多是最小连接费用ω＞1倍的一般距离空间中设施定位问题,简称一般设施定位问题,借助集合覆盖问题,利用问题归约方法证明其不存在近似性能比小于1.243 0.316ln(ω-1)的多项式时间近似算法,除非NPDTIME(nO(log log n));设计了一般设施定位问题的局部搜索算法,证明算法近似性能比是(1 ω)/α,ω＞1,1≤α≤2.仿真实验表明,一般设施定位问题局部搜索算法的求解质量极高;通过实验进一步研究了该算法并给出了改进方法.     

合取范式3可满足问题的局部搜索近似算法

合取范式最大可满足问题是理论计算机科学的核心问题.局部搜索被许多求解实践证明是解答合取范式最大可满足问题十分有效的方法,但未见关于局部搜索算法解答该问题性能分析的结果.文中讨论最大3可满足问题(Max-(3)-Sat)的局部搜索算法并分析算法性能.证明Max-(3)-Sat问题的一位跳变局部搜索算法的近似性能比为4/3;证明一位跳变局部搜索后跟有条件全体跳变算法,解答Max-(3)-Sat问题的近似性能比为5/4.设计一位跳变加全体跳变的新局部搜索算法,证明新算法解答Max-(3)-Sat问题的近似性能比为8/7.将8/7-近似局部搜索算法推广为解答Max-(k)-Sat问题的局部搜索算法,证明算法的近似性能比为(2k+2)/(2k+1),k≥4.设计解答Max-(k)-Sat问题的两位跳变局部搜索算法,证明两位跳变局部搜索算法的近似性能比为1+1/(2k+1+k(k-1)/(n-k)),k≥4.局部搜索算法经多次运行可进一步提高求解性能.文中结果显示,局部搜索算法在合取范式最大可满足问题求解实践中表现出高性能,有其必然性.     

多服务中心设置问题局部搜索算法的分析与实验

讨论了多服务中心设置问题的局部搜索近似算法及其在实际计算中表现出的新性质。首先对局部搜索算法求解多服务中心设置问题的实际近似性能比给出了一个针对性分析结果,然后编程实验对局部搜索求解算法的求解时间和求解质量进行了探讨。     

基于大训练样本集的ε-SVR改进算法研究

在改进算法的研究中,从大训练样本集中进行样本抽样是构建大样本支持向量回归机的重要手段.根据ε-SVR支持向量分布的特有属性和支持向量逐步回归机算法求解ε-SVR的缺陷,为改善训练时间,优化收敛性,从大训练样本集中抽取的小样本集的ε-SVR超平面出发,通过计算大训练样本集样本点距近似超平面距离d,剔除大训练样本集中在ε≤d≤dmax外的训练样本点,逐步搜索SVs,建立大训练样本集ε-SVR.提出了构建大训练样本集ε-SVR的逐步搜索算法,理论分析和仿真实验验证了搜索算法的收敛性和有效性.     

利用近似解加速求解SAT问题的启发式完全算法

结合DPLL完全算法能够证明可满足性(SAT)问题的不可满足性和局部搜索算法快速的优点,提出利用近似解加速求解SAT问题的启发式完全算法.首先利用局部搜索算法快速地得到一个近似解,并将该近似解作为完全算法的初始输入,用于其中分支变量的相位决策.该算法引导完全算法优先搜索近似解所在的子空间,加速解决器找到可满足解的过程,为SAT问题的求解提供了一种新的有效途径.实验结果表明,该算法有效地提高了决策的精度和SAT解决器的效率,对很多实例非常有效.     

设备定位问题局部搜索算法的实验

讨论设备问题的局部搜索近似算法及其在实际计算中表现出的新性质。主要讨论局部搜索算法中初始解的产生方法,设备价值与服务价值大小对算法求解性能的影响。实验表明：约有99%以上的实例可直接利用局部搜索算法求得最优解;贪心算法产生初始解的局部搜索算法求解时间明显短于随机算法产生初始解的方法,但两者求解质量相当;设备价值和服务价值数值范围越大,局部搜索算法越容易求得最优解。     

最大化流水作业加权成套订单数的研究

针对流水作业的加工过程及其复杂性,建立了基于两台机器流水作业工件排序的0-1混合整数规划模型,以最大化加权成套订单数为目标函数.基于求解此类NP难题主要用启发式近似算法,提出了合成分派规则与局部搜索算法相结合的近似算法,用来求解所提出的混合整数规划模型.应用实例表明,用启发式近似算法,以最大化两机流水作业成套订单数为目标,可得出较满意的工件排列次序,从而表明了该算法的有效性.     

测试集问题的集合覆盖贪心算法的深入近似

测试集问题是一个有着广泛应用的NP难问题.集合覆盖贪心算法是测试集问题的一个常用近似算法,其由集合覆盖问题得到的近似比21nn+1能否改进是一个公开的问题.集合覆盖贪心算法的推广被用来求解生物信息学中出现的冗余测试集问题.通过分析条目对被区分次数的分布情况,用去随机方法证明了集合覆盖贪心算法对测试集问题的近似比可以为1.51nn+0.5lnlnn+2,从而缩小了这种算法近似比分析的间隙.另外,给出了集合覆盖贪心算法对冗余度为n-1的加权冗余测试集问题的近似比的紧密下界(2-o(1))lnn-Θ 1).     

高维空间球集覆盖问题的改进1+ε近似算法

高维空间球集的覆盖问题是指对高维空间中多个球构成的集合S,构造一个直径最小的球来覆盖S中所有已知球。本文提出了球集直径的概念,给出求解球集直径的1/3~(1/2)近似算法。基于此算法求解球集实例集合S的初始核心集,进而给出高维空间球集覆盖问题的1+ε近似算法,算法时间复杂度为O(nd/ε+d2/ε3/2(1/ε+d)lg1/ε)。算法保证核心集中球的个数为O(1/ε),与S中球的个数和空间维数无关。     

Approximated approximations for SAO

We propose to replace a number of popular approximations by their diagonal quadratic Taylor series expansions. The resulting separable quadratic approximations are easily convexified, and are well suited for use in dual sequential approximate optimization (SAO) algorithms. Global convergence of the resulting SAO algorithms may be enforced in a natural way using conservatism. The approximated approximation approach is explicitly illustrated for (i) reciprocal and exponential intervening variables, (ii) the intervening variables used in the method of moving asymptotes (MMA), (iii) the intervening variables used in CONLIN, and (iv) the TANA-3 approximations. The use of intermediate responses for use in, for example, truss and frame-like structures, is also discussed. Key advantages of replacing nonlinear approximations by their diagonal quadratic approximations are that these approximated approximations can all be used simultaneously in a single dual statement; the dual does not depend on the form of the original approximations. In addition, in a dual setting, the resulting subproblems yield simple analytical relationships between the primal and dual variables, which is often not the case with the original nonlinear approximations. An important example hereof is the exponential approximation. Although the diagonal quadratic approximations may differ notably from their original counterparts, they typically are quite similar in a sufficiently small search subregion, which relates to the move limits commonly used in SAO anyway.     

近似Log-MAP turbo译码器研究

该文研究近似Log-M AP算法在turbo译码器中的应用。文章对基于近似算法的W CDM A turbo译码器在AW GN信道和平坦慢衰落Rayleigh信道上的纠错性能进行了仿真。仿真结果表明,二阶近似Log-M AP turbo译码器与M A P turbo译码器性能等价,优于SO VA turbo译码器0.7-0.9dB。     

Approximated Distributions of Sampling Inequality Indices

Often, in finite samples, the true level of the confidence intervals for natural estimators of inequality indices belonging to the Gini family differs greatly from their nominal level, which is based on the asymptotic confidence limits. This paper shows how the Gram-Charlier series can be used to obtain improved finite-sample confidence intervals. Our work focuses on the implementation in Mathematica 3.0 of computational procedures to compute the Gram-Charlier distribution for the following sampling inequality indices: R by Gini, P by Piesch and M by Mehran for the Dagum (Type I) distribution. The results of a Monte Carlo experiment confirm that, for the cases investigated, the Gram-Charlier distribution largely eliminates the problem of incorrect finite-sample level.     

Approximated consistency for the automatic recording constraint

We introduce the automatic recording constraint (ARC) that can be used to model and solve scheduling problems where tasks may not overlap in time and the tasks linearly exhaust some resource. Since achieving generalized arc-consistency for the ARC is NP-hard, we develop a filtering algorithm that achieves approximated consistency only. Numerical results show the benefits of the new constraint on three out of four different types of benchmark sets for the automatic recording problem. On these instances, run-times can be achieved that are orders of magnitude better than those of the best previous constraint programming approach.     

稀疏近似最近特征空间嵌入标签传播

针对现有的基于图的半监督学习（graph-based semi-supervised learning,简称GSSL）方法存在模型参数敏感和数据空间判别信息不充分等问题,受最近特征空间嵌入和数据稀疏表示思想的启发,提出一种稀疏近似最近特征空间嵌入标签传播算法SANFSP（sparse approximated nearest feature space embedding label propagation）.SANFSP首先利用特征空间嵌入投影点来稀疏表示原始数据;然后,度量原始数据和稀疏近似最近特征空间嵌入投影间的相似性;进而提出稀疏近似最近特征空间嵌入正则化项;最后,基于传统GSSL 方法的标签传播算法,实现数据标签的平滑传播.同时,还将SANFSP 算法简单拓展到out-of-sample 学习.SANFSP 算法在人造和实际数据集（如人脸识别、可视物件识别以及手写数字分类等）上取得了有效的实验结果.     

保持特征的平面形状近似骨架的抽取算法

针对多边形骨架抽取中轮廓噪声严重影响骨架的问题,提出一种保持特征的多边形近似骨架的抽取算法.通过分水岭算法检测平面多边形的特征突起点,在分支末端点引导骨架的抽取,从而避免多边形轮廓噪声对骨架的影响,得到有效的形状简洁的近似骨架.另外,该方法还适用于半自动的骨架抽取,即允许用户手动指定骨架末端点,使计算所得的骨架具有更高的实用性.实验结果表明,文中方法简单易行,能应用于计算机动画和形状检索等领域.     

Approximated parameterized verification of infinite-state processes with global conditions

We present a simple and effective approximated backward reachability procedure for parameterized systems with existentially and universally quantified global conditions. The individual processes operate on unbounded local variables ranging over the natural numbers. In addition, processes may communicate via broadcast, rendez-vous and shared variables. The procedure operates on an over-approximation of the transition system induced by the parameterized system. We verify mutual exclusion for complex protocols such as atomic, non-atomic and distributed versions of Lamport’s bakery algorithm.     

Efficient Speaker Recognition Using Approximated Cross Entropy (ACE)

Techniques for efficient speaker recognition are presented. These techniques are based on approximating Gaussian mixture modeling (GMM) likelihood scoring using approximated cross entropy (ACE). Gaussian mixture modeling is used for representing both training and test sessions and is shown to perform speaker recognition and retrieval extremely efficiently without any notable degradation in accuracy compared to classic GMM-based recognition. In addition, a GMM compression algorithm is presented. This algorithm decreases considerably the storage needed for speaker retrieval.     

Approximated Centroidal Voronoi Diagrams for Uniform Polygonal Mesh Coarsening

We present a novel clustering algorithm for polygonal meshes which approximates a Centroidal Voronoi Diagram construction. The clustering provides an efficient way to construct uniform tessellations, and therefore leads to uniform coarsening of polygonal meshes, when the output triangulation has many fewer elements than the input mesh. The mesh topology is also simplified by the clustering algorithm. Based on a mathematical framework, our algorithm is easy to implement, and has low memory requirements. We demonstrate the efficiency of the proposed scheme by processing several reference meshes having up to 1 million triangles and very high genus within a few minutes on a low‐ end computer.