Lemniscates and inequalities for the logarithmic capacities of continua

It is shown that if P(z) = z ⁿ + ? is a polynomial with connected lemniscate E(P) = {z: ¦P(z)¦ ≤ 1} and m critical points, then, for any n? m+1 points on the lemniscate E(P), there exists a continuum γ ? E(P) of logarithmic capacity cap γ ≤ 2^?1/n which contains these points and all zeros and critical points of the polynomial. As corollaries, estimates for continua of minimum capacity containing given points are obtained.     

Efficient algorithms for computing the maximum distance between two finite planar sets

An 0(n log n) algorithm is presented for computing the maximum euclidean distance between two finite planar sets of n points. When the n points form the vertices of simple polygons this complexity can be reduced to 0(n). The algorithm is empirically compared to the brute-force method as well as an alternate 0(n²) algorithm. Both the 0(n log n) and 0(n²) algorithms run in 0(n) expected time for many underlying distributions of the points. An ?-approximate algorithm can be obtained that runs in $\text{0(n +}\text{1}\text{?}\text{)}$ worst-case time.     

Efficient algorithms for checking the equivalence of programs in interrupt handling models

The problem of equivalence of interrupt handling programs in two algebraic models is studied. Program operators are divided into two classes, namely, the classes of basic operators and interrupt handling operators. The first model obeys the absorption law, i.e., each basic operator suppresses the result of application of any interrupt handling operator. This means that, if the interrupt handling is successfully finished and the control is passed to basic operators, then the result of interrupt handling has no influence on the program output. An algorithm that solves the problem of equivalence in the above model in O(n ²log n) operations is suggested. The other model obeys the absorption law and satisfies the commutative property for basic operators. For this model, we also propose an algorithm that checks the equivalence of programs in O(n ⁴log n) operations.     

Average complexity of a gift-wrapping algorithm for determining the convex hull of randomly given points

This paper presents an algorithm and its probabilistic analysis for constructing the convex hull ofm given points in ?ⁿ then-dimensional Euclidean space. The algorithm under consideration combines the Gift-Wrapping concept with the so-called Throw-Away Principle (introduced by Akl and Toussaint [1] and later by Devroye [10]) for nonextremal points. The latter principle had been used for a convex-hull-construction algorithm in R² and for its probabilistic analysis in a recent paper by Borgwardtet al. [5]. There, the considerations remained much simpler, because in ?² the construction of the convex hull essentially requires recognition of the extremal points and of their order only. In this paper the Simplex method is used to organize a walk over the surface of the convex hull. During this walk all facets are discovered. Under the condition of general position this information is sufficient, because the whole face lattice can simply be deduced when the set of facets is available. Exploiting the advantages of the revised Simplex method reduces the update effort to ann ×n matrix and the number of calculated quotients for the pivot search to the points which are not thrown away. For this algorithm a probabilistic analysis can be carried out. We assume that ourm random points are distributed identically, independently, and symmetrically under rotations in Rⁿ. Then the calculation of the expected effort becomes possible for a whole parametrical class of distributions over the unit ball. The results mean a progress in three directions:

a parametrization of the expected effort can be given;

the dependency onn— the dimension of the space—can be evaluated;

the additional work of preprocessing for detecting the vertices can be avoided without losing its advantages.

     

On a cardinal group invariant related to decompositions of Abelian groups

For each Abelian groupG, a cardinal invariant χ(G) is introduced and its properties are studied. In the special caseG = ? ⁿ , the cardinalχ(? ⁿ ) is equal to the minimal cardinality of an essential subset of ? ⁿ , i.e., a of a subsetA ? ? ⁿ such that, for any coloring of the group ? ⁿ inn colors, there exists an infinite one-color subset that is symmetric with respect to some pointα ofA. The estimaten( ^{n +} l)/2 ≤χ(? ⁿ ) < 2n is proved for alln and the relationχ(? ⁿ ) =n(n + 1)/2 forn ≤ 3. The structure of essential subsets of cardinalityχ(? ⁿ ) in ? ⁿ is completely described forn ≤ 3.     

