Quantization-based clustering algorithm

In this paper, a quantization-based clustering algorithm (QBCA) is proposed to cluster a large number of data points efficiently. Unlike previous clustering algorithms, QBCA places more emphasis on the computation time of the algorithm. Specifically, QBCA first assigns the data points to a set of histogram bins by a quantization function. Then, it determines the initial centers of the clusters according to this point distribution. Finally, QBCA performs clustering at the histogram bin level, rather than the data point level. We also propose two approaches to improve the performance of QBCA further: (i) a shrinking process is performed on the histogram bins to reduce the number of distance computations and (ii) a hierarchical structure is constructed to perform efficient indexing on the histogram bins. Finally, we analyze the performance of QBCA theoretically and experimentally and show that the approach: (1) can be easily implemented, (2) identifies the clusters effectively and (3) outperforms most of the current state-of-the-art clustering approaches in terms of efficiency.     

Using self-organizing maps to learn geometric hash functions formodel-based object recognition

A major problem associated with geometric hashing and methods which have emerged from it is the nonuniform distribution of invariants over the hash space. In this paper, a new approach is proposed based on an elastic hash table. We proceed by distributing the hash bins over the invariants. The key idea is to associate the hash bins with the output nodes of a self-organizing feature map (SOFM) neural network which is trained using the invariants as training examples. In this way, the location of a hash bin in the space of invariants is determined by the weight vector of the node associated with the hash bin. The advantage of the proposed approach is that it is a process that adapts to the invariants through learning. Hence, it makes absolutely no assumptions about the statistical characteristics of the invariants and the geometric hash function is actually computed through learning. Furthermore, SOFM's topology preserving property ensures that the computed geometric hash function should be well behaved.     

Tree-decomposition based heuristics for the two-dimensional bin packing problem with conflicts

This paper deals with the two-dimensional bin packing problem with conflicts (BPC-2D). Given a finite set of rectangular items, an unlimited number of rectangular bins and a conflict graph, the goal is to find a conflict-free packing of the items minimizing the number of bins used. In this paper, we propose a new framework based on a tree-decomposition for solving this problem. It proceeds by decomposing a BPC-2D instance into subproblems to be solved independently. Applying this decomposition method is not straightforward, since merging partial solutions is hard. Several heuristic strategies are proposed to make an effective use of the decomposition. Computational experiments show the practical effectiveness of our approach.     

An icosahedron-based method for even binning of globally distributed remote sensing data

A new scheme is presented for binning globally distributed measurements. The scheme is based on a network of evenly distributed grid points, defined by repeated subdivision of a spherical icosahedron. Delanuany triangulation is then used to obtain bin perimeters for each grid point, which results in a network of bins that are evenly distributed across the entire globe and have uniform area. A modified winding rule is used to determine which datapoints are in which bin. This binning method is especially suited to remote sensing applications involving datasets covering polar regions, where conventional rectangular latitude/longitude bins introduce distortion and streaking into the binned data if noise is present. It also has the property that adjacent bins overlap, providing Nyquist sampling and preventing spatial aliasing. Tests on synthetic data show that this icosahedral binning scheme preserves underlying data trends and is robust to noise.     

Packing of one-dimensional bins with contiguous selection of identical items: An exact method of optimal solution

Consideration was given to the one-dimensional bin packing problem under the conditions for heterogeneity of the items put into bins and contiguity of choosing identical items for the next bin. The branch-and-bound method using the “next fit” principle and the “linear programming” method were proposed to solve it. The problem and its solution may be used to construct an improved lower bound in the problem of two-dimensional packing.     

Probe test yield optimization based on canonical correlation analysis between process control monitoring variables and probe bin variables

Process control monitoring (PCM) data provide information that is used to track abnormal processes and estimate various probe bin yields. However, multi-dimensional information has not yet been fully utilized from both PCM data and probe bins. In this paper, we proposed a canonical correlation analysis in order to investigate the relationship between multiple PCM variables and various probe bin variables. Polynomial regression was also employed as a methodology for maximizing the performance yield based on the results of the canonical correlation analysis. Two conclusions were drawn from the results of this research. First, the PCM variables that affected the probe bins were contact resistance, sheet resistance, and Isat_P4H as well as threshold voltage (Vt) during the process tuning step. Second, the typical values of Vtl_P4H and Isat_P4H should be changed in order to maximize the performance yield. The proposed method can be used for yield improvement and as a problem-solving approach for optimizing the IC process.     

A parallel multi-objective algorithm for two-dimensional bin packing with rotations and load balancing

