Subquadratic Approximation Algorithms for Clustering Problems in High Dimensional Spaces

One of the central problems in information retrieval, data mining, computational biology, statistical analysis, computer vision, geographic analysis, pattern recognition, distributed protocols is the question of classification of data according to some clustering rule. Often the data is noisy and even approximate classification is of extreme importance. The difficulty of such classification stems from the fact that usually the data has many incomparable attributes, and often results in the question of clustering problems in high dimensional spaces. Since they require measuring distance between every pair of data points, standard algorithms for computing the exact clustering solutions use quadratic or “nearly quadratic” running time; i.e., O(dn ^2?α(d)) time where n is the number of data points, d is the dimension of the space and α(d) approaches 0 as d grows. In this paper, we show (for three fairly natural clustering rules) that computing an approximate solution can be done much more efficiently. More specifically, for agglomerative clustering (used, for example, in the Alta Vista? search engine), for the clustering defined by sparse partitions, and for a clustering based on minimum spanning trees we derive randomized (1 + ∈) approximation algorithms with running times Õ(d ² n ^2?γ) where γ > 0 depends only on the approximation parameter ∈ and is independent of the dimension d.     

加权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).     

加权3-Set Packing 的改进算法

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

医学图像三维分割技术

针对人体组织器官的三维图像分割是医学图像分析和医疗诊断的重要前提,是医学图像三维可视化的重要研究内容。随着医学成像技术和三维可视化技术的飞速发展,计算机辅助诊断成为现实。计算机技术的发展使得医生和研究者可以通过虚拟交互更好地理解人体的解剖结构,对病人作出正确的诊断。在对人体组织器官和感兴趣区域的分割中,三维分割发挥着十分重要的作用。为此,针对目前不同的三维分割算法进行了总体介绍,并将这些算法分为基于结构的分割技术、基于统计学的分割技术和混合技术三大类。     

Dynamic Programming on the Word RAM

Abstract. Dynamic programming is one of the fundamental techniques for solving optimization problems. In this paper we propose a general framework which can be used to decrease the time and space complexity of these algorithms with a logarithmic factor. The framework is based on word encoding, i.e. by representing subsolutions as bits in an integer. In this way word parallelism can be used in the evaluation of the dynamic programming recursion. Using this encoding the subset-sum problem can be solved in O( n b/ log b) time and O(b/ log b) space, where n is the number of integers given and b is the target sum. The knapsack problem can be solved in O( n m/ log m) time and O(m/ log m) space, where n is the number of items and m = max{b,z} is the maximum of the capacity b and the optimal solution value z . The problem of finding a path of a given length b in a directed acyclic graph G=(V,E) can be solved in O(|E|b/ log b) time and O(|V|b/ log b) space. Several other examples are given showing the generality of the achieved technique. Extensive computational experiments are provided to demonstrate that the achieved results are not only of theoretical interest but actually lead to algorithms which are up to two orders of magnitude faster than their predecessors. This is a surprising observation as the increase in speed is larger than the word size of the processor.     

Randomized Algorithms for 3-SAT

Schoning proposed a simple yet efficient randomized algorithm for solving the k-SAT problem. In the case of 3-SAT, the algorithm has an expected running time of poly(n)·(4/3)ⁿ = O(1.334ⁿ). In this paper we present randomized algorithms and show that one of them has O(1.3302ⁿ) expected running time, improving Schoning's algorithm. (Note. At this point, the fastest randomized algorithm for 3-SAT is the one given by Iwama and Tamaki that runs in O(1.324ⁿ).)     

Generation of address sequences for effective random access memory testing

In the present article the problem of efficient application of multiple march tests for the purpose of detecting faults in random access memory, realized through the generation of different address sequences, is considered. For these purposes, a new algorithm for generating address sequences is proposed and the efficiency gained from its application evaluated. In the conclusion experimental results on the use of the proposed method for generating address sequences are presented and the efficiency of the method in multiple run random access memory tests is demonstrated.     

The Use of MC# Language for Implementation of Parallel Algorithms in 3D Simulation

Parallelizm of the real-time visualization of 3D objects is considered in the paper. A 3D space model and its implementation using parallel programming are proposed.     

示例学习算法IBLE和ID3的比较研究

为了比较研究IBLE算法和ID_3算法的学习性能,本文用大量的质谱数据对两种算法做了学习实验。经过学习,IBLE 的平均预测率为93.96%。而ID_3为81.76%,而且IBLE 获得的知识在表示和内容上与专家知识具有较高一致性。文中对两种算法出现上述差异的原因进行了理论分析。     

两种三维图形消隐算法的改进

在介绍了Ｒｏｂｅｒｔｓ算法和画家算法的基础上，提出了其改进算法。前者的改进算法克服了用于凹体或多个形体时不可行的缺点，可实现任意数目和形状的三维形体的隐线消除；而后者的改进算法则克服了要满足物体的表面顺利排序的要求而只能是方体和效率较低的不足，一次成图，省去反复覆盖，且对物体的数目和形状不限。     

加权3D-Matching的改进算法

Matching问题构成了一类重要的NP难问题.此类问题在诸多领域中有着重要的应用,如调度、代码优化等领域.对于加权3D-matching问题,通过深入分析问题的结构特性,可以转化成加权3D-matching augmentation问题进行求解,即从一个最大加权的k-matching着手构造权值最大的(k+1)-matching.从问题的特殊结构特性出发,给出了加权3D-matching augmentation问题特有的性质: k- matching中存在2列使得该2列至少有2k/3元素被包含在(k+1)-matching中所对应的2列中.基于给出的性质,通过运用color-coding和动态规划技术,给出了一个时间复杂度为O* (4.823k)的参数算法,最终求解加权3D-matching问题.该算法较目前文献中的最好结果O* (5.473k)有了极大的改进.     

