Complexity of optimal scheduling problems with three jobs

We consider the time-optimal scheduling problemn/m/J of n jobs with fixed routes on m machines. The problem3/m/J/ with identical routes and the problem3/5/J/ are shown to be NP-hard. Similar results are obtained for the problem of minimizing the mean processing time of three jobs on m machines.Translated from Kibernetika, No. 5, pp. 50–54, September–October, 1990.     

An optimal parallel algorithm for triangulating a set of points in the plane

This paper presents an optimal parallel algorithm for triangulating an arbitrary set ofn points in the plane. The algorithm runs inO(logn) time usingO(n) space andO(_n) processors on a Concurrent-Read, Exclusive-Write Parallel RAM model (CREW PRAM). The parallel lower bound on triangulation is (logn) time so the best possible linear speedup has been achieved. A parallel divide-and-conquer technique of subdividing a problem into subproblems is employed.     

Staircase visibility and computation of kernels

Let be some set of orientations, that is, . We consider the consequences of defining visibility based on curves that are monotone with respect to the orientations in . We call such curves -staircases. Two points p andq in a polygonP are said to -see each other if an -staircase fromp toq exists that is completely contained inP. The -kernel of a polygonP is then the set of all points which -see all other points. The -kernel of a simple polygon can be obtained as the intersection of all {}-kernels, with . With the help of this observation we are able to develop an algorithm to compute the -kernel of a simple polygon, for finite . We also show how to compute theexternal -kernel of a polygon in optimal time . The two algorithms are combined to compute the ( -kernel of a polygon with holes in time .This work was supported by the Deutsche Forschungsgemeinschaft under Grant No. Ot 64/5-4 and the Natural Sciences and Engineering Research Council of Canada and Information Technology Research Centre of Ontario.     

Algorithms and optimality of scheduling soft aperiodic requests in fixed-priority preemptive systems

In this paper, we investigate the problem of scheduling soft aperiodic requests in systems where periodic tasks are scheduled on a fixed-priority, preemptive basis. First, we show that given any queueing discipline for the aperiodic requests, no scheduling algorithm can minimize the response time of every aperiodic request and guarantee that the deadlines of the periodic tasks are met when the periodic tasks are scheduled on a fixed-priority, preemptive basis. We then develop two algorithms: Algorithm is locally optimal in that it minimizes the response time of the aperiodic request at the head of the aperiodic service queue. Algorithm is globally optimal in that it completes the current backlog of work in the aperiodic service queue as early as possible.     

The computational complexity of recognizing permutation functions

Let be a finite field withq elements and a rational function over . No polynomial-time deterministic algorithm is known for the problem of deciding whetherf induces a permutation on . The problem has been shown to be in co-R co-NP, and in this paper we prove that it is inR NP and hence inZPP, and it is deterministic polynomial-time reducible to the problem of factoring univariate polynomials over . Besides the problem of recognizing prime numbers, it seems to be the only natural decision problem inZPP unknown to be inP. A deterministic test and a simple probabilistic test for permutation functions are also presented.     

Stability of the Logistic Population Model with Delayed Environmental Response

The population dynamics model , was considered. For this model with uniform distribution of delays and a _n = 0, nonnegativeness and convexity of the sequence a _k (0 k n) was shown to be the sufficient stability condition. Therefore, there is no need to constrain the reproduction rate and the mean delay .     

Parallel computation of disease transforms

Distance transforms are an important computational tool for the processing of binary images. For ann ×n image, distance transforms can be computed in time (n) on a mesh-connected computer and in polylogarithmic time on hypercube related structures. We investigate the possibilities of computing distance transforms in polylogarithmic time on the pyramid computer and the mesh of trees. For the pyramid, we obtain a polynomial lower bound using a result by Miller and Stout, so we turn our attention to the mesh of trees. We give a very simple (logn) algorithm for the distance transform with respect to theL ₁-metric, an (log² n) algorithm for the transform with respect to theL -metric, and find that the Euclidean metric is much more difficult. Based on evidence from number theory, we conjecture the impossibility of computing the Euclidean distance transform in polylogarithmic time on a mesh of trees. Instead, we approximate the distance transform up to a given error. This works for anyL _k -metric and takes time (log³ n).This research was supported by the Deutsche Forschungsgemeinschaft under Grant Al 253/1-1, Schwerpunktprogramm Datenstrukturen und effiziente Algorithmen.     

Estimating the Optimal Margins of Embeddings in Euclidean Half Spaces

Concept classes can canonically be represented by matrices with entries 1 and –1. We use the singular value decomposition of this matrix to determine the optimal margins of embeddings of the concept classes of singletons and of half intervals in homogeneous Euclidean half spaces. For these concept classes the singular value decomposition can be used to construct optimal embeddings and also to prove the corresponding best possible upper bounds on the margin. We show that the optimal margin for embedding n singletons is and that the optimal margin for half intervals over {1,...,n} is . For the upper bounds on the margins we generalize a bound by Forster (2001). We also determine the optimal margin of some concept classes defined by circulant matrices up to a small constant factor, and we discuss the concept classes of monomials to point out limitations of our approach.     

Combining the Perceptron Algorithm with Logarithmic Simulated Annealing

We present results of computational experiments with an extension of the Perceptron algorithm by a special type of simulated annealing. The simulated annealing procedure employs a logarithmic cooling schedule , where is a parameter that depends on the underlying configuration space. For sample sets S of n-dimensional vectors generated by randomly chosen polynomials , we try to approximate the positive and negative examples by linear threshold functions. The approximations are computed by both the classical Perceptron algorithm and our extension with logarithmic cooling schedules. For and , the extension outperforms the classical Perceptron algorithm by about 15% when the sample size is sufficiently large. The parameter was chosen according to estimations of the maximum escape depth from local minima of the associated energy landscape.      

Stability of Linear Difference and Differential Inclusions

Any given n×n matrix A is shown to be a restriction, to the A-invariant subspace, of a nonnegative N×N matrix B of spectral radius (B) arbitrarily close to (A). A difference inclusion , where is a compact set of matrices, is asymptotically stable if and only if can be extended to a set of nonnegative matrices B with or . Similar results are derived for differential inclusions.     

Exact optimal grillage layouts — Part I: Combinations of free and simply supported edges

In the first instalment of this three-part study, a comprehensive treatment of analytically derived, exact optimal grillage layouts for combinations of simply supported and free edges is given. In part two, grillages with combinations of simply supported, clamped and free edges will be considered.Notation k constant in specific cost function - M beam bending moment - r radius of circular edge - R ⁺,R ^–,S ⁺,S ^–,T optimal regions - x, x _j coordinate along a beam (j) - slope of the adjoint deflection at pointD in directionDA - t, v coordinates along the free edge - adjoint deflection - angle between long beams and free edge - angle between free and simply supported edges - curvature of the adjoint deflection - , angles for layouts with circular edge - total weight (cost) of grillage - coordinate along a beam in anR ⁺ region - distance defined in Fig. 3     

L 1 Sensitivity minimization for plants with commensurate delays

In this paper we consider the problem ofL ¹ sensitivity minimization for linear plants with commensurate input delays. We describe a procedure for computing the minimum performance, and we characterize optimal solutions. The computations involve solving a one-parameter family of finite-dimensional linear programs. Explicit solutions are presented for important special cases.Notation X ^* Dual space of a normed linear spaceX - All elements inS with norm 1 - S The annihilator subspace defined as . - S The annihilator subspace defined as . - BV(X) Functions of bounded variation onX - C ₀(X) Continuous function on a locally compact spaceX such that for all > 0, {x X¦ ¦f(x)¦s is compact - C ^N (a, b) Vectors of continuous functions on (a, b) The authors acknowledge support from the Army Research Office, Center for Intelligent Control, under grant DAAL03-86-K-0171, and the National Science Foundation, under grant 8810178-ECS.     

Semigroups and automorphism groups of strongly connected automata

If an automatonA = (X, I, M) is strongly connected, is its characteristic semigroup ande is a minimal idempotent of , then the automorphism groupG(A) ofA is a homomorphic image of a subgroup of the group e e (Theorem 3.1) and Theorem 3.3 about the necessary and sufficient conditions ofG(A) to be isomorphic to e e Theorems 3.1 and 3.2 make the result by Fleck (1965) more precise. Our method seems completely different from his method. That is, we use the result on regular permutation groups in Burnside's theory of groups of finite order (Theorem 2.1) as new results on the well-known partial ordering of the set of idempotents of a semigroup (Theorems 2.3, 2.5).     

Analogy and duality of texture analysis by harmonics or indicators

According to the classic harmonic approach, an orientation density function (odf)f is expanded into its corresponding Fourier orthogonal series with respect to generalized spherical harmonics, and a pole density function (pdf) into its corresponding Fourier orthogonal series with respect to spherical harmonics. While pdfs are even (antipodally symmetric) functions, odfs are generally not. Therefore, the part of the odf which cannot be determined from normal diffraction pdfs can be mathematically represented as the odd portion of its series expansion. If the odff is given, the even part can be mathematically represented explicitly in terms off itself. Thus, it is possible to render maps ofharmonic orientation ghosts, and to evaluatevariants of mathematical standard odfs resulting in identical pdfs independent of pdf data. However, if only normal diffraction pdfs are known, the data-dependentvariation width of feasible odfs remained unaccessible, and within the harmonic approach a measure of confidence in a solution of the pdf-to-odf inversion problem does not exist.According to any discrete approach, an odff defined on some setG of orientations is expanded into its corresponding Fourier orthogonal series with respect to indicator functions of the elements of a partition ofG, and a pdf defined on the upper (lower) unit hemisphereS ₊ ^{3 3} into its corresponding Fourier orthogonal series with respect to indicator functions of the elements of a partition ofS ₊ ³ . The ambiguity of the pdf-to-odf inversion problem is discussed in terms of column-rank deficiency of the augmented projection matrix. The implication of the harmonic approach to split an odf into auniquely determined and anundetermined part does no longer seem to be reasonable. However, it is possible to numerically determine data-dependent confidence intervals for the Fourier coefficients with respect to the indicator functions which can be immediately interpreted as mean orientation densities within the elements of the partition ofG. Doing so for all Fourier coefficients in the finite series expansion, i.e. for all elements of the partition of the setG, eventually results in the data-dependent variation width of odfs feasible with respect to given pdf data, and to the partitions ofG andS ₊ ³ .Thus it is confirmed that the appearance of orientation ghosts, in particular correlations oftrue andghost orientation components, depends on the representation of an odf. It may be questioned whether in practical applications the implicit assumption of the harmonic method that the even part can be determined uniquely and free of error is generally a reasonable initial condition to develop ghost correction procedures.     

How to Better Use Expert Advice

This work is concerned with online learning from expert advice. Extensive work on this problem generated numerous expert advice algorithms whose total loss is provably bounded above in terms of the loss incurred by the best expert in hindsight. Such algorithms were devised for various problem variants corresponding to various loss functions. For some loss functions, such as the square, Hellinger and entropy losses, optimal algorithms are known. However, for two of the most widely used loss functions, namely the 0/1 and absolute loss, there are still gaps between the known lower and upper bounds.In this paper we present two new expert advice algorithms and prove for them the best known 0/1 and absolute loss bounds. Given an expert advice algorithm ALG, the goal is to form an upper bound on the regret L _ALG – L* of ALG, where L _ALG is the loss of ALG and L* is the loss of the best expert in hindsight. Typically, regret bounds of a canonical form C · are sought where N is the number of experts and C is a constant. So far, the best known constant for the absolute loss function is C = 2.83, which is achieved by the recent IAWM algorithm of Auer et al. (2002). For the 0/1 loss function no bounds of this canonical form are known and the best known regret bound is , where C ₁ = e – 2 and C ₂ = 2 . This bound is achieved by a P-norm algorithm of Gentile and Littlestone (1999). Our first algorithm is a randomized extension of the guess and double algorithm of Cesa-Bianchi et al. (1997). While the guess and double algorithm achieves a canonical regret bound with C = 3.32, the expected regret of our randomized algorithm is canonically bounded with C = 2.49 for the absolute loss function. The algorithm utilizes one random choice at the start of the game. Like the deterministic guess and double algorithm, a deficiency of our algorithm is that it occasionally restarts itself and therefore forgets what it learned. Our second algorithm does not forget and enjoys the best known asymptotic performance guarantees for both the absolute and 0/1 loss functions. Specifically, in the case of the absolute loss, our algorithm is canonically bounded with C approaching and in the case of the 0/1 loss, with C approaching 3/ . In the 0/1 loss case the algorithm is randomized and the bound is on the expected regret.     

A Representation of the Interval Hull of a Tolerance Polyhedron Describing Inclusions of Function Values and Slopes

Given a nonempty set of functions

Determination of the roots and of the global extremum of a lipschitz function

Conclusion The obvious deficiency of the method (1.3), (1.9) is the possible difficulty of the operation . In connection with this one can note that all the above given statements remain valid if the number is replaced by some positive lower bound of |f(t _k ,x)| on .In computational methods, the presence of the Lipschitz constant is considered as a deficiency. In connection with this we can note that the Lipschitz constant L can be replaced by any of its upper estimates. For example, for a differentiable function f(z) one can take .Translated from Kibernetika, No. 2, pp. 71–74, March–April, 1987.     

Solving A\underline x =\underline b Using a Modified Conjugate Gradient Method Based on Roots of A

We consider the modified conjugate gradient procedure for solving A = in which the approximation space is based upon the Krylov space associated with A ^1/p and , for any integer p. For the square-root MCG (p=2) we establish a sharpened bound for the error at each iteration via Chebyshev polynomials in . We discuss the implications of the quickly accumulating effect of an error in in the initial stage, and find an error bound even in the presence of such accumulating errors. Although this accumulation of errors may limit the usefulness of this method when is unknown, it may still be successfully applied to a variety of small, almost-SPD problems, and can be used to jump-start the conjugate gradient method. Finally, we verify these theoretical results with numerical tests.