Polynomial-time approximation schemes for packing and piercing fat objects

We consider two problems: given a collection of n fat objects in a fixed dimension, (1) ( packing) find the maximum subcollection of pairwise disjoint objects, and (2) ( piercing) find the minimum point set that intersects every object. Recently, Erlebach, Jansen, and Seidel gave a polynomial-time approximation scheme (PTAS) for the packing problem, based on a shifted hierarchical subdivision method. Using shifted quadtrees, we describe a similar algorithm for packing but with a smaller time bound. Erlebach et al.'s algorithm requires polynomial space. We describe a different algorithm, based on geometric separators, that requires only linear space. This algorithm can also be applied to piercing, yielding the first PTAS for that problem.     

基于小波包分析及支持向量机的超音速目标识别方法研究

提出了基于小波包分析及支持向量机的超音速目标识别方法 .通过 5 .5 6mm ,7.6 2mm和 12 .7mm三种枪弹试验获取信号 ,用小波包分解激波信号 ,统计每个频带的能量特征 ,用支持向量机方法训练测试样本 ,获得了很好的分类效果 .仿真结果表明基于超音速飞行体产生的激波信号来识别目标是可行的 .     

Stability analysis of abnormal multiplication of plankton using parameter identification technique

This paper presents the mathematical approach for the abnormal multiplication of plankton. An abnormal multiplication can be expressed as an unstable problem and the stability of the system is investigated by introducing eigenvalues of a mathematical equation. The stability of the system can be judged by an eigenvalue based on the Lyapunov's stability theory. In this paper, the Arnoldi‐QR method is used to obtain eigenvalues and eigenvectors of the system. The mode superposition method is employed to create spatial distribution needed to analyse the stability. To obtain the objective eigenvalue, the parameter identification technique is employed. The finite element method is used for the discretization in space. Lake Kasumigaura, which is located in Ibaraki Prefecture in Japan, is selected and actual data in 1975, 1976, 1991 and 2000 are used in order to investigate the stability of the specified lake in Japan. Copyright © 2004 John Wiley & Sons, Ltd.     

Five-step phase-shifting algorithms with unknown values of phase shift

The presented work offers new algorithms for phase evaluation in interferometric measurements. Several phase-shifting algorithms with an arbitrary but constant phase-shift between captured intensity frames are proposed. These phase calculation algorithms need to measure five frames of the intensity of the interference field. The algorithms are similarly derived as so called Carré algorithm. The phase evaluation process then does not depend on the linear phase shift errors. Furthermore, the detailed analysis of the algorithms with respect to most important factors, which affect interferometric measurements, is carried out. It is also studied the dependency of the evaluation algorithms on the phase shift values, and the proposed phase calculation algorithms are compared with respect to the resulting phase errors. The influence of most important factors in the measurement and evaluation process was simulated as systematic and random errors using a proposed mathematical model.     

Convergent Algorithm Based on Progressive Regularization for Solving Pseudomonotone Variational Inequalities

In this paper, we extend the Moreau-Yosida regularization of monotone variational inequalities to the case of weakly monotone and pseudomonotone operators. With these properties, the regularized operator satisfies the pseudo-Dunn property with respect to any solution of the variational inequality problem. As a consequence, the regularized version of the auxiliary problem algorithm converges. In this case, when the operator involved in the variational inequality problem is Lipschitz continuous (a property stronger than weak monotonicity) and pseudomonotone, we prove the convergence of the progressive regularization introduced in Refs. 1, 2.     

Algorithms for Finite and Semi-Infinite Min–Max–Min Problems Using Adaptive Smoothing Techniques

We develop two implementable algorithms, the first for the solution of finite and the second for the solution of semi-infinite min-max-min problems. A smoothing technique (together with discretization for the semi-infinite case) is used to construct a sequence of approximating finite min-max problems, which are solved with increasing precision. The smoothing and discretization approximations are initially coarse, but are made progressively finer as the number of iterations is increased. This reduces the potential ill-conditioning due to high smoothing precision parameter values and computational cost due to high levels of discretization. The behavior of the algorithms is illustrated with three semi-infinite numerical examples.     

Qualitative Theory and Identification of Dynamic System with One Degree of Freedom

Dynamic systems described by nonlinear differential equations of the second order are studied. It is assumed that certain preliminary information on the dissipative or elastic characteristics of systems is known. A new approach is demonstrated to obtaining full information on unknown or partially known characteristics of a system from measurements of not only displacements but also velocities and accelerations __________ Published in Prikladnaya Mekhanika, Vol. 41, No. 6, pp. 139–143, June 2005.     

Robust Adaptive Identification of Fuzzy Systems with Uncertain Data

This study presents a method of adaptive identification of parameters describing Sugeno fuzzy inference system in presence of bounded disturbances while maintaining the readability and interpretability of the fuzzy model during and after identification. This method do not require any a priori knowledge of a bound on the disturbance and noise and of a bound on the unknown parameters values. The method can be used for the robust and adaptive identification of slowly time varying nonlinear systems using fuzzy inference systems. The suggested method was used to build a fuzzy expert system that approximates the functional relationship between physical fitness and some of the measurable physiological parameters by their real measurements and opinion (human-experiences) of a medical expert.     

Multicuts in unweighted graphs and digraphs with bounded degree and bounded tree-width

The Multicut problem can be defined as: given a graph G and a collection of pairs of distinct vertices {s_i,t_i} of G, find a minimum set of edges of G whose removal disconnects each s_i from the corresponding t_i. Multicut is known to be NP-hard and Max SNP-hard even when the input graph is restricted to being a tree. The main result of the paper is a polynomial-time approximation scheme (PTAS) for Multicut in unweighted graphs with bounded degree and bounded tree-width. That is, for any ε>0, we present a polynomial-time (1+ε)-approximation algorithm. In the particular case when the input is a bounded-degree tree, we have a linear-time implementation of the algorithm. We also provide some hardness results: we prove that Multicut is still NP-hard for binary trees and that it is Max SNP-hard if we drop any of the three conditions (unweighted, bounded-degree, bounded tree-width). Finally we show that some of these results extend to the vertex version of Multicut and to a directed version of Multicut.     

硅色敏器件对复色光色差辨识能力的数值分析

对复色光的光谱功率分布和色敏器件光谱响应的实验曲线进行了函数拟合，采用Mathematica 4．2计算了具有不同峰值波长和半高宽的高斯分布的复色光在色敏器件中产生的电流比．计算结果表明，待测复色光的峰值波长和半高宽变化对两种典型的色敏器件的输出信号影响的权重比分别为100：1和10：1。权重比说明色敏器件的输出电流比随峰值波长和半高宽的变化非常灵敏，但两者权重不同，其中峰值波长的变化影响更为显著，是影响复色光颜色变化的主要因素．数值分析的结果表明，硅双结色敏器件对复色光色差有良好的辨识能力．两种器件权重比的差异说明了器件制作工艺与其辨识能力的关系，为器件合理设计提供了理论依据．