On the complexity of branch‐and‐bound search for random trees

Let T_n be a b‐ary tree of height n, which has independent, non‐negative, identically distributed random variables associated with each of its edges, a model previously considered by Karp, Pearl, McDiarmid, and Provan. The value of a node is the sum of all the edge values on its path to the root. Consider the problem of finding the minimum leaf value of T_n. Assume that the edge random variable X is nondegenerate, has E {X^θ}<∞ for some θ>2, and satisfies bP{X=c}<1 where c is the leftmost point of the support of X. We analyze the performance of the standard branch‐and‐bound algorithm for this problem and prove that the number of nodes visited is in probability (β+o(1))ⁿ, where β∈(1, b) is a constant depending only on the distribution of the edge random variables. Explicit expressions for β are derived. We also show that any search algorithm must visit (β+o(1))ⁿ nodes with probability tending to 1, so branch‐and‐bound is asymptotically optimal where first‐order asymptotics are concerned. ©1999 John Wiley & Sons, Inc. Random Struct. Alg., 14: 309–327, 1999     

Self‐dual and self‐petrie‐dual regular maps

Regular maps are cellular decompositions of surfaces with the “highest level of symmetry”, not necessarily orientation‐preserving. Such maps can be identified with three‐generator presentations of groups G of the form G = 〈a, b, c|a² = b² = c² = (ab)^k = (bc)^m = (ca)² = … = 1〉; the positive integers k and m are the face length and the vertex degree of the map. A regular map (G;a, b, c) is self‐dual if the assignment b?b, c?a and a?c extends to an automorphism of G, and self‐Petrie‐dual if G admits an automorphism fixing b and c and interchanging a with ca. In this note we show that for infinitely many numbers k there exist finite, self‐dual and self‐Petrie‐dual regular maps of vertex degree and face length equal to k. We also prove that no such map with odd vertex degree is a normal Cayley map. Copyright © 2011 Wiley Periodicals, Inc. J Graph Theory 69:152‐159, 2012     

New fast divide‐and‐conquer algorithms for the symmetric tridiagonal eigenvalue problem

In this paper, two accelerated divide‐and‐conquer (ADC) algorithms are proposed for the symmetric tridiagonal eigenvalue problem, which cost O(N²r) flops in the worst case, where N is the dimension of the matrix and r is a modest number depending on the distribution of eigenvalues. Both of these algorithms use hierarchically semiseparable (HSS) matrices to approximate some intermediate eigenvector matrices, which are Cauchy‐like matrices and are off‐diagonally low‐rank. The difference of these two versions lies in using different HSS construction algorithms, one (denoted by ADC1) uses a structured low‐rank approximation method and the other (ADC2) uses a randomized HSS construction algorithm. For the ADC2 algorithm, a method is proposed to estimate the off‐diagonal rank. Numerous experiments have been carried out to show their stability and efficiency. These algorithms are implemented in parallel in a shared memory environment, and some parallel implementation details are included. Comparing the ADCs with highly optimized multithreaded libraries such as Intel MKL, we find that ADCs could be more than six times faster for some large matrices with few deflations. Copyright © 2016 John Wiley & Sons, Ltd.     

PDα‐type distributed learning control for nonlinear fractional‐order multiagent systems

This paper considers the consensus tacking problem for nonlinear fractional‐order multiagent systems by presenting a PD^α‐type iterative learning control update law with initial learning mechanisms. The asymptotical convergence of the proposed distributed learning algorithm is strictly proved by using the properties of fractional calculus. A sufficient condition is derived to guarantee the whole multiagent system achieving an asymptotic output consensus. An illustrative example is given to verify the theoretical results.     

Time‐weighted blow‐up rates and pointwise profile for single‐point blow‐up solutions in reaction–diffusion equations

This paper deals with asymptotic behavior for blow‐up solutions to time‐weighted reaction–diffusion equations u_t=Δu+e^αtv^p and v_t=Δv+e^βtu^q, subject to homogeneous Dirichlet boundary. The time‐weighted blow‐up rates are defined and obtained by ways of the scaling or auxiliary‐function methods for all α, . Aiding by key inequalities between components of solutions, we give lower pointwise blow‐up profiles for single‐point blow‐up solutions. We also study the solutions of the system with variable exponents instead of constant ones, where blow‐up rates and new blow‐up versus global existence criteria are obtained. Time‐weighted functions influence critical Fujita exponent, critical Fujita coefficient and formulae of blow‐up rates, but they do not limit the order of time‐weighted blow‐up rates and pointwise profile near blow‐up time. Copyright © 2017 John Wiley & Sons, Ltd.     

