Tree spanners in planar graphs

A tree t-spanner of a graph G is a spanning subtree T of G in which the distance between every pair of vertices is at most t times their distance in G. Spanner problems have received some attention, mostly in the context of communication networks. It is known that for general unweighted graphs, the problem of deciding the existence of a tree t-spanner can be solved in polynomial time for t=2, while it is NP-hard for any t⩾4; the case t=3 is open, but has been conjectured to be hard. In this paper, we consider tree spanners in planar graphs. We show that even for planar unweighted graphs, it is NP-hard to determine the minimum t for which a tree t-spanner exists. On the other hand, we give a polynomial algorithm for any fixed t that decides for planar unweighted graphs with bounded face length whether there is a tree t-spanner. Furthermore, we prove that it can be decided in polynomial time whether a planar unweighted graph has a tree t-spanner for t=3.     

Strong metric subregularity of mappings in variational analysis and optimization

Although the property of strong metric subregularity of set-valued mappings has been present in the literature under various names and with various (equivalent) definitions for more than two decades, it has attracted much less attention than its older “siblings”, the metric regularity and the strong (metric) regularity. The purpose of this paper is to show that the strong metric subregularity shares the main features of these two most popular regularity properties and is not less instrumental in applications. We show that the strong metric subregularity of a mapping F acting between metric spaces is stable under perturbations of the form $f+F$, where f is a function with a small calmness constant. This result is parallel to the Lyusternik–Graves theorem for metric regularity and to the Robinson theorem for strong regularity, where the perturbations are represented by a function f with a small Lipschitz constant. Then we study perturbation stability of the same kind for mappings acting between Banach spaces, where f is not necessarily differentiable but admits a set-valued derivative-like approximation. Strong metric q-subregularity is also considered, where q is a positive real constant appearing as exponent in the definition. Rockafellar's criterion for strong metric subregularity involving injectivity of the graphical derivative is extended to mappings acting in infinite-dimensional spaces. A sufficient condition for strong metric subregularity is established in terms of surjectivity of the Fréchet coderivative, and it is shown by a counterexample that surjectivity of the limiting coderivative is not a sufficient condition for this property, in general. Then various versions of Newton's method for solving generalized equations are considered including inexact and semismooth methods, for which superlinear convergence is shown under strong metric subregularity. As applications to optimization, a characterization of the strong metric subregularity of the KKT mapping is obtained, as well as a radius theorem for the optimality mapping of a nonlinear programming problem. Finally, an error estimate is derived for a discrete approximation in optimal control under strong metric subregularity of the mapping involved in the Pontryagin principle.     

Graph classes and the complexity of the graph orientation minimizing the maximum weighted outdegree

Given an undirected graph with edge weights, we are asked to find an orientation, that is, an assignment of a direction to each edge, so as to minimize the weighted maximum outdegree in the resulted directed graph. The problem is called MMO, and is a restricted variant of the well-known minimum makespan problem. As in previous studies, it is shown that MMO is in P for trees, weak NP-hard for planar bipartite graphs, and strong NP-hard for general graphs. There are still gaps between those graph classes. The objective of this paper is to show tighter thresholds of complexity: We show that MMO is (i) in P for cactus graphs, (ii) weakly NP-hard for outerplanar graphs, and also (iii) strongly NP-hard for graphs which are both planar and bipartite. This implies the NP-hardness for P₄-bipartite, diamond-free or house-free graphs, each of which is a superclass of cactus. We also show (iv) the NP-hardness for series-parallel graphs and multi-outerplanar graphs, and (v) present a pseudo-polynomial time algorithm for graphs with bounded treewidth.     

Dispersive blow-up for nonlinear Schrödinger equations revisited

The possibility of finite-time, dispersive blow-up for nonlinear equations of Schrödinger type is revisited. This mathematical phenomena is one of the conceivable explanations for oceanic and optical rogue waves. In dimension one, the fact that dispersive blow up does occur for nonlinear Schrödinger equations already appears in [9]. In the present work, the existing results are extended in several ways. In one direction, the theory is broadened to include the Davey–Stewartson and Gross–Pitaevskii equations. In another, dispersive blow up is shown to obtain for nonlinear Schrödinger equations in spatial dimensions larger than one and for more general power-law nonlinearities. As a by-product of our analysis, a sharp global smoothing estimate for the integral term appearing in Duhamel's formula is obtained.     

Fast enclosure for all eigenvalues in generalized eigenvalue problems

