Average-case analysis of the Modified Harmonic algorithm

In this paper we analyze the average-case performance of the Modified Harmonic algorithm for on-line bin packing. We first analyze the average-case performance for arbitrary distribution of item sizes over (0,1]. This analysis is based on the following result. Letf ₁ andf ₂ be two linear combinations of random variables {N _i } _i=1 ^k where theN _i 's have a joint multinomial distribution for eachn= _i=1 ^k ,N _i . LetE(f ₁) O andE(f ₂) 0. Then lim_n E(max(_{f 1},f ₂ ))/n = lim _n max(E(f ₁),E(f ₂))/n. We then consider the special case when the item sizes are uniformly distributed over (0,1]. For specific values of the parameters, the Modified Harmonic algorithm turns out to be better than the other two linear-time on-line algorithms—Next Fit and Harmonic—in both the worst case as well as the average case. We also obtain optimal values for the parameters of the algorithm from the average-case standpoint. For these values of the parameters, the average-case performance ratio is less than 1.19. This compares well with the performance ratios 1.333. and 1.2865. of the Next Fit algorithm and the Harmonic algorithm, respectively.     

Average-case analysis of algorithms using Kolmogorov complexity

Analyzing the average-case complexity of algorithms is a very practical but very difficult problem in computer science.In the past few years,we have demonstrated that Kolmogorov complexity is an improtant tool for analyzing the average-case complexity of algorithms.We have developed the incompressibility method.In this paper,sereral simple examples are used to further demonstrate the power and simplicity of such method.We prove bounds on the average-case number of stacks(queues)required for sorting sequential or parallel Queuesort or Stacksort.     

Average-case analysis for the MAX-2SAT problem

We propose a simple probability model for MAX-2SAT instances for discussing the average-case complexity of the MAX-2SAT problem. Our model is a “planted solution model”, where each instance is generated randomly from a target solution. We show that for a large range of parameters, the planted solution (more precisely, one of the planted solution pairs) is the optimal solution for the generated instance with high probability. We then give a simple linear-time algorithm based on a message passing method, and we prove that it solves the MAX-2SAT problem with high probability for random MAX-2SAT instances under this planted solution model for probability parameters within a certain range.     

基于ip-iq谐波检测算法的改进与仿真

在介绍了基于瞬时无功功率理论的谐波检测算法基本原理基础上,提出了基于该理论的ip-iq谐波检测算法的改进方案--直流分量法,对此方法进行理论推导并在Simulink仿真环境中进行建模仿真实验.实验结果表明,直流分量法比传统的滤波器法具有更好的动态响应特性.     

Average-case analysis of VCG with approximate resource allocation algorithms

The Vickrey-Clarke-Groves (VCG) mechanism offers a general technique for resource allocation with payments, ensuring allocative efficiency while eliciting truthful information about preferences. However, VCG relies on exact computation of an optimal allocation of resources, a problem which is often computationally intractable, and VCG that uses an approximate allocation algorithm no longer guarantees truthful revelation of preferences. We present a series of results for computing or approximating an upper bound on agent incentives to misreport their preferences. Our first key result is an incentive bound that uses information about average (not worst-case) performance of an algorithm, which we illustrate using combinatorial auction data. Our second result offers a simple sampling technique for amplifying the difficulty of computing a utility-improving lie. An important consequence of our analysis is an argument that using state-of-the-art algorithms for solving combinatorial allocation problems essentially eliminates agent incentives to lie.     

Deep Performance Analysis of Refined Harmonic Bin Packing Alogrithm

Refined Harmonic (RH) is one of the best on-line bin packing algorithms. The algorithm was first proposed by Lee&;Lee in 1985 and the upper bound of the worst-case performance ratio has been proved to be 1.63596 … In this paper, it is proved that 1.63596… is also the lower bound. The average performance of RH is also studied for the first time. It is shown that the average-case performance ratio of RH is 1.28243…under the uniform distribution.     

Average-case analysis of QuickSort and Binary Insertion Tree height using incompressibility

We study the Kolmogorov complexity of a Binary Insertion Tree, and present a succinct encoding scheme for Binary Insertion Trees produced from incompressible permutations. Based on the encoding scheme, we obtain a simple incompressibility argument that yields an asymptotic analysis of the average height of a Binary Insertion Tree. This argument further implies that the QuickSort algorithm sorts a permutation of n elements in Θ(nlgn) comparisons on average.     

