Large deviation principles for Euclidean functionals and other nearly additive processes

We prove a large deviation principle for a process indexed by cubes of the multidimensional integer lattice or Euclidean space, under approximate additivity and regularity hypotheses. The rate function is the convex dual of the limiting logarithmic moment generating function. In some applications the rate function can be expressed in terms of relative entropy. The general result applies to processes in Euclidean combinatorial optimization, statistical mechanics, and computational geometry. Examples include the length of the minimal tour (the traveling salesman problem), the length of the minimal matching graph, the length of the minimal spanning tree, the length of the k-nearest neighbors graph, and the free energy of a short-range spin glass model. Received: 3 April 1999 / Revised version: 23 June 1999 / Published online: 8 May 2001     

Data compression and histograms

Summary In this paper, the relationship between code length and the selection of the number of bins for a histogram density is considered for a sequence of iid observations on [0,1]. First, we use a shortest code length criterion to select the number of bins for a histogram. A uniform almost sure asymptotic expansion for the code length is given and it is used to prove the asymptotic optimality of the selection rule. In addition, the selection rule is consistent if the true density is uniform [0,1]. Secondly, we deal with the problem: what is the best achievable average code length with underlying density functionf? Minimax lower bounds are derived for the average code length over certain smooth classes of underlying densitiesf. For the smooth class with bounded first derivatives, the rate in the lower bound is shown to be achieved by a code based on a sequence of histograms whose number of bins is changed predictively. Moreover, this best code can be modified to ensure that the almost sure version of the code length has asymptotically the same behavior as its expected value, i.e., the average code length.Research supported in part by NSF grant DMS-8701426Research supported in part by NSF grant DMS-8802378     

Rigidity in the class of orientable compact surfaces of minimal total absolute curvature

Consider an orientable compact surface in three-dimensional Euclidean space with minimum total absolute curvature. If the Gaussian curvature changes sign to finite order and satisfies a nondegeneracy condition along closed asymptotic curves, we show that any other isometric surface differs by at most a Euclidean motion.     

Eigenvalue asymptotics for an elliptic boundary problem involving an indefinite weight

We are concerned here with the eigenvalue asymptotics for a non-selfadjoint elliptic boundary problem involving an indefinite weight function which vanishes on a set of positive measure. The asymptotic behaviour of the eigenvalues is well known for the case of second order operators. However for higher order operators, results have only been established under the restriction that the order of the operator exceeds the dimension of the underlying Euclidean space in which the problem is set. In this paper we establish the eigenvalue asymptotics for the case of higher order operators without any such restriction.Supported in part by the John Knopfmacher Centre for Applicable Analysis and Number Theory, University of the Witwatersrand.     

三维欧氏Steiner最小树的Delaunay四面体网格混合智能算法

Steiner最小树问题是组合优化中经典的NP难题,在许多实际问题中有着广泛的应用,而三维欧氏Steiner最小树问题是对二维欧氏Steiner最小树问题的推广。由于三维欧氏Steiner树问题的求解非常困难,至今为止的相关成果较为少见。本文针对该问题,利用Delaunay四面体网格剖分技术,提出了一种混合型智能求解方法,不仅可以尽量避免拓扑结构陷入局部最优,且对较大规模的问题求解亦有良好的效果。算法在Matlab环境下编程实现,经实例测试,获得了满意的效果。     

An optimal partition problem related to nonlinear eigenvalues

We extend to the case of many competing densities the results of the paper (Ann. Inst. H. Poincaré 6 (2002)). More precisely, we are concerned with an optimal partition problem in N-dimensional domains related to the method of nonlinear eigenvalues introduced by Nehari, (Acta Math. 105 (1961)). We prove existence of the minimal partition and some extremality conditions. Moreover, in the case of two-dimensional domains we give an asymptotic formula near the multiple intersection points. Finally, we show some connections between the variational problem and the behavior of competing species systems with large interaction.     

Attractor information for discrete dynamical systems by means of optimal discrete Galerkin bases

We introduce local adaptive discrete Galerkin bases as a basis set in order to obtain geometrical and topological information about attractors of discrete dynamical systems. The asymptotic behavior of these systems is described by the reconstruction of their attractors in a finite dimensional Euclidean space and by the attractor topological characteristics including the minimal embedding dimension and its local dimension. We evaluate numerically the applicability of our geometrical and topological results by examining two examples: a dissipative discrete system and a nonlinear discrete predator–prey model that includes several types of self-limitation on the prey.     

