A branch-and-bound method for the minimum k−enclosing ball problem

The minimum k-enclosing ball problem seeks the ball with smallest radius that contains at least k of m given points. This problem is NP-hard. We present a branch-and-bound algorithm on the tree of the subsets of k points to solve this problem. Our method is able to solve the problem exactly in a short amount of time for small and medium sized datasets.     

氦原子与非对称替代氢分子碰撞(E=0.3eV)角分布计算

用密耦方法计算了非对称同位素替代分子与氦原子碰撞(He-HD,HT,DT)转动激发,当入射能量E=0.3 eV时,得到了上述碰撞体系的微分散射截面或角分布.基于上述理论计算,讨论了原子与双原子分子碰撞的同位素效应.     

超尺寸物品装箱问题及其算法

本文探讨一类新装箱问题-超尺寸物品装箱问题。针对实际解决该问题的两涉法，我们提出了一个评价效率更高的目标函数，证明了在此目标函数下两步法的渐近最坏比不小于2，并给出了渐近量坏比与拆分次数的关系。最后本文提出了一种不同于两步法的新在线算法MA，证明了在新目标函数下其渐近最坏比不超过7/4。     

Fine Dry Grinding of Zeolite in a Laboratory Ball Mill

This paper presents the importance and usage of natural zeolites, which was recently recognized in the industry. Therefore, the grinding properties of natural zeolite were studied with the emphasis on a kinetic study in a ball mill. The experimental mill employed was laboratory sized, 200 mm diameter, 191 mm length, providing a total mill volume of 6000 cm³, with a total mass of 5.62 kg of steel balls of 25 mm diameter with a charge of 20% of the mill volume and with a rotation speed of 76 rpm. The breakage parameters were determined by using single sized feed fractions of ?850+600 μm, ?600+425 μm, and ?425+300 μm for the zeolite samples. The S_i (specific rate of breakage) and B_{i, j} (primary breakage distribution) values were obtained for those feed size fractions in order to predict the product size distributions by simulation for comparison to the experimental data. From the experimental results, S_i values increased as the feed sizes became coarser, i.e., the highest S_i value was 0.85 min^?1 for ?850+600 μm, while the lowest S_i value was 0.65 min^?1 for ?425+300 μm feed ground in the mill. The B_{i, j} values obtained for the zeolite sample were γ=0.84, ?=0.61, and β=4.25. The breakage parameters obtained showed that the zeolite is broken faster than quartz and slower than calcite and barite in terms of the a_T values reported previously at the same experimental conditions. The simulations of the product size distributions of zeolite were in good agreement with the experimental data using a standard ball mill simulation program. The slowing‐down effect was also seen in the mill after 4 min. of grinding.     

Experimental investigation of time-dependent cavitation in an oscillatory squeeze film

The occurrence of time-dependent cavitation and tensile stress in an oscillatory oil squeeze film were investigated experimentally. The test apparatus was a simple thrust bearing consisting of two parallel circular plates separated by a thin viscous oil film. During the test, one plate was at rest while the other (transparent) oscillated in a direction normal to its surface. This test configuration was chosen to avoid the rotational motion and complicated geometry of a squeeze film journal bearing. The frequency of oscillation was in the range of 5 to 50 Hz and was controlled by an electro-magnetic exciter. The process of cavity formation and its subsequent development was recorded by a high-speed video camera. Concomitant pressure in the oil film was measured both within and without the cavitation region. It was found that both tensile stress and cavities existed in a squeeze film under certain working conditions.     

A Hybrid Improvement Heuristic for the One-Dimensional Bin Packing Problem

We propose in this work a hybrid improvement procedure for the bin packing problem. This heuristic has several features: the use of lower bounding strategies; the generation of initial solutions by reference to the dual min-max problem; the use of load redistribution based on dominance, differencing, and unbalancing; and the inclusion of an improvement process utilizing tabu search. Encouraging results have been obtained for a very wide range of benchmark instances, illustrating the robustness of the algorithm. The hybrid improvement procedure compares favourably with all other heuristics in the literature. It improved the best known solutions for many of the benchmark instances and found the largest number of optimal solutions with respect to the other available approximate algorithms.     

PACKING PAIRS BY QUINTUPLES:THE CASE OF ZERO CONGRUENCE MOD 4

ＰＡＣＫＩＮＧＰＡＩＲＳＢＹＱＵＩＮＴＵＰＬＥＳ：ＴＨＥＣＡＳＥＯＦＺＥＲＯＣＯＮＧＲＵＥＮＣＥＭＯＤ４ＹＩＮＪＩＡＮＸＩＮＧＡｂｓｔｒａｃｔ：ＬｅｔＤ（ｖ）ｄｅｎｏｔｅｔｈｅｍａｘｉｍｕｍｎｕｍｂｅｒｏｆｑｕｉｎｔｕｐｌｅｓｏｆａｖ－ｓｅｔｏｆｐｏ...     

A Constraint Programming Approach to Extract the Maximum Number of Non-Overlapping Test Forms

This paper introduces a novel approach for extracting the maximum number of non-overlapping test forms from a large collection of overlapping test sections assembled from a given item bank. The approach involves solving maximum set packing problems (MSPs). A branch-and-bound MSP algorithm is developed along with techniques adapted from constraint programming to estimate lower and upper bounds on the optimal MSP solution. The algorithm is general and can be applied in other applications including combinatorial auctions. The results of computer simulations and experiments with an operational item bank are presented. An erratum to this article is available at .     

Measuring Light Field of Light Source with High Directional Resolution Using Mirrored Ball and Pinhole Camera

This paper presents a method of measuring a light field of a light source with high directional resolution using a mirrored ball and a pinhole camera. The light field describes a spatial and directional distribution of radiances from the light source. The directional distribution is expanded by a reflection on the mirrored ball, and the radiances are measured by a charge-coupled device (CCD) camera with a pinhole lens. The light source is laterally moved by a robot arm to measure the directionally expanded light field, and each pixel on a CCD can obtain the radiances from the light source through the pinhole lens with high directional resolution. The light field is estimated from the pixel value and the position of each pixel using a ray tracing technique. The light field of a krypton lamp was experimentally measured by the proposed method, and the accuracy of the measurement was evaluated against the irradiances measured by a spectro-radiometer at sample points.     

Packing two disks into a polygonal environment

We consider the following problem. Given a polygon P, possibly with holes, and having n vertices, compute a pair of equal radius disks that do not intersect each other, are contained in P, and whose radius is maximized. Our main result is a simple randomized algorithm whose expected running time, on any input, is O(nlogn). This is optimal in the algebraic decision tree model of computation.