Counterexamples in measuring the distance between binary trees

Examples are given to show that the closest partition distance measure need not agree with the nearest neighbor interchange distance for unordered labeled binary trees. Proposed algorithms for computing the closest partition distance are shown to be of exponential complexity and hence may not be useful in approximating the nearest neighbor interchange distance.     

Computational experience with the Chow—Yorke algorithm

The Chow—Yorke algorithm is a nonsimplicial homotopy type method for computing Brouwer fixed points that is globally convergent. It is efficient and accurate for fixed point problems. L.T. Watson, T.Y. Li, and C.Y. Wang have adapted the method for zero finding problems, the nonlinear complementarity problem, and nonlinear two-point boundary value problems. Here theoretical justification is given for applying the method to some mathematical programming problems, and computational results are presented.This work was partially supported by NSF Grant MCS 7821337.     

A numerical technique for three-dimensional compressible boundary layers

The non-linear two-point boundary value problem for three-dimensional compressible boundary layers is solved through the application of a boundary value technique for a range of parameters characterizing the nature of stagnation point flows. The analytical boundary conditions, at infinity, are applied at the edge of the computational mesh with iterations on the size of the domain. The solutions obtained show excellent agreement with the established similarity solutions for three-dimensional flows. The present method has the potential advantage of yielding the wall values of f″_w, g″_w and θ′_w as a part of the solution, contrary to the previously used ‘shooting’ methods. The algorithm is computationally simple and numerically stable and extremely suitable for engineering design applications.     

Development and optimisation of a novel genetic algorithm for studying model protein folding

Determination of the native state of a protein from its amino acid sequence is the goal of protein folding simulations, with potential applications in gene therapy and drug design. Location of the global minimum structure for a given sequence, however, is a difficult optimisation problem. In this paper, we describe the development and application of a genetic algorithm (GA) to find the lowest-energy conformations for the 2D HP lattice bead protein model. Optimisation of the parameters of our standard GA program reveals that the GA is most successful (at finding the lowest-energy conformations) for high rates of mating and mutation and relatively high elitism. We have also introduced a number of new genetic operators: a duplicate predator—which maintains population diversity by eliminating duplicate structures; brood selection—where two parent structures undergo crossover and give rise to a brood of (not just two) offspring; and a Monte Carlo based local search algorithm—to explore the neighbourhood of all members of the population. It is shown that these operators lead to significant improvements in the success and efficiency of the GA, both compared with our standard GA and with previously published GA studies for benchmark HP sequences with up to 50 beads.     

Randomized on-line scheduling on three processors

We consider a randomized on-line scheduling problem where each job has to be scheduled on any of m identical processors. The objective is to minimize the expected makespan. We show that the competitive ratio of any randomized algorithm for m=3 processors must be strictly greater than .     

Genetic differentiation and subspecies development of the giant panda as revealed by DNA fingerprinting

Over the last 100 years giant pandas (Ailuropoda melanoleuca) have been separated into six completely isolated mountain ranges. DNA fingerprinting revealed different differentiation patterns in giant pandas, including early-stage, late-stage, recent divergence and recent genetic depression. A separation around 10 000 years ago resulted in highly significant differences in DNA fingerprints and morphological characteristics between Qinling and Sichuan populations. Supported by morphological differences, the genetic data were used to classify the Qinling population as a new subspecies, A. m. qinlingensis, while the Sichuan populations were classified into the original subspecies, A. m. melanoleuca. Thus, the Qinling population deserves management as a separate unit. In the Sichuan populations, two management units were defined, including Qionglai-Minshan and Daxiangling-Xiaoxiangling-Liangshan. Our data suggest urgent measures are needed to establish green corridors between subpopulations in each mountain range to increase gene flow and genetic variation to ensure long-term survival.     

Single Machine Scheduling of Unit-time Jobs with Controllable Release Dates

The paper presents a bicriterion approach to solve the single-machine scheduling problem in which the job release dates can be compressed while incurring additional costs. The two criteria are the makespan and the compression cost. For the case of equal job processing times, an O(n⁴) algorithm is developed to construct integer Pareto optimal points. We discuss how the algorithm developed can be modified to construct an -approximation of noninteger Pareto optimal points. The complexity status of the problem with total weighted completion time criterion is also established.     

A free boundary problem for a fluid flow in a heterogeneous porous medium

In this paper we study the problem of seepage of a fluid through a porous medium, assuming the flow governed by a nonlinear Darcy law and nonlinear leaky boundary conditions. We prove the continuity of the free boundary and the existence and uniqueness of minimal and maximal solutions. We also prove the uniqueness of theS ₃-connected solution in various situations.     

Hilbert's Tenth Problem and Mazur's Conjecture for large subrings of

We give the first examples of infinite sets of primes such that Hilbert's Tenth Problem over has a negative answer. In fact, we can take to be a density 1 set of primes. We show also that for some such there is a punctured elliptic curve over such that the topological closure of in has infinitely many connected components.

     

A Point Balance Algorithm for the Spherical Code Problem

The Spherical Code (SC) problem has many important applications in such fields as physics, molecular biology, signal transmission, chemistry, engineering and mathematics. This paper presents a bilevel optimization formulation of the SC problem. Based on this formulation, the concept of balanced spherical code is introduced and a new approach, the Point Balance Algorithm (PBA), is presented to search for a 1-balanced spherical code. Since an optimal solution of the SC problem (an extremal spherical code) must be a 1-balanced spherical code, PBA can be applied easily to search for an extremal spherical code. In addition, given a certain criterion, PBA can generate efficiently an approximate optimal spherical code on a sphere in the n-dimensional space ⁿ. Some implementation issues of PBA are discussed and putative global optimal solutions of the Fekete problem in 3, 4 and 5-dimensional space are also reported. Finally, an open question about the geometry of Fekete points on the unit sphere in the 3-dimensional space is posed.