Estimates on conjectures of Minkowski and woods II

Let ? ⁿ be the n-dimensional Euclidean space. Let ∧ be a lattice of determinant 1 such that there is a sphere |X| < Rwhich contains no point of ∧ other than the origin O and has n linearly independent points of ∧ on its boundary. A well known conjecture in the geometry of numbers asserts that any closed sphere in ? ⁿ of radius \(\sqrt n /2\) contains a point of ∧. This is known to be true for n ≤ 8. Recently we gave estimates on a more general conjecture of Woods for n ≥ 9. This lead to an improvement for 9 ≤ n ≤ 22 on estimates of Il’in (1991) to the long standing conjecture of Minkowski on product of n non-homogeneous linear forms. Here we shall refine our method to obtain improved estimates for Woods Conjecture. These give improved estimates of Minkowski’s conjecture for 9 ≤ n ≤ 31.     

Inductive limits of spaces of vector- valued integrable functions

For an order-continuous Banach function space Λ and a separated inductive limit E:= ind_n E _n, we prove that ind_n A {E_n} is a topological subspace of Λ {E}; moreover, both spaces coincide if the inductive limit is hyperstrict. As a consequence, we deduce that if E is an LF-space, then L ^p {E} is barrelled for 1 ≤ p ≤ ∞.     

Probabilistic computation of integer polynomial GCDs

We describe a probabilistic algorithm for the computation of the gcd of two univariate integer polynomials of degrees ≤ n with their l¹-norms being bounded by 2^h and estimate its expected running time by a worst-case bound of O(n(n + h)^{1 + o(1)}) bit operations.     

The just-in-time scheduling problem in a flow-shop scheduling system

We study the problem of maximizing the weighted number of just-in-time (JIT) jobs in a flow-shop scheduling system under four different scenarios. The first scenario is where the flow-shop includes only two machines and all the jobs have the same gain for being completed JIT. For this scenario, we provide an O(n³) time optimization algorithm which is faster than the best known algorithm in the literature. The second scenario is where the job processing times are machine-independent. For this scenario, the scheduling system is commonly referred to as a proportionate flow-shop. We show that in this case, the problem of maximizing the weighted number of JIT jobs is NP-hard in the ordinary sense for any arbitrary number of machines. Moreover, we provide a fully polynomial time approximation scheme (FPTAS) for its solution and a polynomial time algorithm to solve the special case for which all the jobs have the same gain for being completed JIT. The third scenario is where a set of identical jobs is to be produced for different customers. For this scenario, we provide an O(n³) time optimization algorithm which is independent of the number of machines. We also show that the time complexity can be reduced to O(n log n) if all the jobs have the same gain for being completed JIT. In the last scenario, we study the JIT scheduling problem on m machines with a no-wait restriction and provide an O(mn²) time optimization algorithm.     

Adaptive Itô-Taylor algorithm can optimally approximate the Itô integrals of singular functions

We deal with numerical approximation of stochastic Itô integrals of singular functions. We first consider the regular case of integrands belonging to the Hölder class with parameters r and ?. We show that in this case the classical Itô-Taylor algorithm has the optimal error Θ(n^−(r+?)). In the singular case, we consider a class of piecewise regular functions that have continuous derivatives, except for a finite number of unknown singular points. We show that any nonadaptive algorithm cannot efficiently handle such a problem, even in the case of a single singularity. The error of such algorithm is no less than n^{−min{1/2,r+?}}. Therefore, we must turn to adaptive algorithms. We construct the adaptive Itô-Taylor algorithm that, in the case of at most one singularity, has the optimal error O(n^−(r+?)). The best speed of convergence, known for regular functions, is thus preserved. For multiple singularities, we show that any adaptive algorithm has the error Ω(n^{−min{1/2,r+?}}), and this bound is sharp.     

