On selecting thek largest with median tests

LetW _itk(n) be the minimax complexity of selecting thek largest elements ofn numbersx ₁,x ₂,...,x _n by pairwise comparisonsx _i :x _j . It is well known thatW ₂(n) =n–2+ [lgn], andW _k (n) = n + (k–1)lg n +O(1) for all fixed k 3. In this paper we studyW _k (n), the minimax complexity of selecting thek largest, when tests of the form Isx _i the median of {x _i ,x _j ,x _t }? are also allowed. It is proved thatW₂(n) =n–2+ [lgn], andW _k (n) =n + (k–1)lg₂ n +O(1) for all fixedk3.This research was supported in part by the National Science Foundation under Grant No. DCR-8308109.     

Fitting a least squares piecewise linear continuous curve in two dimensions

An optimal piecewise linear continuous fit to a given set of n data points D = {(x_i, y_i) : 1 ≤ i ≤ n} in two dimensions consists of a continuous curve defined by k linear segments {L₁, L₂,…,L_k} which minimizes a weighted least squares error function with weight w_i at (x_i, y_i), where k ≥ 1 is a given integer. A key difficulty here is the fact that the linear segment L_j, which approximates a subset of consecutive data points D_j ⊂ D in an optimal solution, is not necessarily an optimal fit in itself for the points D_j. We solve the problem for the special case k = 2 by showing that an optimal solution essentially consists of two least squares linear regression lines in which the weight w_j of some data point (x_j, y_j) is split into the weights λw_j and (1 − λ)w_j, 0 ≤ λ ≤ 1, for computations of these lines. This gives an algorithm of worst-case complexity O(n) for finding an optimal solution for the case k = 2.     

Characterization of normal forms possessing inverse in the λ-β-η-calculus

The aim of this paper is to generalize a result given by Curry and Feys, who have shown that the only regular combinators possessing inverse in the λ-β-η-calculus are the permutators, whose definition is p=λzλx₁…λx_n(zx_i1…x_in) for n?0 where i₁,…, i_r is a permutation of 1,…, n. Here we extend this characterization to the set of normal forms, showing that the only normal forms possessing inverse in the λ-βη-calculus are the “hereditarily finite permutators” (h.f.p.), whose recursive definition is: if n?0, P_j (1?j?n) are h.f.p. and i₁,…,i_n is a permutation of 1,…, n, then the normal form of P = λzλx₁…λx_n(z(P₁x_i1))… (P_nin) is an h.f.p.     

Mehrstufige Auswahldisziplin in einem M/G/1-Processor-sharing-System mit Prioritäten

In this paper the well-known multilevel processor-sharing algorithm for M/G/1 systems without priorities is extended to M/G/1 systems with priority classes. The average response timeT _j (x) and the average waiting timeW _j (x) for aj-class job, which requires a total service ofx sec, is analytically calculated. Some figures demonstrate, how the priority classes and the total number of the different levels affect the behavior of the functionsT _j (x) andW _j (x). In addition, the foreground-background algorithm with priorities, which is in the literature not yet covered, is treated as a special case of the multilevel processor-sharing algorithm.     

Thek-track assignment problem