Windows环境下表处理软件与文字处理软件之间的数据通信

文中主要介绍了在Ｗｉｎｄｏｗｓ环境下字处理软件Ｗｏｒｄ与表处理软件Ｌｏｔｕｓ１－２－３之间实现数据通信的方法。     

遥测数字接口的研究与实现

为了满足航天器遥测数字接口高码速率、高可靠性、小型化及低功耗等特性,设计了异步串行信号接收器。该接收器采用乒乓流水技术,将接收到的数据分别写入到两个RAM中,从而完成数据同时读写且互不干扰的操作。接收器的所有核心功能均集中在一片FPGA芯片内完成,实现了设备核心电路单片化设计,并较好地解决了数字电路通常出现的各器件之间信号互扰等问题。各种仿真及试验结果表明,该数字接口设备可以很好地满足航天器的各种要求。     

三维ICT图像处理与分析系统关键算法研究

该文介绍了ICT图像处理与分析系统关键算法的研究,即三维重建算法的改进和为提高测量精度所采用的双线性插值算法。改进的重建算法提高了三维面显示的效果,有效地抑制了三维面显示中的阶梯效应。另外,采用的测量算法使得测量误差在0.05mm以内,可以满足绝大部分工业CT应用的需求。     

Approximation Algorithms for 3D Orthogonal Knapsack

We study non-overlapping axis-parallel packings of 3D boxes with profits into a dedicated bigger box where rotation is either forbidden or permitted, and we wish to maximize the total profit. Since this optimization problem is NP-hard, we focus on approximation algorithms. We obtain fast and simple algorithms for the non-rotational scenario with approximation ratios 9 ε and 8 ε , as well as an algorithm with approximation ratio 7 ε that uses more sophisticated techniques; these are the smallest approximation ratios known for this problem. Furthermore, we show how the used techniques can be adapted to the case where rotation by 90° either around the z-axis or around all axes is permitted, where we obtain algorithms with approximation ratios 6 ε and 5 ε , respectively. Finally our methods yield a 3D generalization of a packability criterion and a strip packing algorithm with absolute approximation ratio 29/4, improving the previously best known result of 45/4.     

Algorithms for matching 3D line sets

Matching two sets of lines is a basic tool that has applications in many computer vision problems such as scene registration, object recognition, motion estimation, and others. Line sets may be composed of infinitely long lines or finite length line segments. Depending on line lengths, three basic cases arise in matching sets of lines: 1) finite-finite, 2) finite-infinite, and 3) infinite-infinite. Case 2 has not been treated in the literature. For Cases 1 and 3, existing algorithms for matching 3D line sets are not completely satisfactory in that they either solve special situations, or give approximate solutions, or may not converge, or are not invariant with respect to coordinate system transforms. In this paper, we present new algorithms that solve exactly all three cases for the general situation. The algorithms are provably convergent and invariant to coordinate transforms. Experiments with synthetic and real 3D image data are reported.     

ID3算法在军事训练成绩分析中的应用

随着部队实战化训练的深入,传统的训练成绩分析方法已不能适应科学组训的需要。该文引入射击训练实例,应用人工智能中机器学习的ID3归纳学习算法,对射击情况进行分类分析,得出影响军事训练成绩的内部原因以及其他一些结论。     

Cooling Algorithms Based on the 3-bit Majority

Algorithmic cooling is a potentially important technique for making scalable NMR quantum computation feasible in practice. Given the constraints imposed by this approach to quantum computing, the most likely cooling algorithms to be practicable are those based on simple reversible polarization compression (RPC) operations acting locally on small numbers of bits. Several different algorithms using 2- and 3-bit RPC operations have appeared in the literature, and these are the algorithms I consider in this note. Specifically, I show that the RPC operation used in all these algorithms is essentially a majority vote of 3 bits, and prove the optimality of the best such algorithm. I go on to derive some theoretical bounds on the performance of these algorithms under some specific assumptions about errors.      

Telecommunication technology for the management of large scale clinical trials: the Gissi experience

The Coordinating Centre (CC) of the Gruppo Italiano per lo Studio della Sopravvivenza nell’Infarto miocardico (GISSI) used telecommunication technology to develop a computerized network system for the data management of the GISSI studies. Through a personal computer (PC), a communication program, a modem and a telephone line, the investigator in each participating centre can connect with a micro-computer at the CC, to recruit/randomize patients and download reports on the progress of the trial. In the first case, the investigator is required to answer a set of predefined questions, and thereby the system automatically checks eligibility criteria and randomly assigns the patient to a treatment arm. In the second case, once the investigator has made a choice from a list of standard reports and the relative query on CC central database, the generation, the formatting and the transfer of the selected report to the PC are executed automatically on line. The main advantages of this system are a reduction in number of mistakes in data completion and in the human and economic resources required, as well as the real time updating of participating centres. The system was successfully adopted in the GISSI-3 trial (200 Coronary Care Units and 19 394 patients enrolled), in the European arm of the CORE trial and it is currently being used in the GISSI-Prevenzione trial.     

ID3算法在军事训练成绩分析中的应用

随着部队实战化训练的深入,传统的训练成绩分析方法已不能适应科学组训的需要。该文引入射击训练实例,应用人工智能中机器学习的ID3归纳学习算法,对射击情况进行分类分析,得出影响军事训练成绩的内部原因以及其他一些结论。