Configurations in bowtie systems

There are ten configurations of two bowties that can arise in a bowtie system. We determine a basis for configurations of two bowties in both balanced and general bowtie systems. We also determine the avoidance spectrum for the three most compact configurations of two bowties.     

Twofold 2-perfect bowtie systems with an extra property

A bowtie is a closed trail whose graph consists of two 3-cycles with exactly one vertex in common. A 2-fold bowtie system of order n is an edge-disjoint decomposition of 2K _n into bowties. A 2-fold bowtie system is said to be 2-perfect provided that every pair of distinct vertices is joined by two paths of length 2. It is said to be extra provided these two paths always have distinct midpoints. The extra property guarantees that the two paths x, a, y and x, b, y between every pair of vertices form a 4-cycle (x, a, y, b), and that the collection of all such 4-cycles is a four-fold 4-cycle system. We show that the spectrum for extra 2-perfect 2-fold bowtie systems is precisely the set of all n ?? 0 or 1 (mod 3), ${n\,\geqslant\,6}$ . Additionally, with an obvious definition, we show that the spectrum for extra 2-perfect 2-fold maximum packings of 2K _n with bowties is precisely the set of all n ?? 2 (mod 3), ${n\,\geqslant\,8}$ .     

On bowtie rings,universal survival rings and universal lying-over rings

If (R,M) is a quasilocal integral domain of Krull dimension n,?1<n≤∞, and E is the direct sum of denumerably many copies of R/M, then T:=R?E is a reduced n-dimensional universal survival ring which is not a universal lying-over ring. In fact, T is a new kind of such ring, as T is not (isomorphic to) an A+B construction and T is not a ring of continuous real-valued functions. The analysis includes identifying all the prime ideals of T and showing that T is its own total quotient ring and satisfies Property A. The assertion would fail if n=1, as T would be a universal lying-over ring in this case. It is also shown that a (commutative unital) ring A satisfies Property A if and only if each ideal of A that consists only of zero-divisors survives in the complete ring of quotients of A.     

A transportation problem formulation for the MAC Airlift Planning problem

The Military Airlift Command (MAC) is responsible for planning the allocation of airlift resources for the movement of cargo and passengers. A heuristic algorithm, the Airlift Planning Algorithm (APA), has recently been developed under subcontract to the Oak Ridge National Laboratory to assist MAC in scheduling airlift resources. In this paper, we present a transportation problem formulation which can be used as a preprocessor to the APA or as an estimator for the APA. This paper examines the robustness and sensitivity of the transportation problem formulation. In particular, the performance of the APA improves by approximately 10% when the transportation problem is used as a preprocessor for two hypothetical problems and improves by up to 50% for derived airlift constrained problems.     

Estimates for the corona problem

Estimates are given for solutions of the corona problem for H^∞ of the upper half plane or unit disk. Roughly speaking, our results assert that if at every point one corona datum is large, then small corona solutions may be obtained. Our methods use heavily the theory of functions of bounded mean oscillation and in particular, a result of Garnett and Jones.     

Algorithms for the quickest path problem and the reliable quickest path problem

The quickest path problem consists of finding a path in a directed network to transmit a given amount of items from an origin node to a destination node with minimal transmission time, when the transmission time depends on both the traversal times of the arcs, or lead time, and the rates of flow along arcs, or capacity. In telecommunications networks, arcs often also have an associated operational probability of the transmission being fault free. The reliability of a path is defined as the product of the operational probabilities of its arcs. The reliability as well as the transmission time are of interest. In this paper, algorithms are proposed to solve the quickest path problem as well as the problem of identifying the quickest path whose reliability is not lower than a given threshold. The algorithms rely on both the properties of a network which turns the computation of a quickest path into the computation of a shortest path and the fact that the reliability of a path can be evaluated through the reliability of the ordered sequence of its arcs. Other constraints on resources consumed, on the number of arcs of the path, etc. can also be managed with the same algorithms.     

Probabilistic analysis of solving the assignment problem for the traveling salesman problem

This paper deals with probabilistic analysis of optimal solutions of the asymmetric traveling salesman problem. The exact distribution for the number of required next-best solutions of the assignment problem with random data in order to find an optimal tour is given. For every n-city asymmetric problem, there exists an algorithm such that (i) with probability 1 ? s, s?(0,1) the algorithm produces an optimal tour, (ii) it runs in time $\text{O}\text{(}\text{n}{}^4\text{3}\text{)}$, and (iii) it requires less than w((w + n ? 1)$\text{log}\text{(w + n ? 1) + w + 1) +}\text{1}\text{6}\text{w(n}{}^3\text{+ 3n}{}^2\text{+ 2n ? 6)}$ computational steps, where w = log(s)/log(1 ? E_n); E_n ?(0,1) is given by a simple mathematical formula. Additionally, the polynomial of (iii) gives the exact (deterministic) execution time to find w =1 ,2…. next-best solutions of the assignment problem.     

Approximation theorems for the solution of Fourier's problem and Dirichlet's problem