Thek-track assignment problem is a scheduling problem withn jobs andk machines. Each machinej has a certain operational period (track) which starts at timea _j and ends at timeb _j . Each jobi has a specific start times _i and a specific finish timet _i . A schedule is an assignment of certain jobs to machines such that the intervals [s _i ,t _i [assigned to the same machinej do not overlap and fit into track [a _j ,b _j [. We are interested in a schedule which maximizes the number of assigned jobs. AO(n ^k?1 k!k ^k+1 )-algorithm which solves this problem is presented. Furthermore it is shown that the more general problem, in which for each track only a given set of jobs can be scheduled on that track, can be solved inO(n ^k k!k ^k )-time.     

Bounded solutions of nonlinear difference equations with advanced arguments

Sufficient conditions of existence and uniqueness of α-bounded and bounded solutions to the difference equation with advancedd arguments x(n + 1) = A(n)x(n) + B(n)x(σ₁(n)) + f(n, x(n), x(σ₂(n)), σ_i(n) ⩾ n + 1, i = 1,2, are given. It is proven that under certain conditions it is possible to find positive numbers R, μ, such that from every initial condition ξ satisfying ∥ξ∥ ⩽ R, a unique bounded solution, belonging to the ball ∥x∥ ⩽ μ, starts.     

Selection and sorting in totally monotone arrays

A two-dimensional arrayA={a[i, j]} is calledtotally monotone if, for alli ₁i ₂ andj ₁j ₂,a[i ₁,j ₁]a[i ₁,j ₂] impliesa[i ₂,j ₁]a[i ₂,j ₂]. Totally monotone arrays were introduced in 1987 by Aggarwal, Klawe, Moran, Shor, and Wilber, who showed that several problems in computational geometry and VLSI river routing could be reduced to the problem of finding a maximum entry in each row of a totally monotone array. In this paper we consider several selection and sorting problems involving totally monotone arrays and give a number of applications of solutions for these problems. In particular, we obtain the following results for anm × n totally monotone arrayA:

Numerische Lösung von Anfangswertaufgaben gewöhnlicher Differentialgleichungen n-ter Ordnung mittels Einschrittverfahren

In the present paper a new exponentially fitted one-step method is given for the numerical treatment of the initial value problemy ⁽ⁿ⁾=f(x, y, y′, ..., y ^(n?1)),y ^(j) (x ₀)=y ₀ ^(j) j=0, 1, ...n?1. The method is given by a local linearisation off(x, y, y′, ..., y ^(n?1)). Using new functions the solution of a special linear differential equation of then-th order with constant coefficients is transformed in such a way so that it no longer contains numerical singularities. The efficiency of the method is demonstrated by several numerical stiff-examples.     

L 1 shortest paths among polygonal obstacles in the plane

We present an algorithm for computingL ₁ shortest paths among polygonal obstacles in the plane. Our algorithm employs the “continuous Dijkstra” technique of propagating a “wavefront” and runs in timeO(E logn) and spaceO(E), wheren is the number of vertices of the obstacles andE is the number of “events.” By using bounds on the density of certain sparse binary matrices, we show thatE =O(n logn), implying that our algorithm is nearly optimal. We conjecture thatE =O(n), which would imply our algorithm to be optimal. Previous bounds for our problem were quadratic in time and space. Our algorithm generalizes to the case of fixed orientation metrics, yielding anO(n?^?1/2 log² n) time andO(n?^?1/2) space approximation algorithm for finding Euclidean shortest paths among obstacles. The algorithm further generalizes to the case of many sources, allowing us to compute anL ₁ Voronoi diagram for source points that lie among a collection of polygonal obstacles.     

The interval-merging problem

A closed interval is an ordered pair of real numbers [x, y], with x ? y. The interval [x, y] represents the set {i ∈ R∣x ? i ? y}. Given a set of closed intervals I={[a₁,b₁],[a₂,b₂],…,[a_k,b_k]}, the Interval-Merging Problem is to find a minimum-cardinality set of intervals M(I)={[x₁,y₁],[x₂,y₂],…,[x_j,y_j]}, j ? k, such that the real numbers represented by equal those represented by . In this paper, we show the problem can be solved in O(d log d) sequential time, and in O(log d) parallel time using O(d) processors on an EREW PRAM, where d is the number of the endpoints of I. Moreover, if the input is given as a set of sorted endpoints, then the problem can be solved in O(d) sequential time, and in O(log d) parallel time using O(d/log d) processors on an EREW PRAM.     

The region approach for computing relative neighbourhood graphs in the Lp metric

The following geometrical proximity concepts are discussed: relative closeness and geographic closeness. Consider a setV={v ₁,v ₂, ...,v _n } of distinct points in atwo-dimensional space. The pointv _j is said to be arelative neighbour ofv _i ifd _p (v _i ,v _j )≤max{d _p (v _j ,v _k ),d _p (v _j ,v _k )} for allv _k ∈V, whered _p denotes the distance in theL _p metric, 1≤p≤∞. After dividing the space around the pointv _i into eight sectors (regions) of equal size, a closest point tov _i in some region is called anoctant (region, orgeographic) neighbour ofv _i. For anyL _p metric, a relative neighbour ofv _i is always an octant neighbour in some region atv _i. This gives a direct method for computing all relative neighbours, i.e. for establishing therelative neighbourhood graph ofV. For every pointv _i ofV, first search for the octant neighbours ofv _i in each region, and then for each octant neighbourv _j found check whether the pointv _j is also a relative neighbour ofv _i. In theL _p metric, 1<p<∞, the total number of octant neighbours is shown to be θ(n) for any set ofn points; hence, even a straightforward implementation of the above method runs in θn ²) time. In theL ₁ andL _∞ metrics the method can be refined to a θ(n logn+m) algorithm, wherem is the number of relative neighbours in the output,n-1≤m≤n(n-1). TheL ₁ (L _∞) algorithm is optimal within a constant factor.     

Optimal algorithms for the average-constrained maximum-sum segment problem

Given a real number sequence A=(a₁,a₂,…,an), an average lower bound L, and an average upper bound U, the Average-Constrained Maximum-Sum Segment problem is to locate a segment A(i,j)=(ai,ai+1,…,aj) that maximizes _∑i?k?jak subject to . In this paper, we give an O(n)-time algorithm for the case where the average upper bound is ineffective, i.e., U=∞. On the other hand, we prove that the time complexity of the problem with an effective average upper bound is Ω(nlogn) even if the average lower bound is ineffective, i.e., L=−∞.     

Substitutions into propositional tautologies

We prove that there is a polynomial time substitution (y₁,…,yn):=g(x₁,…,xk) with k?n such that whenever the substitution instance A(g(x₁,…,xk)) of a 3DNF formula A(y₁,…,yn) has a short resolution proof it follows that A(y₁,…,yn) is a tautology. The qualification “short” depends on the parameters k and n.     

Eine stets quadratisch konvergente Modifikation des Steffensen-Verfahrens

It is shown that the following modification of the Steffensen procedurex _n+1=x _n ?k _s (x _n )f(x _n ) (f[x _n ,x _n ?f(x _n )])^?1 (n=0,1,...) withk _s (x)=(1?z _s (x))^?1,z _s (x)=f(x) 2f[x?f(x),x,x+f(x)]×(f[x,x?f(x)])^?2 is quadratically convergent to the root of the equation \(f(x) = (x - \bar x)^p g(x) = 0(p > 0,g(\bar x) \ne 0)\) . Furthermore \(\mathop {\lim }\limits_{n \to \infty } k_s (x_n ) = p\) holds.     

Geometric applications of a matrix-searching algorithm

LetA be a matrix with real entries and letj(i) be the index of the leftmost column containing the maximum value in rowi ofA.A is said to bemonotone ifi ₁ >i ₂ implies thatj(i ₁) ≥J(i ₂).A istotally monotone if all of its submatrices are monotone. We show that finding the maximum entry in each row of an arbitraryn xm monotone matrix requires Θ(m logn) time, whereas if the matrix is totally monotone the time is Θ(m) whenm≥n and is Θ(m(1 + log(n/m))) whenm<n. The problem of finding the maximum value within each row of a totally monotone matrix arises in several geometric algorithms such as the all-farthest-neighbors problem for the vertices of a convex polygon. Previously only the property of monotonicity, not total monotonicity, had been used within these algorithms. We use the Θ(m) bound on finding the maxima of wide totally monotone matrices to speed up these algorithms by a factor of logn.     

Computing a Hamiltonian Path of Minimum Euclidean Length Inside a Simple Polygon

Given an n-vertex convex polygon, we show that a shortest Hamiltonian path visiting all vertices without imposing any restriction on the starting and ending vertices of the path can be found in O(nlogn) time and Θ(n) space. The time complexity increases to O(nlog² n) for computing this path inside an n-vertex simple polygon. The previous best algorithms for these problems are quadratic in time and space. For our purposes, we reformulate the above shortest-path problems in terms of a dynamic programming scheme involving falling staircase anti-Monge weight-arrays, and, in addition, we provide an O(nlogn) time and Θ(n) space algorithm to solve the following one-dimensional dynamic programming recurrence $$E[i] = \min _{1\le j\le k}\min _{k\le i} \{V[k-1] + b(i,j) + c(j,k)\},\quad i=1, \dots,n,$$ where V[0] is known, V[k], for k=1,…,n, can be computed from E[k] in constant time, and B={b(i,j)} and C={c(j,k)} are known falling staircase anti-Monge weight-arrays of size n×n.     

On the RAS-algorithm

Given a nonnegative real (m, n) matrixA and positive vectorsu, v, then the biproportional constrained matrix problem is to find a nonnegative (m, n) matrixB such thatB=diag (x) A diag (y) holds for some vectorsx ∈ ? ^m andy ∈ ? ⁿ and the row (column) sums ofB equalu _i (v _j )i=1,...,m(j=1,..., n). A solution procedure (called the RAS-method) was proposed by Bacharach [1] to solve this problem. The main disadvantage of this algorithm is, that round-off errors slow down the convergence. Here we present a modified RAS-method which together with several other improvements overcomes this disadvantage.     

The asymptotic distribution of random clumps

When objects are scattered at random in the plane or in space, some of them overlap to form clumps. It is the object of the present paper to study the asymptotic distribution of the number of clumps of given size and topological structure generated within the following model: Ifx ₁, ...,x _n are points in ? ⁿ andU=-U?? ⁿ is a symmetric set, then the pointsx _i andx _j are said tooverlap or rather to form aU-coincidence, ifx _i ?x _j ∈U. Adjoining tox ₁, ...,x _n andU, the graphG(x ₁, ...,x _n ;U)?({1, ..., n}, {[i, j]:1≤ix _i ?x _j ∈U}), the so calledcoincidence-graph, we ask for the number of connected components of this graph isomorphic to a given graphH and call this numberL9x ₁, ...x _n ;U, H). In the paper, the asymptotic distribution ofL(...) under various assumptions about the distribution of the pointsx ₁, ...,x _n and the size ofU is studied. Depending on these assumptions, we prove that the asymptotic distribution ofL(...) is either Poisson or normal.