An algorithm for constructing an optimal structural schedule

The article is devoted to the problem of finding an optimal schedule for a class of functionals ƒ which allows for the existence of a structural set of activities. The functionalƒ(R), where, is defined in the following way: where {_i(t)} is a structural set of functions, and the function F is defined on any finite set of arguments and satisfies the following conditions: 1)F(x)=(x); 2) F(x₁,x₂)=(x₁,x₂), F(x₁,x₂,...x₃)= (x₁, F(x₂,...,x_s)), S2; 3) and do not decrease in each of their arguments, and moreover, 3a) strictly increases with the increase of both arguments, 3b) if (x₁,x₂)>(x₁, x₂ (x₂, x₃)> (x₂,x₃), then F(x₁,x₂,x₃)>F(x₁,x₂,x₃).Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova AN SSSR, Vol. 124, pp. 5–20, 1983.     

A chord-stretching map of a convex loop is an isometry

Let ⁿ be n-dimensional Euclidean space, and let : [0, L] ⁿ and : [0, L] ⁿ be closed rectifiable arcs in ⁿ of the same total length L which are parametrized via their arc length. is said to be a chord-stretched version of if for each 0s tL, |(t)–(s)| |(t)–(s)|. is said to be convex if is simple and if ([0, L]) is the frontier of some plane convex set. Individual work by Professors G. Choquet and G. T. Sallee demonstrated that if were simple then there existed a convex chord-stretched version of . This result led Professor Yang Lu to conjecture that if were convex and were a chord-stretched version of then and would be congruent, i.e. any chord-stretching map of a convex arc is an isometry. Professor Yang Lu has proved this conjecture in the case where and are C ² curves. In this paper we prove the conjecture in general.     

On the complexity of following the central path of linear programs by linear extrapolation II

A class of algorithms is proposed for solving linear programming problems (withm inequality constraints) by following the central path using linear extrapolation with a special adaptive choice of steplengths. The latter is based on explicit results concerning the convergence behaviour of Newton's method to compute points on the central pathx(r), r>0, and this allows to estimate the complexity, i.e. the total numberN = N(R, ) of steps needed to go from an initial pointx(R) to a final pointx(), R>>0, by an integral of the local weighted curvature of the (primal—dual) path. Here, the central curve is parametrized with the logarithmic penalty parameterr0. It is shown that for large classes of problems the complexity integral, i.e. the number of stepsN, is not greater than constm log(R/), where < 1/2 e.g. = 1/4 or = 3/8 (note that = 1/2 gives the complexity of zero order methods). We also provide a lower bound for the complexity showing that for some problems the above estimation can hold only for 1/3.As a byproduct, many analytical and structural properties of the primal—dual central path are obtained: there are, for instance, close relations between the weighted curvature and the logarithmic derivatives of the slack variables; the dependence of these quantities on the parameterr is described. Also, related results hold for a family of weighted trajectories, into which the central path can be embedded.On leave from the Institute of Mathematics, Eötvös University Budapest, H-1080 Budapest, Hungary.     

Quasianapole Interaction of Charged Fermions

We obtain the analytic expression for the total cross section of the reaction e ^– e ⁺l ^– l ⁺ (l=,) taking possible quasianapole interaction effects into account. We find numerical restrictions on the interaction parameter value from data for the reaction e ^– e ^+–+ in the energy domain below the Z ⁰ peak.     

An efficient heuristic algorithm for minimum matching

We give a new heuristic algorithm for minimum matching problems and apply it to the Euclidean problem with random vertices in 2 dimensions. The algorithm is based on simulated annealing and performs in practice faster than previous heuristic algorithms yielding suboptimal solutions of the same good quality. From configurations with up toN=20.000 vertices in the unit square we estimate that the length of a minimum matching scales asymptotically asLN with (=0.3123±0.0016.

---

Zusammenfassung Wir stellen einen neuen heuristischen Algorithmus für minimale Matching-Probleme vor und wenden diesen auf das euklidische Problem mit zufÄlliger Punkteverteilung in 2 Dimensionen an. Auf Simulated Annealing basierend lÄuft der Algorithmus schneller als frühere heuristische Algorithmen und erreicht dabei suboptimale Lösungen gleich guter QualitÄt. Aus Konfigurationen mit bis zuN=20.000 Punkten im Einheitsquadrat schÄtzen wir, da\ für die LÄnge des minimalen Matchings asymptotischLN mit=0.3123±0.0016 gilt.

     

On a Test Statistic for Linear Trend

Let {W(s)} _s 0 be a standard Wiener process. The supremum of the squared Euclidian norm Y (t)², of the R²-valued process Y(t)=(1/t W(t), {12/t ³ int_{0 t} s dW (s)– {3/t} W(t)), t [, 1], is the asymptotic, large sample distribution, of a test statistic for a change point detection problem, of appearance of linear trend. We determine the asymptotic behavior P {sup _t [, 1] Y(t)² > u as u , of this statistic, for a fixed (0,1), and for a moving = (u) 0 at a suitable rate as u . The statistical interest of our results lie in their use as approximate test levels.     

Growth of length of sequential derivation transformed into natural one

We consider the (&, )-fragment of the intuitionistic propositional calculus. It is proved that under the standard transformation of a Gentzen derivation into a natural derivation(), the length of (())2^2·length( ). There is constructed a sequence of Gentzen derivations of length _i, for which the length of (( _i))2^{1/3·length(i}), which shows that the upper bound obtained is not too weak.Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova AN SSSR, Vol. 88, pp. 192–196, 1979.     

Isometries of symmetric operator spaces associated with AFD factors of typeII and symmetric vector-valued spaces

If is a surjective isometry of the separable symmetric operator spaceE(M, ) associated with the approximately finite-dimensional semifinite factorM and if · _E(M,) is not proportional to · _{L 2}, then there exist a unitary operatorUM and a Jordan automorphismJ ofM such that(x)=UJ(x) for allxME(M, ). We characterize also surjective isometries of vector-valued symmetric spacesF((0, 1), E(M, )).Research supported by the Australian Research Council     

Topologically invariant linear forms on spaces of abstract distributions on a locally compact abelian group

A special case of the main result proved in this paper is the following. IfG is a locally compact, -compact, non-compact connected abelian group, thenL ² (G)={f–*f:fL ² (G), L ¹ (G), 0 and _G =1}. In this case, any topologically invariant linear form onL ² (G) is 0.     

Left linear theories — A generalization of module theory

In this paper we introduce left linear theories of exponentN (a set) on the setL as mapsL ×L ^N (l, ) l · L such that for alll L and , L ^N the relation (l · ) =l( · ) holds, where · L ^N is given by ( · )(i) = (i),i N. We assume thatL has a unit, that is an element L ^N withl · =l, for alll L, and · = , for all L ^N . Next, left (resp. right)L-modules andL-M-bimodules and their homomorphisms are defined and lead to categoriesL-Mod, Mod-L, andL-M-Mod. These categories are algebraic categories and their free objects are described explicitly. Finally, Hom(X, Y) andX Y are introduced and their properties are investigated.Herrn Professor Dr. D. Pumplün zum 60. Geburtstag gewidmet     

On measures that agree on balls

The fundamental result: if and v are two finite Borel measures, defined in the spaceL ^p[0, 1] (1p<) or in C(K) (K is a metric compactum without isolated points), then from the equalities (B)=v(B) for all balls B of radius 1 there follows that =v. In addition, in the spaces C(K) and _p (1p<) from the inequalities (B) v(B) there follows that v.Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova Akademii Nauk SSSR, Vol. 177, pp. 122–128, 1989.     

Extension of Operators Defined on Reflexive Subspaces of L 1 or L 1/H 1 0

Inperpolation theory is used to develop a general pattern for proving the extension theorems mentioned in the title. In the case where the range space G is a w ^*-closed subspace of L or H with reflexive annihilator F, a necessary and sufficient condition on G is found for such an extension to always be possible. Specifically, F must be Hilbertian and become complemented in L ^p (1 < p 2) after a suitable change of density. Bibliography: 17 titles.     

Sur certaines algèbres associées à une mesure de Guelfand

Let be a Guelfand measure (cf. [A, B]) on a locally compact groupG DenoteL ₁ (G)=*L ₁(G)* the commutative Banach algebra associated to . We show thatL ₁ (G) is semi-simple and give a characterization of the closed ideals ofL ₁ (G). Using the -spherical Fourier transform, we characterize all linear bounded operators inL ₁ (G) which are invariants by -translations (i.e. such that ¹(( _x f) )=( _x ((f)) for eachxG andfL ₁ (G); where _x f(y)=f(xy); x,y G). WhenG is compact, we study the algebraL ₁ (G) and obtain results analogous to ones obtained for the commutative case: we show thatL ₁ (G) is regular, all closed sets of its Guelfand spectrum are sets of synthesis and establish theorems of harmonic synthesis for functions inL _p (G) (p=1,2 or +).

     

Selfdecomposable distributions for maxima of independent random vectors

Summary In the present paper the limit laws for conveniently normalized multivariate sample extremes are characterized by means of the decomposability of probability distributions. Continuous automorphisms ofR ^d =[–,]^d with respect to the operation v defined by x y=(max(x _i, y_i),i=1... d) are treated as norming mappings. An integral representation of the limit distributions is found using their log-concavity and a decomposition ofR ^d in orbits of the norming family. Finally an example is given as an illustration.Research supported in part by the Committee of Science, Bulgarian Concil of Ministers, under contract no. 60/1987     

On the asymptotic and invariantσ-algebras of random walks on locally compact groups

Summary Consider a random walk of law on a locally compact second countable groupG. Let the starting measure be equivalent to the Haar measure and denote byQ the corresponding Markov measure on the space of pathsG . We study the relation between the spacesL (G , ^a ,Q) andL (G , ⁱ ,Q) where ^a and ⁱ stand for the asymptotic and invariant -algebras, respectively. We obtain a factorizationL (G , ^a ,Q) L (G , ⁱ ,Q)L (C) whereC is a cyclic group whose order (finite or infinite) coincides with the period of the Markov shift and is determined by the asymptotic behaviour of the convolution powers ⁿ.     

On inertial wave and flow structure at low Rossby number

Flow disturbances produced by the slow relative motion of an impermeable body in a large, rapidly rotating vessel are studied as an asymptotic theory for an inviscid, incompressible fluid at a small Rossby number (u _c /L1). The axial distance between the vessel wallsH is assumed to be so much larger than the body scaleL that the reduced height H/L is of unit order or greater. This flow admits a columnar structure near the body and an outer nonlinear structure of the inertial-wave type far above the forcing region, at distances along the rotation-axis (z=0(L/)). The inner boundary condition for the outer problem is provided by transferring the impermeable surface condition through the columnar structure; the outer solution in turn determines the vorticity and the solution of the columnar inner region.For thin obstacles or shallow ground topography (1), the outer solution is governed by an equation comparable to a linear one for inertial waves. The linear solutions obtained for steady transverse motion in an infinite domain () shows that, in this case, surface (perturbation) velocities are orthogonal to those in an irrotational (non-rotating) flow over the same ground topography. In the far field, i.e., ( z/L l) disturbances are confined mainly behind a wedge-shaped caustic front downstream of the rotation axis , wherein their amplitudes are comparable to , in general accord with Lighthill's result from group-velocity consideration. The field behind the caustic supports, however, lee waves extending far downstream with diminishing strength. Their wave lengths belong to orderLz/x, and therefore these waves should appear to be densely packed in the wedge-shaped region. The question on tilting of the Taylor column is delineated; the structure of the caustic zone and its upstream flow behavior are also analyzed.

---

Zusammenfassung Die Strömung um einen Körper, der sich langsam in einem grossen, rotierenden Behälter bewegt, wird untersucht mit einer asymptotischen Theorie für eine reibungsfreie, inkompressible Flüssigkeit bei einer kleinen Rossby-Zahl, d.h. u _c /L1. Der axiale AbstandH zwischen den Gefässwänden wird als soviel grösser als die Körperabmessung angenommen, dass für die reduzierte Höhe =H/L 0(1) gilt. Diese Strömung erlaubt eine säulenähnliche Struktur (Taylor column) in Körpernähe und eine äussere, nichtlineare Struktur vom Wellentyp für Höhenz=0(L/) über dem Köper. Die innere Randbedingung für das äussere Problem wird erhalten, indem die Bedingung an der Wand durch die Säule verschoben wird. Die äussere Lösung bestimmt ihrerseits die Rotation und damit die Lösung im inneren, säulenartigen Bereich.Wenn Körper oder Bodenform flach sind (1), so wird die Aussenlösung durch eine Gleichung bestimmt, welche vergleichbar ist mit einer linearen Gleichung für Trägheitswellen. Lineare Lösungen werden für gleichförmige Bewegung von der Achse weg in einem unbegrenzten Bereich ) gegeben. Sie zeigen, dass die Oberflächenstromlinien orthogonal zu den Stromlinien sind, die bei rotationsfreier (nichtdrehender) Strömung über der gleichen Bodenform entstehen. Im Fernfeld ( z/L l) sind Störungen hauptsächlich auf ein keilförmiges Gebiet stromabwärts von der Rotationsachse ( ) begrenzt. In diesem Gebiet geht ihre Amplitude mit , in Uebereinstimmung mit Lighthill's Resultat, das mit der Gruppengeschwindigkeit hergeleitet wurde. Im keiförmigen Gebiet bestehen drei Familien von Lee-Wellen, welche sich mit unveränderter Stärke weit stromabwärts erstrecken. Ihre Wellenlängen gehören zur OrdnungLx/z, weshalb die Wellen im keilförmigen Bereich dicht gepackt erscheinen. Die Frage der Neigung der Taylor Säule behandelt und die Struktur des Randes vom keilförmigen Bereich wird analysiert.

---

---

This work is dedicated to Professor Nicholas Rott on the occasion of his sixtieth birthday.     

Partitioning arrangements of lines II: Applications

In this paper we present efficient deterministic algorithms for various problems involving lines or segments in the plane, using the partitioning algorithm described in a companion paper [A3]. These applications include: (i) anO(m ^2/3 n ^2/3 · log^2/3 n · log^/3 (m/n)+(m+n) logn) algorithm to compute all incidences betweenm points andn lines, where is a constant <3.33; (ii) anO(m ^2/3 n ^2/3 · log^5/3 n · log^/3 (m/n)+(m+n) logn) algorithm to computem faces in an arrangement ofn lines; (iii) anO(n ^4/3 log^(+2)/3 n) algorithm to count the number of intersections in a set ofn segments; (iv) anO(n ^4/3 log^{( + 2)/3} n) algorithm to count red-blue intersections between two sets of segments, and (v) anO(n ^3/2 log^/3 n) algorithm to compute spanning trees with low stabbing number for a set ofn points. We also present an algorithm that, given set ofn points in the plane, preprocesses it, in timeO(nm log^+1/2 n), into a data structure of sizeO(m) forn lognmn ², so that the number of points ofS lying inside a query triangle can be computed inO((n/m) log^3/2 n) time.Work on this paper has been supported by Office of Naval Research Grant N00014-87-K-0129, by National Science Foundation Grant DCR-83-20085, and by grants from the Digital Equipment Corporation and the IBM Corporation. A preliminary version of this paper appears in theProceedings of the 5th ACM Symposium on Computational Geometry, 1989, pp. 11–22.     

Positive Solutions for a Singular Nonlinear Problem on a Bounded Domain in R 2

For a bounded regular Jordan domain in R ², we introduce and study a new class of functions K() related on its Green function G. We exploit the properties of this class to prove the existence and the uniqueness of a positive solution for the singular nonlinear elliptic equation u+(x,u)=0, in D(), with u=0 on and uC(), where is a nonnegative Borel measurable function in ×(0,) that belongs to a convex cone which contains, in particular, all functions (x,t)=q(x)t ^–,>0 with nonnegative functions qK(). Some estimates on the solution are also given.     

Drachennetze mit geradlinigen Hauptdiagonalen

A C^s-net of curves N (s1) [3] in a regular C^s-2-surface Eⁿ (n2) is called a C^s-kite- net [4] if N and the net N₁ of its angular bisecting curves form a pair of diagonal nets [1] in such a way that each mesh of N-curves possessing two N₁-diagonals shows, with respect to one of these (calledmain diagonal), the same symmetry of angles and lengths as a rectilinear kite in E². Referring to the fact that the main diagonals of any C^s-kite-net N (s2) are geodesics in [5], we ask in this paper for all C^s-kite-nets and, more generally, C^s-D-nets [5] (s1) withstraight main diagonals. This leads, among other results, to a characterization of the skew ruled surfaces in Eⁿ (n3) with constant parameter of distribution and the constant striction /2.

---

---

Herrn Professor Dr. WERNER BURAU zum 70. Geburtstag gewidmet     

Subsets with Restricted Movement

Let G be a finite permutation group on a set with no fixed points in and let m and k be integers with 0 < m < k. For a finite subset of the movement of is defined as move() = max_gG| ^g \ |. Suppose further that G is not a 2-group and that p is the least odd prime dividing |G| and move() m for all k-element subsets of . Then either || k + m or k (7m – 5) / 2, || (9m – 3)/2. Moreover when || > k + m, then move() m for every subset of .