Selecting mixed-effects models based on a generalized information criterion

The generalized information criterion (GIC) proposed by Rao and Wu [A strongly consistent procedure for model selection in a regression problem, Biometrika 76 (1989) 369-374] is a generalization of Akaike's information criterion (AIC) and the Bayesian information criterion (BIC). In this paper, we extend the GIC to select linear mixed-effects models that are widely applied in analyzing longitudinal data. The procedure for selecting fixed effects and random effects based on the extended GIC is provided. The asymptotic behavior of the extended GIC method for selecting fixed effects is studied. We prove that, under mild conditions, the selection procedure is asymptotically loss efficient regardless of the existence of a true model and consistent if a true model exists. A simulation study is carried out to empirically evaluate the performance of the extended GIC procedure. The results from the simulation show that if the signal-to-noise ratio is moderate or high, the percentages of choosing the correct fixed effects by the GIC procedure are close to one for finite samples, while the procedure performs relatively poorly when it is used to select random effects.     

Minimum Networks for Four Points in Space

The minimum network problem (Steiner tree problem) in space is much harder than the one in the Euclidean plane. The Steiner tree problem for four points in the plane has been well studied. In contrast, very few results are known on this simple Steiner problem in 3D-space. In the first part of this paper we analyze the difficulties of the Steiner problem in space. From this analysis we introduce a new concept — Simpson intersections, and derive a system of iteration formulae for computing Simpson intersections. Using Simpson intersections the Steiner points can be determined by solving quadratic equations. As well this new computational method makes it easy to check the impossibility of computing Steiner trees on 4-point sets by radicals. At the end of the first part we consider some special cases (planar and symmetric 3D-cases) that can be solved by radicals. The Steiner ratio problem is to find the minimum ratio of the length of a Steiner minimal tree to the length of a minimal spanning tree. This ratio problem in the Euclidean plane was solved by D. Z. Du and F. K. Hwang in 1990, but the problem in 3D-space is still open. In 1995 W.D. Smith and J.M. Smith conjectured that the Steiner ratio for 4-point sets in 3D-space is achieved by regular tetrahedra. In the second part of this paper, using the variational method, we give a proof of this conjecture.     

Intersection theorems under dimension constraints

In Ahlswede et al. [Discrete Math. 273(1-3) (2003) 9-21] we posed a series of extremal (set system) problems under dimension constraints. In the present paper, we study one of them: the intersection problem. The geometrical formulation of our problem is as follows. Given integers 0?t, k?n determine or estimate the maximum number of (0,1)-vectors in a k-dimensional subspace of the Euclidean n-space Rⁿ, such that the inner product (“intersection”) of any two is at least t. Also we are interested in the restricted (or the uniform) case of the problem; namely, the problem considered for the (0,1)-vectors of the same weight ω.The paper consists of two parts, which concern similar questions but are essentially independent with respect to the methods used.In Part I, we consider the unrestricted case of the problem. Surprisingly, in this case the problem can be reduced to a weighted version of the intersection problem for systems of finite sets. A general conjecture for this problem is proved for the cases mentioned in Ahlswede et al. [Discrete Math. 273(1-3) (2003) 9-21]. We also consider a diametric problem under dimension constraint.In Part II, we study the restricted case and solve the problem for t=1 and k<2ω, and also for any fixed 1?t?ω and k large.     

Locally minimal uniformly oriented shortest networks

The Steiner problem in a λ-plane is the problem of constructing a minimum length network interconnecting a given set of nodes (called terminals), with the constraint that all line segments in the network have slopes chosen from λ uniform orientations in the plane. This network is referred to as a minimum λ-tree. The problem is a generalization of the classical Euclidean and rectilinear Steiner tree problems, with important applications to VLSI wiring design.A λ-tree is said to be locally minimal if its length cannot be reduced by small perturbations of its Steiner points. In this paper we prove that a λ-tree is locally minimal if and only if the length of each path in the tree cannot be reduced under a special parallel perturbation on paths known as a shift. This proves a conjecture on necessary and sufficient conditions for locally minimal λ-trees raised in [M. Brazil, D.A. Thomas, J.F. Weng, Forbidden subpaths for Steiner minimum networks in uniform orientation metrics, Networks 39 (2002) 186-222]. For any path P in a λ-tree T, we then find a simple condition, based on the sum of all angles on one side of P, to determine whether a shift on P reduces, preserves, or increases the length of T. This result improves on our previous forbidden paths results in [M. Brazil, D.A. Thomas, J.F. Weng, Forbidden subpaths for Steiner minimum networks in uniform orientation metrics, Networks 39 (2002) 186-222].     

