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.     

二叉分裂算法的随机路径长度

用泊松变换的方法研究了由二叉分裂算法所产生的随机树上的随机路径的长度,首次得到了关于其数学期望的确切表达式.在此基础上,对该期望的渐近性状进行了分析,证明了当被分裂的集合的大小n趋于无穷时,随机路径长度的期望具有log2n的阶.     

The supersymmetric WKB approximation of ring-shaped oscillator potential in r and θ dimensions with spherical polar coordinates

According to calculation of the energy spectrum of ring-shape oscillator potential by using the supersymmetric WKB approximation, it is shown that the energy spectrum of some noncentral separable potentials can be exactly obtained in r and θ dimensions by above method.     

Linearized and rational approximation method for solving non‐linear Burgers' equation

A new numerical method called linearized and rational approximation method is presented to solve non‐linear evolution equations. The utility of the method is demonstrated for the case of differentiation of functions involving steep gradients. The solution of Burgers' equation is presented to illustrate the effectiveness of the technique for the solution of non‐linear evolution equations exhibiting nearly discontinuous solutions. Copyright © 2004 John Wiley & Sons, Ltd.     

Construction of best Bregman approximations in reflexive Banach spaces

An iterative method is proposed to construct the Bregman projection of a point onto a countable intersection of closed convex sets in a reflexive Banach space.

     

Eikonal Approximation to 5D Wave Equations and the 4D Space-Time Metric

We apply a method analogous to the eikonal approximation to the Maxwell wave equations in an inhomogeneous anisotropic medium and geodesic motion in a three dimensional Riemannian manifold, using a method which identifies the symplectic structure of the corresponding mechanics, to the five dimensional generalization of Maxwell theory required by the gauge invariance of Stueckelberg's covariant classical and quantum dynamics. In this way, we demonstrate, in the eikonal approximation, the existence of geodesic motion for the flow of mass in a four dimensional pseudo-Riemannian manifold. These results provide a foundation for the geometrical optics of the five dimensional radiation theory and establish a model in which there is mass flow along geodesics. We then discuss the interesting case of relativistic quantum theory in an anisotropic medium as well. In this case the eikonal approximation to the relativistic quantum mechanical current coincides with the geodesic flow governed by the pseudo-Riemannian metric obtained from the eikonal approximation to solutions of the Stueckelberg–Schrödinger equation. The locally symplectic structure which emerges is that of a generally covariant form of Stueckelberg's mechanics on this manifold.     

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.     

The Cosmological Constant in the Framework of Gravito-Magnetodynamic Waves in Weak Gravitational Fields

Using the linearization of Einstein's equations for weak gravitational fields, a specific model of gravito-magnetofluid is elaborated. The study of wave formation and propagation in such a medium is necessarily connected to the existence of the cosmological constant.     

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.