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.     

A complete set of numerical invariants for a subfactor

We show that certain numerical invariants associated naturally to a subfactor planar algebra constitute a complete family in the sense of determining the isomorphism class of the subfactor planar algebra.In the course of the proof, we show also that planar algebra isomorphisms of subfactor planar algebras can always be chosen to be ∗-preserving. This latter statement generalises the fact that ‘Hopf algebra isomorphisms of finite-dimensional Kac algebras can be chosen to be ∗-preserving’.     

A co‐ordinate system independent streamwise upwind method for fluid flow computation

A new co‐ordinate invariant streamwise upwind formulation for convection dominated flows is developed. The eddy diffusivity/viscosity is added directly to the equations in order to remove the oscillations in the solution. The equations then can be solved by any high‐order scheme and the solution retains the accuracy of the high‐order scheme. The accuracy and reduced lateral thickness growth rate are demonstrated with several numerical examples, including pure convective flows and lid‐driven cavity flow. The lateral spreading due to the numerical diffusion is controlled by the anisotropic tensor. Copyright © 2004 John Wiley & Sons, Ltd.     

About the Notion of Semiring of Sets

We introduce a generalized notion of semiring and prove that all known properties that semirings have according to the old definition are preserved.     

Point-to-Periodic and Periodic-to-Periodic Connections

In this work we consider computing and continuing connecting orbits in parameter dependent dynamical systems. We give details of algorithms for computing connections between equilibria and periodic orbits, and between periodic orbits. The theoretical foundation for these techniques is given by the seminal work of Beyn in 1994, “On well-posed problems for connecting orbits in dynamical systems”, where a numerical technique is also proposed. Our algorithms consist of splitting the computation of the connection from that of the periodic orbit(s). To set up appropriate boundary conditions, we follow the algorithmic approach used by Demmel, Dieci, and Friedman, for the case of connecting orbits between equilibria, and we construct and exploit the smooth block Schur decomposition of the monodromy matrices associated to the periodic orbits. Numerical examples illustrate the performance of the algorithms. This revised version was published online in July 2006 with corrections to the Cover Date.     

The PDE-preserving operators on nuclearly entire functions of bounded type

The PDE-preserving operators O on the space of nuclearly entire functions of bounded type H_Nb(E) on a Banach space E are characterized. An operator is PDE-preserving when it preserves homogenous solutions to homogeneous convolution equations. We establish a one to one correspondence between O and a set Σ of sequences of entire functionals, i.e. exponential type functions. In this way, algebraic structures on Σ, such as ring structures, can be carried over to O and vice versa. In particular, it follows that O is a non-commutative ring (algebra) with unity with respect to composition and the convolution operators form a commutative subring (subalgebra). We discuss range and kernel properties, for the operators in O, and characterize the projectors (onto polynomial spaces) in O by determining the corresponding elements in Σ. This revised version was published online in June 2006 with corrections to the Cover Date.     

双阱结构含时量子输运的微扰论及输运方程

利用Lewis-Riesenfeld不变量理论和与不变量有关的幺正变换方法研究了双阱结构含时量子 输运的微扰论.获得了双阱内含时薛定谔方程的精确解的完备集，在此基础上，把双阱与左 右热库的相互作用作为微挠，获得了双阱结构一阶近似下的输运方程，并在绝热近似下提供 了一种用于研究量子输运过程中几何相因子(Berry相因子)的方法. 关键词： 含时量子输运 输运方程 不变量 几何相因子     

Geometric separation and exact solutions for the parameterized independent set problem on disk graphs

We consider the parameterized problem, whether for a given set  of n disks (of bounded radius ratio) in the Euclidean plane there exists a set of k non-intersecting disks. For this problem, we expose an algorithm running in time that is—to our knowledge—the first algorithm with running time bounded by an exponential with a sublinear exponent. For λ-precision disk graphs of bounded radius ratio, we show that the problem is fixed parameter tractable with a running time  . The results are based on problem kernelization and a new “geometric ( -separator) theorem” which holds for all disk graphs of bounded radius ratio. The presented algorithm then performs, in a first step, a “geometric problem kernelization” and, in a second step, uses divide-and-conquer based on our new “geometric separator theorem.”     

无界区域R1上推广的B-BBM方程的整体吸引子

本文研究了无界区域R^1上推广的B—BBM方程的长时间动力学行为，证明了该方程整体吸引子的存在性．     

广义向量均衡问题的解与解集的凸性

引进集值映射的锥真拟凹概念，讨论一类具有集值映射的广义向量衡问题解的存在性与解集的凸性。