SizeScale:求解旅行商问题(TSP)的新算法

旅行商（TSP）问题是组合优化中最典型的NP－Hard问题之一，目前关于该问题的启发式算法主要分布为两类：环路构造算法和环路改进算法，对于第1类算法，首次提出了在环路构造中成批加入顶点，同时在构造过程对环路进行局部优化的思想，由上得到了一种新的算法：SizeScale-Construct，它的解质量极大地改进了现有的环路构造算法，对于2类算法，在分析局部最优解与全局最优解之间关系的基础上，提出了另一个采用局部最优解的交集作为初始环路的新算法：SizeScale-Improve，实验结果表明该算法在解的质量和求解速度上都较大地改进了现有最好的环路改进算法；另一方面，理论上对于最坏情况和平均情况时间复杂度的分析表明这两个算法是实用的。     

Efficient minimum spanning tree algorithms on the reconfigurable mesh

1 IntroductionLet G = (V, E) be a connected, undirected graph with a weight function W on the set Eof edges to the set of reals. A spanning tree is a subgraph T = (V, ET), ET G E, of C suchthat T is a tree. The weight W(T) of a spanning tree T is the sum of the weights of its edges.A spanning tree with the smallest possible'weight is called a minimum spanning tree (MST)of G. Computing an MST of a given weighted graph is an important problem that arisesin many applications. For this …     

组播中代价最小的核选择算法

基于核的组播路由协议使用核节点作为传输中心,所有的组播数据首先被单播到核节点,然后再通过以核节点为根的分发树组播到目的节点.核节点的选择直接影响单播和组播的总代价.以总代价最小为目标,提出了核选择的完全算法和近似算法.     

基于Wormhole路由的二维Mesh上的并行k-选择

由于二维网孔机器的结构简单、规整,易于ＶＬＳＩ实现,使得它不仅成为许多理论研究的基础模型,而且还是许多并行机所采用的互连结构．Ｗｏｒｍ ｈｏｌｅ 路由技术的采用改进了二维网孔机器的通信能力．该文在带有Ｗｏｒｍ ｈｏｌｅ 路由技术的ｎ×ｎ 二维网孔机器上提出了一个时间复杂度为Ｏ（ｌｏｇ２ｎｌｏｇｌｏｇｎ）的并行ｋ－选择算法,改进了该问题在Ｓｔｏｒｅ－ａｎｄ－Ｆｏｒｗ ａｒｄ 路由技术下的时间复杂度下界Ｏ（ｎ）．据已掌握的资料,该算法为最早的、非总线连接的二维网孔机器上的、时间复杂度为对数的多项式级的ｋ－选择算法．     

可重构造的网孔机器上的k-选择

对于一个 ｍ ×ｎ（ｍ ≤ｋ）的列有序矩阵,文中在 ｎ × ｎ 可重构造的网孔机器上提出了一个并行 ｋ选择算法,其时间复杂度为 Ｏ（ｌｏｇ２ｍ ＋ ｌｏｇｍ ｌｏｇ２ ｎ＋ ｌｏｇ３ ｎ）,而对于一般的ｌ元集,文中在相同的模型下提出了一个时间复杂度为 Ｏ ｌｏｇ２ ｌｎ ＋ ｌｏｇ ｌｎ ｌｏｇ２ ｎ＋ ｌｏｇ３ｎ＋ ｌｎ ｌｏｇ ｌｎ 的并行 ｋ选择算法．当时 ｌ≥ Ｏ（ｎｌｏｇ３ｎ／ｌｏｇ ｌｏｇｎ,该时间复杂度为 Ｏ ｌｎ ｌｏｇ ｌｎ ．特别地,当ｌ＝ Ｏ（ｎ１＋ ε）（ε＞ ０ 为常数）,则时间复杂度为 Ｏ ｌｎ ｌｏｇｎ ．此时达到的加速比为 ｎ／ｌｏｇｎ．