On the asymptotic behavior of the energy for the wave equations with time depending coefficients

We consider the asymptotic behavior of the total energy of solutions to the Cauchy problem for wave equations with time dependent propagation speed. The main purpose of this paper is that the asymptotic behavior of the total energy is dominated by the following properties of the coefficient: order of the differentiability, behavior of the derivatives as t → ∞ and stabilization of the amplitude described by an integral. Moreover, the optimality of these properties are ensured by actual examples. Supported by Grants-in-Aid for Young Scientists (B) (No.16740098), The Ministry of Education, Culture, Sports, Science and Technology.     

Complete linear Weingarten surfaces of Bryant type. A Plateau problem at infinity

In this paper we study a large class of Weingarten surfaces which includes the constant mean curvature one surfaces and flat surfaces in the hyperbolic 3-space. We show that these surfaces can be parametrized by holomorphic data like minimal surfaces in the Euclidean 3-space and we use it to study their completeness. We also establish some existence and uniqueness theorems by studing the Plateau problem at infinity: when is a given curve on the ideal boundary the asymptotic boundary of a complete surface in our family? and, how many embedded solutions are there?

     

The mean number of steps in the Euclidean algorithm with odd partial quotients

The length of the continued-fraction expansion of a rational number with odd partial quotients is expressed via the Gauss-Kuz’min statistics for the classical continued fraction. This has made it possible to prove asymptotic formulas, similar to those already known for the classical Euclidean algorithm, for the mean length of the Euclidean algorithm with odd partial quotients.     

Axiomatizations of the Euclidean compromise solution

A multicriteria optimization problem is one of choosing an alternative that optimizes several—possibly conflicting—objective functions simultaneously. The utopia point of a multicriteria optimization problem is the vector that specifies for each objective function the most favorable feasible value. The Euclidean compromise solution in multicriteria optimization is a solution that selects from a feasible set the alternative such that its vector of criteria values has minimal Euclidean distance to the utopia point. This paper provides several axiomatic characterizations of the Euclidean compromise solution that are based on consistency properties.     

Large time behaviors of hot spots for the heat equation with a potential

We consider the Cauchy problem of the heat equation with a potential which behaves like the inverse square at infinity. In this paper we study the large time behavior of hot spots of the solutions for the Cauchy problem, by using the asymptotic behavior of the potential at the space infinity.     

Self-similar solutions for the LSW model with encounters

The LSW model with encounters has been suggested by Lifshitz and Slyozov as a regularization of their classical mean-field model for domain coarsening to obtain universal self-similar long-time behavior. We rigorously establish that an exponentially decaying self-similar solution to this model exist, and show that this solutions is isolated in a certain function space. Our proof relies on setting up a suitable fixed-point problem in an appropriate function space and careful asymptotic estimates of the solution to a corresponding homogeneous problem.     

A boundary layer problem arising in gravity-driven laminar film flow of power-law fluids along vertical walls

A rigorous mathematical analysis is given for a boundary layer problem for a third-order nonlinear ordinary differential equation, which arises in gravity-driven laminar film flow of power-law fluids along vertical walls. Firstly, the problem is transformed into a singular nonlinear two-point boundary value problem of second order. Next, the latter is proved to have a unique positive solution, for which some estimates are established. Finally, the result above-mentioned is turned over to the original problem. The conclusion of this paper is that the boundary layer problem has a unique normal solution if the power-law index is less than or equal to one and a generalized normal solution if the power-law index is greater than one. Also the asymptotic behavior of the normal solution at the infinity is displayed.The work was supported by NNSF of China.     

Boundary behavior of solutions for the degenerate logistic type elliptic problem with boundary blow-up

By the Karamata regular variation theory and constructing comparison function, we show the exact asymptotic behavior of solutions for the degenerate logistic type elliptic problem with boundary blow-up.     

A bivariate interval censorship model for partnership formation

We consider a statistical problem of estimating a bivariate age distribution of newly formed partnership. The study is motivated by a type of data that consist of uncensored, right-censored, left-censored, interval-censored and missing observations in the coordinates of a bivariate random vector. A model is proposed for formulating such type of data. A feasible algorithm to estimate the generalized MLE (GMLE) of the bivariate distribution function is also proposed. We establish asymptotic properties for the GMLE under a discrete assumption on the underlying distributions and apply the method to the data set.