A fast method for enclosing all eigenvalues in generalized eigenvalue problems Ax=λBx is proposed. Firstly a theorem for enclosing all eigenvalues, which is applicable even if A is not Hermitian and/or B is not Hermitian positive definite, is presented. Next a theorem for accelerating the enclosure is presented. The proposed method is established based on these theorems. Numerical examples show the performance and property of the proposed method. As an application of the proposed method, an efficient method for enclosing all eigenvalues in polynomial eigenvalue problems is also sketched.     

Dual simplex method for GUB problems

The dual simplex method for generalized upper bound (GUB) problems is presented. One of the major operations in the dual simplex method is to update the elements of therth row, wherer is the index for the leaving basic variable. Those updated elements are used for the ratio test to determine the entering basic variabble. A very simple formula for therth row update for the dual simplex method for a GUB problem is derived, which is similar to the formula for the standard linear program. This derivation is based on the change key operation, which is to exchange the key column and its counterpart in the nonkey section. The change key operation is possible because of a theorem that guarantees the existence of such a counterpart.     

The Logical vs. the Ontological Understanding of Conditions

According to the truth-functional analysis of conditions, to be ‘necessary for’ and ‘sufficient for’ are converse relations. From this, it follows that to be ‘necessary and sufficient for’ is a symmetric relation, that is, that if P is a necessary and sufficient condition for Q, then Q is a necessary and sufficient condition for P. This view is contrary to common sense. In this paper, I point out that it is also contrary to a widely accepted ontological view of conditions, according to which if P is a necessary and sufficient condition for Q, then Q is in no sense a condition for P; it is a mere consequence of P.     

On weakly nonlinear evolution of convective flow in a passive mushy layer

The problem of weakly nonlinear convective flow in a mushy layer, with a permeable mush–liquid interface and constant permeability, is studied under operating conditions for an experiment. A Landau type nonlinear evolution equation for the amplitude of the secondary solutions, which is based on the Landau theory and formulation for the Rayleigh, $R$, number close to its critical value, $R_c$, is developed. Using numerical and analytical methods, the solutions to the evolution equation are calculated for both supercritical and subcritical conditions. We found, in particular, that for $R<R_c$, the amplitude of the secondary solutions decays with time. For $R>R_c$, the tendency for chimney formation in the mushy layer increases with time. In addition, in such a supercritical regime, the basic flow is linearly unstable and we see the presence of steady flow for large values of time. These results suggest a possible slow transition to turbulence in such a flow system.     

A new frequency‐uniform coercive boundary integral equation for acoustic scattering

A new boundary integral operator is introduced for the solution of the soundsoft acoustic scattering problem, i.e., for the exterior problem for the Helmholtz equation with Dirichlet boundary conditions. We prove that this integral operator is coercive in L²(Γ) (where Γ is the surface of the scatterer) for all Lipschitz star‐shaped domains. Moreover, the coercivity is uniform in the wavenumber k = ω/c, where ω is the frequency and c is the speed of sound. The new boundary integral operator, which we call the “star‐combined” potential operator, is a slight modification of the standard combined potential operator, and is shown to be as easy to implement as the standard one. Additionally, to the authors' knowledge, it is the only second‐kind integral operator for which convergence of the Galerkin method in L²(Γ) is proved without smoothness assumptions on Γ except that it is Lipschitz. The coercivity of the star‐combined operator implies frequency‐explicit error bounds for the Galerkin method for any approximation space. In particular, these error estimates apply to several hybrid asymptoticnumerical methods developed recently that provide robust approximations in the high‐frequency case. The proof of coercivity of the star‐combined operator critically relies on an identity first introduced by Morawetz and Ludwig in 1968, supplemented further by more recent harmonic analysis techniques for Lipschitz domains. © 2011 Wiley Periodicals, Inc.     

The analytic continuation of solutions to elliptic boundary value problems in two independent variables

An explicit representation is derived for the continuation across an analytic boundary of the solution to a boundary value problem for an analytic elliptic equation of second order in two independent variables. The representation is in terms of Cauchy data on the boundary and the complex Riemann function. This is equivalent to a representation for the solution to Cauchy's problem given by Henrici in 1957. It is confirmed that the method of complex characteristics is satisfactory for locating real singularities in the solution provided that the Riemann function is entire in its four arguments. Applications to Laplace's and Helmholtz's equations are discussed. By inserting known, simple solutions to the latter equation into the representation formula, several nontrivial integral relations involving the Bessel function J₀, and a possibly new series expansion for J_μ(x), are found.     

Infinite Divisibility of Random Objects in Locally Compact Positive Convex Cones