Bin packing problems are NP-hard combinatorial optimization problems of fundamental importance in several fields, including computer science, engineering, economics, management, manufacturing, transportation, and logistics. In particular, the non-guillotine version of the single-objective two-dimensional bin packing problem with rotations is a highly complex scheduling problem that consists in packing a set of items into the minimum number of bins, where items can be rotated 90° and are characterized by having different heights and widths. Recently, some authors have proposed multi-objective formulations that also consider additional objectives, such as the balancing the bin load in order to increase its stability. The load imbalance minimization, which depends on the distribution of the items packed in them, is a critical point in many real applications. This paper analyzes how to solve two-dimensional bin packing problems with rotations and load balancing using parallel and multi-objective memetic algorithms that apply a set of search operators specifically designed to solve this problem. Results obtained using a set of test problems show the good performance of parallel and multi-objective memetic algorithms in comparison with other methods found in the literature.     

Online bin stretching with three bins

Online bin stretching is a semi-online variant of bin packing in which the algorithm has to use the same number of bins as an optimal packing, but is allowed to slightly overpack the bins. The goal is to minimize the amount of overpacking, i.e., the maximum size packed into any bin. We give an algorithm for online bin stretching with a stretching factor of \(11/8 = 1.375\) for three bins. Additionally, we present a lower bound of \(45/33 = 1.\overline{36}\) for online bin stretching on three bins and a lower bound of 19/14 for four and five bins that were discovered using a computer search.     

弱时频正交性条件下的混合矩阵盲估计

针对语音信号的弱时频正交性,提出一种基于主分量分析的混合矩阵估计方法.在时频域中,允许每个时频点存在任意多个源信号,通过对每个时频点进行主分量分析,检测只有一个源信号存在的时频点,此类时频点最大特征值对应的特征向量即为混合向量的一个估计,因此对所有估计出的混合向量进行K均值聚类,将聚类中心作为混合矩阵的估计.实验仿真表明,提出的方法提高了混合矩阵的估计精度,特别适用于估计欠定情况下的混合矩阵.     

Approximation Algorithms for Extensible Bin Packing

In a variation of bin packing called extensible bin packing, the number of bins is specified as part of the input, and bins may be extended to hold more than the usual unit capacity. The cost of a bin is 1 if it is not extended, and the size if it is extended. The goal is to pack a set of items of given sizes into the specified number of bins so as to minimize the total cost. Adapting ideas Grötschel et al. (1981), Grötschel et al. (1988), Karmarkar and Karp (1982), Murgolo (1987), we give a fully polynomial time asymptotic approximation scheme (FPTAAS) for extensible bin packing. We close with comments on the complexity of obtaining stronger results.     

Iterative approaches for solving a multi-objective 2-dimensional vector packing problem

In this paper, we address a bi-objective 2-dimensional vector packing problem (Mo2-DBPP) that calls for packing a set of items, each having two sizes in two independent dimensions, say, a weight and a height, into the minimum number of bins. The weight corresponds to a “hard” constraint that cannot be violated while the height is a “soft” constraint. The objective is to find a trade-off between the number of bins and the maximum height of a bin. This problem has various real-world applications (computer science, production planning and logistics). Based on the special structure of its Pareto front, we propose two iterative resolution approaches for solving the Mo2-DBPP. In each approach, we use several lower bounds, heuristics and metaheuristics. Computational experiments are performed on benchmarks inspired from the literature to compare the effectiveness of the two approaches.     

Hydrodynamic modeling of short-channel devices using an upwind flux vector splitting scheme

Upwind flux vector splitting is presented for hydrodynamic modeling of 1D and 2D deep-submicron semiconductor devices. This approach splits the Jacobian matrices of the hydrodynamic system into two parts corresponding to forward and backward running fluxes, and an upwind difference is applied to each split flux. Influences of the boundary discontinuity of electric field and velocity on transport results in the 2D deep-submicron devices are discussed. The study demonstrates that the developed method is capable of handling large discontinuity of the boundary conditions, and highly non-linear source terms in short-channel semiconductor devices.     

求解二维对流扩散方程的格子Boltzmann方法

针对二维对流扩散方程,基于D2Q4格子速度,用Chapman-Enskog多尺度分析技术,将时间尺度取为二阶,空间尺度取为一阶,推导了各个速度方向上的平衡态分布函数所满足的条件,给出了简单且对称的平衡态分布函数表达式,所得到的平衡态分布函数能正确地恢复出二维对流扩散方程,从而构建了一种新的求解二维对流扩散方程的D2Q4格子Boltzmann（LB）模型。用所给LB模型对扩散方程和两个不同初边界条件的对流扩散方程进行了数值求解,数值实验结果表明数值解与精确解吻合较好,与相关文献结果比较边界误差要小得多,验证了模型的有效性。     

A class of simple stochastic online bin packing algorithms