Mathematische Annalen -     

Wavelet solutions for the Dirichlet problem

Summary. A modified classical penalty method for solving a Dirichlet boundary value problem is presented. This new fictitious domain penalty method eliminates the traditional need of generating a complex computation grid in the case of irregular domains. It is based on the fact that one can expand the boundary measure under the chosen basis which leads to a fast, approximate calculation of boundary integral. The compact support and orthonormality of the basis are essential for representing the boundary measure numerically, and therefore for implementing this methodology. Received June 3, 1992 / Revised version received November 8, 1993     

Solving the eigenvalue problem for matrices

One presents some algorithms related among themselves for solving the partial and the complete eigenvalue problem for an arbitrary matrix. Algorithm 1 allows us to construct the invariant subspaces and to obtain with their aid a matrix whose eigenvalues coincide with the eigenvalues of the initial matrix and belong to a given semiplane. Algorithm 2 solves the same problem for a given strip. The algorithms 3 and 4 reduces the complete eigenvalue problem of an arbitrary matrix to some problem for a quasitriangular matrix whose diagonal blocks have eigenvalues with identical real parts. Algorithm 4 finds also the unitary matrix which realizes this transformation. One gives Algol programs which realize the algorithms 1–3 for real matrices and testing examples.     

POPMUSIC for the travelling salesman problem

POPMUSIC— Partial OPtimization Metaheuristic Under Special Intensification Conditions — is a template for tackling large problem instances. This metaheuristic has been shown to be very efficient for various hard combinatorial problems such as p-median, sum of squares clustering, vehicle routing, map labelling and location routing. A key point for treating large Travelling Salesman Problem (TSP) instances is to consider only a subset of edges connecting the cities. The main goal of this article is to present how to build a list of good candidate edges with a complexity lower than quadratic in the context of TSP instances given by a general function. The candidate edges are found with a technique exploiting tour merging and the POPMUSIC metaheuristic. When these candidate edges are provided to a good local search engine, high quality solutions can be found quite efficiently. The method is tested on TSP instances of up to several million cities with different structures (Euclidean uniform, clustered, 2D to 5D, grids, toroidal distances). Numerical results show that solutions of excellent quality can be obtained with an empirical complexity lower than quadratic without exploiting the geometrical properties of the instances.     

Gauss-Newton methods for the complementarity problem

Mangasarian has shown that the solution of the complementarity problem is equivalent to the solution of a system of nonlinear equations. In this paper, we propose a damped Gauss-Newton algorithm to solve this system, prove that under appropriate hypotheses one gets rapid local convergence, and present computational experience.The author would like to thank Professor Michael Ferris for pointing out a flaw in one of the proofs in an earlier preprint of this paper (Ref. 1). He is grateful to Professor Olvi Mangasarian for bringing to his attention additional references relevant to the material in this paper, and for his suggestions which resulted in a greatly improved presentation.     

Half-inverse problem for the Dirac operator

Given the spectrum of the Dirac operator, together with the potential on the half-interval and one boundary condition, this paper provides reconstruction of the potential on the whole interval, and proves the existence conditions of the solution.     

Algorithms for the vector maximization problem

We consider a convex setB inR ⁿ described as the intersection of halfspacesa _i ^T x ≦b _i (i ∈ I) and a set of linear objective functionsf _j =c _j ^T x (j ∈ J). The index setsI andJ are allowed to be infinite in one of the algorithms. We give the definition of theefficient points ofB (also called functionally efficient or Pareto optimal points) and present the mathematical theory which is needed in the algorithms. In the last section of the paper, we present algorithms that solve the following problems:

1. To decide if a given point inB is efficient.
2. To find an efficient point inB.
3. To decide if a given efficient point is the only one that exists, and if not, find other ones.
4. The solutions of the above problems do not depend on the absolute magnitudes of thec _j. They only describe the relative importance of the different activitiesx _i. Therefore we also consider $$\begin{gathered} \max G^T x \hfill \\ x efficient \hfill \\ \end{gathered} $$ for some vectorG.

     

Heuristics for the container loading problem

The knapsack container loading problem is the problem of loading a subset of rectangular boxes into a rectangular container of fixed dimensions such that the volume of the packed boxes is maximized. A new heuristic based on the wall-building approach is proposed, which decomposes the problem into a number of layers which again are split into a number of strips. The packing of a strip may be formulated and solved optimally as a Knapsack Problem with capacity equal to the width or height of the container. The depth of a layer as well as the thickness of each strip is decided through a branch-and-bound approach where at each node only a subset of branches is explored.Several ranking rules for the selection of the most promising layer depths and strip widths are presented and the performance of the corresponding algorithms is experimentally compared for homogeneous and heterogeneous instances. The best ranking rule is then used in a comprehensive computational study involving large-sized instances. These computational results show that instances with a total box volume up to 90% easily may be solved to optimality, and that average fillings of the container volume exceeding 95% may be obtained for large-sized instances.