视频目标轨迹分析的改进PrefixSpan方法

从序列模式挖掘的角度对视频目标运动轨迹的分析和应用问题进行了研究,提出了一种基于改进 PrefixSpan的频繁轨迹模式挖掘算法,并给出了基于所挖掘的频繁模式进行在线目标运动异常检测的方法。该方法对目标的运动轨迹进行量化编码,采用改进的PrefixSpan算法挖掘其中连续出现的频繁模式,通过字符串近似匹配的方法来检测当前运动轨迹所表示的目标行为是否异常。由于不需要计算两两轨迹之间的相似性,该方法可以应用于规模较大、分布模式数目难以确定场合下的视频目标轨迹分析问题。对仿真和真实场景的实验验证了该方法的有效性。     

改进的粒子群算法及收敛性分析

针对PSO算法对多峰值函数搜索易陷入局部极值点的缺点,提出一种改进的粒子群(MPSO)算法。MPSO算法采用逃逸策略和免疫学习策略来保证种群多样性,使算法能有效进行全局搜索。并讨论MPSO算法的收敛性,证明其能以概率1全局收敛。最后用3个常用的测试函数进行仿真,实验结果表明MPSO算法比PSO算法有更好的收敛性和更快的收敛速度。     

改进的混沌遗传算法

将遗传算法与混沌算法相结合,提出了一种新颖的基于猫映射的混沌遗传算法（CGA）,解释了猫映射的遍历性,分析了猫映射的混沌分布优越性。该算法利用猫映射的初值敏感性扩大搜索范围,利用猫映射的遍历性进行混沌变量的优化搜索,从而减少了数据冗余,保持了种群多样性,有效地解决了局部收敛问题。理论分析和数值仿真表明,该算法具有更好的收敛性能。     

改进的PSO混合算法

为了提高粒子群算法的寻优速度和寻优精度,提出一种改进的PSO混合算法。在差分进化(DE)算法中引入了动态比例因子,在PSO算法中引入DE算法的变异、交叉操作,重新构造PSO算法的粒子位置更新公式。选取了4个基准函数进行测试,并与其他PSO混合算法作了比较。仿真结果表明该方法是有效的。     

改进的概念相似度算法

本体映射是目前的热点问题,而概念相似度计算则是它的关键部分。目前的方法基本上都是基于多策略的综合方法,而综合方法存在计算量大、权值难以确定等问题。提出了一种改进的综合算法－PCASim。该方法通过概念名称相似度计算减少计算量,利用主成分分析改进权值。实验表明该方法是切实可行的。     

无线环境下拥塞控制算法的改进及其稳定性分析

无线网络中数据传输的往返时间RTT(roundtrip time)比有线网络中的RTT大,这使得针对有线网络设计的以时延作为拥塞信号的拥塞控制对偶算法应用到无线网络中时,其稳态性能下降,无线网络的带宽不能得到充分利用.针对对偶算法进行了改进,以保证该算法在无线网络中的稳态性能不会降低;同时,就改进算法的稳定性进行了理论分析和仿真,给出了判断该分布式算法稳定的定理和参数的选择范围.     

一种改进的LLR-SPA译码新算法

针对LDPC码目前广泛使用的译码算法精度低的问题,在LLR-SPA译码算法的基础上提出了一种提高译码精度的新算法。该算法将LLR-SPA算法中复杂度较高的雅可比修正项采用泰勒级数进行分段线性近似,实验表明,该算法在译码复杂度基本不变的情况下,可以大幅度地提高其译码精度。     

Average-case performance analysis of scheduling random parallel tasks with precedence constraints on mesh connected multicomputer systems

We investigate the problem of scheduling parallel tasks with precedence constraints on mesh connected multicomputer systems. It is still an open problem on whether there exists an approximation algorithm with finite asymptotic worst-case and/or average-case performance bound for this scheduling problem. As an early attempt to solve our problem, we propose and analyze the performance of a level-by-level scheduling algorithm LL. In fact, we solve a special case of the problem when all tasks request for square submeshes and run on a square mesh system whose size is a power of 2. There are three basic techniques in algorithm LL, i.e., the level-by-level scheduling strategy for handling precedence constraints, the largest-task-first algorithm for scheduling tasks in the same level, and the two-dimensional buddy system for system partitioning and processor allocation. Algorithm LL does not have a finite worst-case performance bound; however, it has quite acceptable average-case performance. The main contribution of the paper is to show that under the assumptions that task sizes are independent and identically distributed (i.i.d.) random variables with a common probability distribution, and that task execution times are i.i.d. random variables with finite mean and variance, and that the probability distributions of task sizes and execution times are independent of each other, for wide task graphs and typical task size distributions, algorithm LL has an asymptotic average-case performance bound about two for all probability distributions of task execution times.     