On cubic non‐Cayley vertex‐transitive graphs

In 1983, the second author [D. Maru?i?, Ars Combinatoria 16B (1983), 297–302] asked for which positive integers n there exists a non‐Cayley vertex‐transitive graph on n vertices. (The term non‐Cayley numbers has later been given to such integers.) Motivated by this problem, Feng [Discrete Math 248 (2002), 265–269] asked to determine the smallest valency ?(n) among valencies of non‐Cayley vertex‐transitive graphs of order n. As cycles are clearly Cayley graphs, ?(n)?3 for any non‐Cayley number n. In this paper a goal is set to determine those non‐Cayley numbers n for which ?(n) = 3, and among the latter to determine those for which the generalized Petersen graphs are the only non‐Cayley vertex‐transitive graphs of order n. It is known that for a prime p every vertex‐transitive graph of order p, p² or p³ is a Cayley graph, and that, with the exception of the Coxeter graph, every cubic non‐Cayley vertex‐transitive graph of order 2p, 4p or 2p² is a generalized Petersen graph. In this paper the next natural step is taken by proving that every cubic non‐Cayley vertex‐transitive graph of order 4p², p>7 a prime, is a generalized Petersen graph. In addition, cubic non‐Cayley vertex‐transitive graphs of order 2p^k, where p>7 is a prime and k?p, are characterized. © 2011 Wiley Periodicals, Inc. J Graph Theory 69: 77–95, 2012     

Hyper‐Archimedean BL‐algebras are MV‐algebras