Random objects taking on values in a locally compact second countable convex cone are studied. The convex cone is assumed to have the property that the class of continuous additive positively homogeneous functionals is separating, an assumption which turns out to imply that the cone is positive. Infinite divisibility is characterized in terms of an analog to the Lévy–Khinchin representation for a generalized Laplace transform. The result generalizes the classical Lévy–Khinchin representation for non-negative random variables and the corresponding result for random compact convex sets inRⁿ. It also gives a characterization of infinite divisibility for random upper semicontinuous functions, in particular for random distribution functions with compact support and, finally, a similar characterization for random processes on a compact Polish space.     

On energy estimates for second order hyperbolic equations with Levi conditions for higher order regularity

We consider energy estimates for second order homogeneous hyperbolic equations with time dependent coefficients. The property of energy conservation, which holds in the case of constant coefficients, does not hold in general for variable coefficients; in fact, the energy can be unbounded as t → ∞ in this case. The conditions to the coefficients for the generalized energy conservation (GEC), which is an equivalence of the energy uniformly with respect to time, has been studied precisely for wave type equations, that is, only the propagation speed is variable. However, it is not true that the same conditions to the coefficients conclude (GEC) for general homogeneous hyperbolic equations. The main purpose of this paper is to give additional conditions to the coefficients which provide (GEC); they will be called as C ^k -type Levi conditions due to the essentially same meaning of usual Levi condition for the well-posedness of weakly hyperbolic equations.     

Strict Efficiency in Vector Optimization

The notion of strict minimum of order m for real optimization problems is extended to vector optimization. Its properties and characterization are studied in the case of finite-dimensional spaces (multiobjective problems). Also the notion of super-strict efficiency is introduced for multiobjective problems, and it is proved that, in the scalar case, all of them coincide. Necessary conditions for strict minimality and for super-strict minimality of order m are provided for multiobjective problems with an arbitrary feasible set. When the objective function is Fréchet differentiable, necessary and sufficient conditions are established for the case m = 1, resulting in the situation that the strict efficiency and super-strict efficiency notions coincide.     

Distribution of Wilks' likelihood-ratio criterion in the complex case

Summary The null distribution of Wilks' likelihood ratio criterian, Λ, in the complex case, is obtained, and explicit expressions for the same are given forp=2 and 3, wherep is the number of variables. It is shown that unlike the real case the distributions derived have closed form representation for allp and for allf ₂, the hypothesis degree of freedom. Tables of correction factors for converting chi-square percentiles to exact percentiles of a logarithmic function of Λ are provided for fourteen (p, f ₂) pairs. Tables for an additional thirteen pairs can be obtained from those tabulated by interchangingp andf ₂. This research was supported (in part) by the National Science Foundation under Grant Number GU-15-34. Reproduction in whole or in part is permitted for any purpose of the United States Government.     

cut* 空间的拓扑性质

该文引入了 cut^*空间的概念,所谓的 cut^*空间是指去掉任意一点连通,去掉任意两点不连通的连通空间.通过对其性质的讨论,得到如下主要结论: 首先得到cut^*空间中每个点非开即闭,并且cut^*空间中有无限多个闭点;其次讨论了一类特殊的 cut^*空间,即去掉一点是COTS的 cut^* 空间.指出``$X$是 cut^*空间,任意 $x\inX,X\setminus\{x\}$是不可约cut空间'这样的空间类是不存在的.在文章的最后,讨论了去掉一点是LOTS的 cut^*空间的覆盖性质,得到这样的空间是紧空间或Lindel\"of空间的结论.     

Diophantine equations and the generalized Riemann hypothesis

We show that, for a listable set P of polynomials with integer coefficients, the statement “for all roots θ of all polynomials in P, the generalized Riemann hypothesis for Q(θ) holds” is Diophantine. That is, the statement is equivalent to the unsolvability of a particular Diophantine equation. This is achieved by finding a decidable property P such that the aforementioned statement may be written in the form “P holds for all natural numbers”.     

The probability of triviality

Given a variety of algebras, what is the probability that for an arbitrary identity p q the only algebra in that satisfies p q is the trivial algebra? More generally, if is a subvariety of what is the probability that p q together with the identities of forms an equational basis for ? We consider these questions for various and and we provide criteria that allow for explicit determination of these probabilities. Received April 14, 1997; accepted in final form January 19, 1998.     

Nonconforming mixed finite element approximation to the stationary Navier-Stokes equations on anisotropic meshes

The main aim of this paper is to study the error estimates of a rectangular nonconforming finite element for the stationary Navier-Stokes equations under anisotropic meshes. That is, the nonconforming rectangular element is taken as approximation space for the velocity and the piecewise constant element for the pressure. The convergence analysis is presented and the optimal error estimates both in a broken H¹-norm for the velocity and in an L²-norm for the pressure are derived on anisotropic meshes.