In the one-dimensional bin packing problem a list ofn items has to be packed into a minimum number of unit-capacity bins. A class of linear online algorithms for the approximate solution of bin packing with items drawn from a known probability distribution is presented. Each algorithm depends on the distribution and on a parameter controlling the performance of the algorithm. It is shown that with increasing number of items the expected performance ratio has an arbitrary small deviation from optimum.     

A new variable-sized bin packing problem

The problem of BLASTing a genome against a database of DNA sequences to identify potential relationships with other genomes can be divided into subproblems quite naturally. We consider a setting where the problem is distributed to PCs having idle time. This results in a new variant of bin packing, where a rectangle is divided into smaller rectangles that are to be packed in variable-sized bins which arrive on-line. A rectangle fits in a bin, if the sum of its height and width is no more than the size of the bin. The goal is to minimize the total size of the bins used for packing the entire rectangle.     

CHAMP: Creating heuristics via many parameters for online bin packing

The online bin packing problem is a well-known bin packing variant and which requires immediate decisions to be made for the placement of a lengthy sequence of arriving items of various sizes one at a time into fixed capacity bins without any overflow. The overall goal is maximising the average bin fullness. We investigate a ‘policy matrix’ representation, which assigns a score for each decision option independently and the option with the highest value is chosen, for one-dimensional online bin packing. A policy matrix might also be considered as a heuristic with many parameters, where each parameter value is a score. We hence effectively investigate a framework which can be used for creating heuristics via many parameters. The proposed framework combines a Genetic Algorithm optimiser, which searches the space of heuristics in policy matrix form, and an online bin packing simulator, which acts as the evaluation function. The empirical results indicate the success of the proposed approach, providing the best solutions for almost all item sequence generators used during the experiments. We also present a novel fitness landscape analysis on the search space of policies. This study hence gives evidence of the potential for automated discovery by intelligent systems of powerful heuristics for online problems; reducing the need for expensive use of human expertise.     

Defect spatial pattern recognition using a hybrid SOM–SVM approach in semiconductor manufacturing

As manufacturing geometries continue to shrink and circuit performance increases, fast fault detection and semiconductor yield improvement is of increasing concern. Circuits must be controlled to reduce parametric yield loss, and the resulting circuits tested to guarantee that they meet specifications. In this paper, a hybrid approach that integrates the Self-Organizing Map and Support Vector Machine for wafer bin map classification is proposed. The log odds ratio test is employed as a spatial clustering measurement preprocessor to distinguish between the systematic and random wafer bin map distribution. After the smoothing step is performed on the wafer bin map, features such as co-occurrence matrix and moment invariants are extracted. The wafer bin maps are then clustered with the Self-Organizing Map using the aforementioned features. The Support Vector Machine is then applied to classify the wafer bin maps to identify the manufacturing defects. The proposed method can transform a large number of wafer bin maps into a small group of specific failure patterns and thus shorten the time and scope for troubleshooting to yield improvement. Real data on over 3000 wafers were applied to the proposed approach. The experimental results show that our approach can obtain over 90% classification accuracy and outperform back-propagation neural network.     

局内装箱算法综述

系统地介绍了局内装箱算法,归纳了其发展过程中的各种改进如数据分配模型、箱的划分等。阐述了该算法在工作分配、任务调度以及日常生活中的计划、包装、调度等计算机工程领域的应用。最后,对局内装箱算法提出了进一步的研究方向。     

A finite element penalty method for the linearized viscoelastic Oldroyd fluid motion equations

In this paper, a fully discrete finite element penalty method is considered for the two-dimensional linearized viscoelastic fluid motion equations, arising from the Oldroyd model for the non-Newton fluid flows. With the finite element method for the spatial discretization and the backward Euler scheme for the temporal discretization, the velocity and pressure are decoupled in this method, which leads to a large reduction of the computational scale. Under some realistic assumptions, the unconditional stability of the fully discrete scheme is proved. Moreover, the optimal error estimates are obtained, which are better than the existing results. Finally, some numerical results are given to verify the theoretical analysis. The difference between the motion of the Newton and non-Newton fluid is also observed.     

Variable neighbourhood search for the variable sized bin packing problem

The variable sized bin packing problem is a generalisation of the one-dimensional bin packing problem. Given is a set of weighted items, which must be packed into a minimum-cost set of bins of variable sizes and costs. This problem has practical applications, for example, in packing, transportation planning, and cutting. In this work we propose a variable neighbourhood search metaheuristic for tackling the variable sized bin packing problem. The presented algorithm can be seen as a hybrid metaheuristic, because it makes use of lower bounding techniques and dynamic programming in various algorithmic components. An extensive experimentation on a diverse set of problem instances shows that the proposed algorithm is very competitive with current state-of-the-art approaches.