Generalizations of Boolean elements of a BL‐algebra L are studied. By utilizing the MV‐center MV(L) of L, it is reproved that an element x ∈ L is Boolean iff x ∨ x * = 1 . L is called semi‐Boolean if for all x ∈ L, x * is Boolean. An MV‐algebra L is semi‐Boolean iff L is a Boolean algebra. A BL‐algebra L is semi‐Boolean iff L is an SBL‐algebra. A BL‐algebra L is called hyper‐Archimedean if for all x ∈ L, xⁿ is Boolean for some finite n ≥ 1. It is proved that hyper‐Archimedean BL‐algebras are MV‐algebras. The study has application in mathematical fuzzy logics whose Lindenbaum algebras are MV‐algebras or BL‐algebras. (© 2007 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Two‐level discretization of the Navier‐Stokes equations with r‐Laplacian subgridscale viscosity

The r‐Laplacian has played an important role in the development of computationally efficient models for applications, such as numerical simulation of turbulent flows. In this article, we examine two‐level finite element approximation schemes applied to the Navier‐Stokes equations with r‐Laplacian subgridscale viscosity, where r is the order of the power‐law artificial viscosity term. In the two‐level algorithm, the solution to the fully nonlinear coarse mesh problem is utilized in a single‐step linear fine mesh problem. When modeling parameters are chosen appropriately, the error in the two‐level algorithm is comparable to the error in solving the fully nonlinear problem on the fine mesh. We provide rigorous numerical analysis of the two‐level approximation scheme and derive scalings which vary based on the coefficient r, coarse mesh size H, fine mesh size h, and filter radius δ. We also investigate the two‐level algorithm in several computational settings, including the 3D numerical simulation of flow past a backward‐facing step at Reynolds number Re = 5100. In all numerical tests, the two‐level algorithm was proven to achieve the same order of accuracy as the standard one‐level algorithm, at a fraction of the computational cost. © 2011 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq, 2011     

A Crank‐Nicolson Petrov‐Galerkin method with quadrature for semi‐linear parabolic problems

We propose and analyze an application of a fully discrete C² spline quadrature Petrov‐Galerkin method for spatial discretization of semi‐linear parabolic initial‐boundary value problems on rectangular domains. We prove second order in time and optimal order H¹ norm convergence in space for the extrapolated Crank‐Nicolson quadrature Petrov‐Galerkin scheme. We demonstrate numerically both L² and H¹ norm optimal order convergence of the scheme even if the nonlinear source term is not smooth. © 2005 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq, 2005.     

Learning finite binary sequences from half‐space data

The problem of inferring a finite binary sequence w *∈{−1, 1}ⁿ is considered. It is supposed that at epochs t=1, 2,…, the learner is provided with random half‐space data in the form of finite binary sequences u ^(t)∈{−1, 1}ⁿ which have positive inner‐product with w *. The goal of the learner is to determine the underlying sequence w * in an efficient, on‐line fashion from the data { u ^(t), t≥1}. In this context, it is shown that the randomized, on‐line directed drift algorithm produces a sequence of hypotheses {w^(t)∈{−1, 1}ⁿ, t≥1} which converges to w * in finite time with probability 1. It is shown that while the algorithm has a minimal space complexity of 2n bits of scratch memory, it has exponential time complexity with an expected mistake bound of order Ω(e^0.139n). Batch incarnations of the algorithm are introduced which allow for massive improvements in running time with a relatively small cost in space (batch size). In particular, using a batch of 𝒪(n log n) examples at each update epoch reduces the expected mistake bound of the (batch) algorithm to 𝒪(n) (in an asynchronous bit update mode) and 𝒪(1) (in a synchronous bit update mode). The problem considered here is related to binary integer programming and to learning in a mathematical model of a neuron. ©1999 John Wiley & Sons, Inc. Random Struct. Alg., 14, 345–381 (1999)     

Efficient algorithms for three‐dimensional axial and planar random assignment problems

Beautiful formulas are known for the expected cost of random two‐dimensional assignment problems, but in higher dimensions even the scaling is not known. In three dimensions and above, the problem has natural “Axial” and “Planar” versions, both of which are NP‐hard. For 3‐dimensional Axial random assignment instances of size n, the cost scales as Ω(1/ n), and a main result of the present paper is a linear‐time algorithm that, with high probability, finds a solution of cost O(n^–1+o(1)). For 3‐dimensional Planar assignment, the lower bound is Ω(n), and we give a new efficient matching‐based algorithm that with high probability returns a solution with cost O(n log n). © 2013 Wiley Periodicals, Inc. Random Struct. Alg., 46, 160–196, 2015     

The Crank‐Nicolson/Adams‐Bashforth scheme for the time‐dependent Navier‐Stokes equations with nonsmooth initial data

In this article, we study the stability and convergence of the Crank‐Nicolson/Adams‐Bashforth scheme for the two‐dimensional nonstationary Navier‐Stokes equations with a nonsmooth initial data. A finite element method is applied for the spatial approximation of the velocity and pressure. The time discretization is based on the implicit Crank‐Nicolson scheme for the linear terms and the explicit Adams‐Bashforth scheme for the nonlinear term. Moreover, we prove that the scheme is almost unconditionally stable for a nonsmooth initial data u₀ with div u₀ = 0, i.e., the time step τ satisfies: τ ≤ C₀ if u₀ ∈ H¹ ∩ L^∞; τ |log h| ≤ C₀ if u₀ ∈ H¹ for the mesh size h and some positive constant C₀. Finally, we obtain some error estimates for the discrete velocity and pressure under the above stability condition. © 2010 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq, 28: 155‐187, 2012     

Infinite families of non‐embeddable quasi‐residual Menon designs

A Menon design of order h² is a symmetric (4h²,2h²‐h,h²‐h)‐design. Quasi‐residual and quasi‐derived designs of a Menon design have parameters 2‐(2h² + h,h²,h²‐h) and 2‐(2h²‐h,h²‐h,h²‐h‐1), respectively. In this article, regular Hadamard matrices are used to construct non‐embeddable quasi‐residual and quasi‐derived Menon designs. As applications, we construct the first two new infinite families of non‐embeddable quasi‐residual and quasi‐derived Menon designs. © 2008 Wiley Periodicals, Inc. J Combin Designs 17: 53–62, 2009     

2‐connected 7‐coverings of 3‐connected graphs on surfaces

An m‐covering of a graph G is a spanning subgraph of G with maximum degree at most m. In this paper, we shall show that every 3‐connected graph on a surface with Euler genus k ≥ 2 with sufficiently large representativity has a 2‐connected 7‐covering with at most 6k ? 12 vertices of degree 7. We also construct, for every surface F² with Euler genus k ≥ 2, a 3‐connected graph G on F² with arbitrarily large representativity each of whose 2‐connected 7‐coverings contains at least 6k ? 12 vertices of degree 7. © 2003 Wiley Periodicals, Inc. J Graph Theory 43: 26–36, 2003     

Besov‐Morrey spaces and Triebel‐Lizorkin‐Morrey spaces on domains

The purpose of this paper is to develop a theory of the Besov‐Morrey spaces and the Triebel‐Lizorkin‐Morrey spaces on domains in R ⁿ. We consider the pointwise multiplier operator, the trace operator, the extension operator and the diffeomorphism operator. Not only to domains in R ⁿ we extend our definition of function spaces to compact oriented Riemannian manifolds. Among the properties above, the result for the trace operator is in particular interesting, which reflects the property of the parameters p, q in the Morrey space ??^p_q (© 2010 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Limit theory for the random on‐line nearest‐neighbor graph

In the on‐line nearest‐neighbor graph (ONG), each point after the first in a sequence of points in ?^d is joined by an edge to its nearest neighbor amongst those points that precede it in the sequence. We study the large‐sample asymptotic behavior of the total power‐weighted length of the ONG on uniform random points in (0,1)^d. In particular, for d = 1 and weight exponent α > 1/2, the limiting distribution of the centered total weight is characterized by a distributional fixed‐point equation. As an ancillary result, we give exact expressions for the expectation and variance of the standard nearest‐neighbor (directed) graph on uniform random points in the unit interval. © 2007 Wiley Periodicals, Inc. Random Struct. Alg., 2008     

Stability of nonconstant steady‐state solutions for 2‐fluid nonisentropic Euler‐Poisson equations in semiconductor

We consider the periodic problem for 2‐fluid nonisentropic Euler‐Poisson equations in semiconductor. By choosing a suitable symmetrizers and using an induction argument on the order of the time‐space derivatives of solutions in energy estimates, we obtain the global stability of solutions with exponential decay in time near the nonconstant steady‐states for 2‐fluid nonisentropic Euler‐Poisson equations. This improves the results obtained for models with temperature diffusion terms by using the pressure functions p^ν in place of the unknown variables densities n^ν.     

Nonoverlapping domain decomposition characteristic finite differences for three‐dimensional convection‐diffusion equations

One domain decomposition method modified with characteristic differences is presented for non‐periodic three‐dimensional equations by multiply‐type quadratic interpolation and variant time‐step technique. This method consists of reduced‐scale, two‐dimensional computation on subdomain interface boundaries and fully implicit subdomain computation in parallel. A computational algorithm is outlined and an error estimate in discrete l²‐ norm is established by introducing new inner products and norms. Finally, numerical examples are given to illustrate the theoretical results, efficiency and parallelism of this method. © 2010 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq 28: 17‐37, 2012     

Claw‐free circular‐perfect graphs

The circular chromatic number of a graph is a well‐studied refinement of the chromatic number. Circular‐perfect graphs form a superclass of perfect graphs defined by means of this more general coloring concept. This article studies claw‐free circular‐perfect graphs. First, we prove that if G is a connected claw‐free circular‐perfect graph with χ(G)>ω(G), then min{α(G), ω(G)}=2. We use this result to design a polynomial time algorithm that computes the circular chromatic number of claw‐free circular‐perfect graphs. A consequence of the strong perfect graph theorem is that minimal imperfect graphs G have min{α(G), ω(G)}=2. In contrast to this result, it is shown in Z. Pan and X. Zhu [European J Combin 29(4) (2008), 1055–1063] that minimal circular‐imperfect graphs G can have arbitrarily large independence number and arbitrarily large clique number. In this article, we prove that claw‐free minimal circular‐imperfect graphs G have min{α(G), ω(G)}≤3. © 2010 Wiley Periodicals, Inc. J Graph Theory 65: 163–172, 2010     

Spaces of Bessel‐potential type and embeddings: the super‐limiting case

We consider Bessel‐potential spaces modelled upon Lorentz‐Karamata spaces and establish embedding theorems in the super‐limiting case. In addition, we refine a result due to Triebel, in the context of Bessel‐potential spaces, itself an improvement of the Brézis‐Wainger result (super‐limiting case) about the “almost Lipschitz continuity” of elements of H^1+n/p_p (?ⁿ). These results improve and extend results due to Edmunds, Gurka and Opic in the context of logarithmic Bessel potential spaces. We also give examples of embeddings of Besselpotential type spaces which are not of logarithmic type. (© 2004 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)