Harmonic analysis of homogeneous networks

We introduce a generalization of mutually inhibitory networks called homogeneous networks. Such networks have symmetric connection strength matrices that are circulant (one-dimensional case) or block circulant with circulant blocks (two-dimensional case). Fourier harmonics provide universal eigenvectors, and we apply them to several homogeneous examples: k-wta, k-cluster, on/center off/surround, and the assignment problem. We also analyze one nonhomogeneous case: the subset-sum problem. We present the results of 10000 trials on a 50-node k-cluster problem and 100 trials on a 25-node subset-sum problem.     

Modified FDP cluster algorithm and its application in protein conformation clustering analysis

We present a modified find density peaks (MFDP) clustering algorithm. In the MFDP, a critical parameter, dc, is auto-defined by minimizing the entropy of all points. By considering both the point density, ρ, and large distance from points with higher densities, δ, the high-dimensional points are transformed into a 2D space. The halo points of the original FDP cluster algorithm are redefined, and a definition of boundary points is introduced to illustrate the intersection region between clusters. To demonstrate the clustering ability, the distance-based K-means clustering and density-based algorithms DBSCAN, original FDP are employed respectively. Four criteria are introduced to evaluate the clustering algorithms quantitatively. For most of the cases, the MFDP provides a superior clustering result than both of the typical clustering algorithms, and FDP in 20 commonly used benchmark datasets, particularly in clearly depicting the intersection region between clusters. Finally, we evaluate the performance of the MFDP in the cluster analysis of conformations in molecular dynamics (MD). In the MD clustering process, eight typical cluster center conformations are selected in six collective variable spaces. Moreover, it is in strong agreement with the experiment results. The clustering results demonstrate the potential for generalized applications of the modified algorithm to similar problems.     

Average-case complexity for the execution of recursive definitions on relational databases

The execution costs of various types of database queries, expressed in terms of linear recusive definitions, are evaluated for two common query evaluation algorithms in the case where the database relations are represented by forests of labelled oriented trees. In a first stage, the execution costs are computed for a given forest. A key issue in this computation is the partition of the set of nodes in the forest into equivalence classes, the properties of which are explored. Moreover, the representation adopted is conceptually simple and provides additional results which are of interest by themselves. In a second stage, the averages of these costs, computed over all databases representable by forests with a given number of nodes, are also evaluated. Finally, the execution cost of the considered database queries is computed for the case where the underlined database relations are modelled as Hamiltonian digraphs. Received: 4 October 1995 / 19 February 1997     

改进的NURBS曲线预估校正插补方法

现行的NURBS曲线参数预估校正插补方法不能预估最开始的两个参数,而且不能控制预估参数迭代修正的次数。提出改进的NURBS预估校正插补方法,该方法预估插补点参数,根据最大进给步长约束、轮廓误差约束以及法向加速度约束,判定预估参数与实际参数的误差,当误差在允许范围内,则对参数步长增量进行调整,否则进行迭代修正。仿真实验结果表明,新方法通过对参数步长增量的调整,使得预估参数更加接近实际参数,较现有方法有效减少了参数迭代修正的次数,利于实时插补的实现。     

一种改进的粒子滤波SLAM算法

提出一种改进的粒子滤波SLAM（simultaneous localization and map building）同时定位和地图创建实现方法。改进方法让机器人大约行进10步完成基于局部已创建地图下的粒子滤波定位后,再利用激光传感器探测环境并更新创建的地图;同时在利用粒子滤波定位时,使粒子只分布在由航位推算法得出的机器人位姿附近,从而可有效地减少粒子的数量。实验结果表明,与标准的粒子滤波SLAM 算法比较,改进算法提高了机器人SLAM过程中定位和地图创建的精度和实时性,并为移动机器人在室外未知环境同时定位和地图创建提供了新方法。