About Widths of Wiener Space in theLq-Norm

We calculate the average Kolmogorov and linearn-widths of the Wiener space in theL_q-norm. For the case 1 ≤q< ∞, then-widthsd_ndecrease asymptotically asn^-1/2.     

The non-existence of certain finite linear spaces

We study the existence of finite linear spaces with v points and n ²+n+2 lines, where n ²+1?v?n ²+n+1. For n?3, there is only one such linear space; it has ten points and fourteen lines.     

Fast computation of eigenvalues of companion,comrade, and related matrices

The class of eigenvalue problems for upper Hessenberg matrices of banded-plus-spike form includes companion and comrade matrices as special cases. For this class of matrices a factored form is developed in which the matrix is represented as a product of essentially 2×2 matrices and a banded upper-triangular matrix. A non-unitary analogue of Francis’s implicitly-shifted QR algorithm that preserves the factored form and consequently computes the eigenvalues in O(n ²) time and O(n) space is developed. Inexpensive a posteriori tests for stability and accuracy are performed as part of the algorithm. The results of numerical experiments are mixed but promising in certain areas. The single-shift version of the code applied to companion matrices is much faster than the nearest competitor.     

An example of non-uniqueness of a simple partial fraction of the best uniform approximation

For arbitrary natural n ≥ 2 we construct an example of a real continuous function, for which there exists more than one simple partial fraction of order ≤ n of the best uniform approximation on a segment of the real axis. We prove that even the Chebyshev alternance consisting of n+1 points does not guarantee the uniqueness of the best approximation fraction. The obtained results are generalizations of known non-uniqueness examples constructed for n = 2, 3 in the case of simple partial fractions of an arbitrary order n.     

Potential theory in the class of m-subharmonic functions

A potential theory for the equation (dd ^c u)m ∧ β ^n?m = fβ ⁿ , 1 ≤ m ≤ n, is developed. The corresponding notions of m-capacity and m-subharmonic functions are introduced, and their properties are studied.     

Minimax linear programming problem

In this paper, we consider the following minimax linear programming problem: min z = max_{1 ≤ j ≤ n}{C_jX_j}, subject to Ax = g, x ≥ 0. It is well known that this problem can be transformed into a linear program by introducing n additional constraints. We note that these additional constraints can be considered implicitly by treating them as parametric upper bounds. Based on this approach we develop two algorithms: a parametric algorithm and a primal—dual algorithm. The parametric algorithm solves a linear programming problem with parametric upper bounds and the primal—dual algorithm solves a sequence of related dual feasible linear programming problems. Computation results are also presented, which indicate that both the algorithms are substantially faster than the simplex algorithm applied to the enlarged linear programming problem.     

Average running time of the fast Fourier transform

We compare several algorithms for computing the discrete Fourier transform of n numbers. The number of “operations” of the original Cooley-Tukey algorithm is approximately 2nA(n), where A(n) is the sum of the prime divisors of n. We show that the average number of operations satisfies $\text{1}\text{x}\text{)∑}{}_{\mathrm{n\le x}}\text{2n A(n) ～ (}\text{π}{}^2\text{9}\text{)(}\text{x}{}^2\text{log}\text{x}\text{)}$. The average is not a good indication of the number of operations. For example, it is shown that for about half of the integers n less than x, the number of “operations” is less than n^1.61. A similar analysis is given for Good's algorithm and for two algorithms that compute the discrete Fourier transform in O(n log n) operations: the chirp-z transform and the mixed-radix algorithm that computes the transform of a series of prime length p in O(p log p) operations.     

An effective algorithm for the two-stage location problem on a tree-like network

A two-stage facility location problem on a tree-like network is considered under the restriction that the transportation costs for a unit of production from one node to another is equal to the sum of the edges in the path connecting these nodes. Some exact algorithm with time complexity O(nm ³) is suggested for this problem, where n is the number of the production demand points and, m is an upper bound on the number of possible facility location sites of each stage.