Large step volumetric potential reduction algorithms for linear programming

We consider the construction of potential reduction algorithms using volumetric, and mixed volumetric — logarithmic, barriers. These are true large step methods, where dual updates produce constant-factor reductions in the primal-dual gap. Using a mixed volumetric — logarithmic barrier we obtain an iteration algorithm, improving on the best previously known complexity for a large step method. Our results complement those of Vaidya and Atkinson on small step volumetric, and mixed volumetric — logarithmic, barrier function algorithms. We also obtain simplified proofs of fundamental properties of the volumetric barrier, originally due to Vaidya.Research supported by a Summer Research Grant from the College of Business Administration, University of Iowa.     

Die Verteilung der schlichten Funktionen in einem Funktionenraum

We consider the set of regular functions . We construct a Borel measure and a class of outer measures _h onH. With these and _h we show that: (HS)=0 and _h (HS)=0, (S is the set of normed univalent functions). From _h (HS)=0 follows—forh=t —that the Hausdorff—Billingsley-dimension ofHS is zero.     

Certain class of nonuniform estimates in multidimensional limit theorems

Quantities of the form | F(X) — G(X) | are estimated, where F and G are the convolutions of certain k-dimensional probability distributions, while X is a convex polyhedron in R^k. Estimates of the form | F(X) — G(X) | c(k)(F, G, X) are proved, differing from the known ones by the presence of the factor (F, G, X) in the right-hand side, which may turn out to be small if the polyhedron X is small in a definite sense.Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova Akademii Nauk SSSR, Vol. 184, pp. 92–105, 1990.     

A bad network problem for the simplex method and other minimum cost flow algorithms

For any integern, a modified transportation problem with 2n + 2 nodes is constructed which requires 2 ⁿ + 2 ^n–2–2 iterations using all but one of the most commonly used minimum cost flow algorithms.As a result, the Edmonds—Karp Scaling Method [3] becomes the only known good (in the sense of Edmonds) algorithm for computing minimum cost flows.     

Schwachdiskrete Bewegungsgruppen einer pseudoeuklidischen Ebene

There are considered discontinuous motion groups — in a very weak sense — of a pseudoeuclidean plane. A motion groupG is to be said (8)-discrete, if there can be found a nontrivial orbit G(P) and a Minkovskian circle diskU which contains only a finite number of elements of G(P). Such groups will be divided after their subgroup of translations, necessary and sufficient conditions for the translations will be given as same as — to a certain extent — a classification of (8)-discrete groups.

---

---

Herrn Professor Benno Klotzek zum 60. Geburtstag gewidmet     

Dense lattice packings of spheres in Euclidean spaces of dimension n⩽16 *

We present a number of lattice packings of equal spheres in ⁿ for n16 For n15, these packings have the same density as the densest known lattice packings. For n=16, the packing described here is denser than the known ones.It should be pointed out that the 16-dimensional lattice described here is equivalent to one found by E. S. Barnes and G. E. Wall, J. Aust. Math. Soc.,1, 47–63 (1959); see also J. Leech and N. J. A. Sloane, Can. J. Math.,23, 718–745 (1971) — Translator.Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova AN SSSR, Vol. 82, 144–146, 1979.     

Parabelscharen und grenzkreise in der isotropen ebene

It is known by H. Sachs [5] that the classical curve theorem of ABRAMESCU also holds in isotropic geometry. Generalising an idea due to O. Röschel [2] we regard all inscribed parabolas (s, t) of a triangle (t). This triangle is formed by the tangents of three neighbouring points of a C -curve k(t) in an isotropic plane. Let U((t)) be the circumcircle of (t) and I((t)) the incircle of the triangle (t) whose midpoints of the sides are the vertices of (t). The circle U((t)) is the locus of the isotropic focal points of (s, t) and the incircle I((T)) the envelope of the isotropic axes of (s, t). We prove that the ABRAMESU-circle — lim U((t)) — is identical with the locus of the focal points of lim (s, t) and the circle lim I((t)) with the envelope of the axes of lim (s, t). The characteristic points, different from k(t), of the circles lim U((t)) and lim I((t)) determine the direction of the affine-normal of k(t).Herrn Professor Helmut Mäurer zum 60. Geburtstag gewidmet     

The gap between monotone and non-monotone circuit complexity is exponential

A. A. Razborov has shown that there exists a polynomial time computable monotone Boolean function whose monotone circuit complexity is at leastn ^{c losn} . We observe that this lower bound can be improved to exp(cn ^1/6–o(1)). The proof is immediate by combining the Alon—Boppana version of another argument of Razborov with results of Grötschel—Lovász—Schrijver on the Lovász — capacity, of a graph.     

Exact constants in some converse theorems for approximations by trigonometric polynomials

It is known that if the continuous 2-periodic function f(x) belongs to the class w^(r) (r=1, 2, ...), i.e., it has an absolutely continuous derivative of order r—1 such that we have almost everywhereTranslated from Matematicheskie Zametki, Vol. 20, No. 5, pp. 787–792, November, 1976.     

Curvature of indefinite almost contact manifolds

The curvature tensor of indefinite almost contact manifolds is investigated. By means of the study of the Jacobi operator along spacelike, timelike and null geodesies, spaces of constant curvature are characterized as well as spaces of pointwise constant -sectional curvature. As an extension of these conditions we introduce the socalled -isotropic spaces and show a local classification of such manifolds.Supported by projects XUGA 20701B93 and DGICYT PB94 — 0633 — C02 — 01     

Minimallösungen von Differenzengleichungen in quasinormierten abelschen Gruppen

In [2] and [3] F.W.SCHÄFKE presents — as a basis for far-reaching generalizations of many classical results about linear difference equations — a simple theorem about difference equations x_n+1=A_nx_n for sequences of elements in a normed abelian group with given endomorphisms A_n and as the core of the theory a constructive method for determining the — primary important-minimal solutions.In the following note, more general structures (instead of ([o,),+,)) are considered as range of generalized norms, by which the field of application of the theory is enlarged, and- by the greater adaptibility of quasinorms — the basis for more exact estimates for different types of solutions in practical problems is given.     

Zur Kinematik der isotropen Ebene II

In this paper there are studied mozions / _o in the isotropic plane. Given a C² — curve k in the moving frame we find the enveloped curve k_o in the fixed frame _o and consider the correspondance between the isotropic curvatures A and A_o of k and k_o. Than we investigate third-order properties of the pointpaths.     

Die Verteilung der schlichten Funktionen in einem Funktionenraum

We consider the set of regular functions H = { f:f = z + ?_{n = 2}^￥ nb_n zⁿ ,|b_n | \leqslant 1} on |z| < 1H = \{ f:f = z + \sum\limits_{n = 2}^\infty {nb_n z^n ,|b_n |{\mathbf{ }} \leqslant 1\} {\mathbf{ }}} on{\mathbf{ }}|z|{\mathbf{ }}< {\mathbf{ }}1 . We construct a Borel measure and a class of outer measures _h onH. With these and _h we show that: (HS)=0 and _h (HS)=0, (S is the set of normed univalent functions). From _h (HS)=0 follows—forh=t —that the Hausdorff—Billingsley-dimension ofHS is zero.     

Computations on the growth of the first factor for prime cyclotomic fields II

It is shown by computing thath(p) — the first factor of the class number of the prime cyclotomic fieldk(exp(2i/p)) — is strictly increasing for 19p1097.     

An axiomatization of the nucleolus

In this paper we give a set of axioms characterizing the nucleolus of a TU-game on the class of zero-monotonic games as well as on the class of balanced games. Among the axioms there are familiar ones like anonymity (ANN) and covariance (COV), a restriction of a known property, the restricted reduced game property (ResRGP) and a continuity axiom (LIM). Further we introduce another property of the nucleolus — the alternative reduced game property (AltRGP) — and show that this property together with the ones mentioned before characterizes the nucleolus almost completely on its definition set.     

Investigation of the working region of kapron fibers

Kapron fibers with various stretch ratios have been subjected to tensile stress relaxation tests at constant clamped length. The relaxation constants — activation energy U₀ and the coefficient — are calculated from the results of the experiments. It is shown that the fiber parameters U₀ and depend on the given molecular orientation.All-Union Scientific-Research Institute of Synthetic Fibers, Kiev Branch. Translated from Mekhanika Polimerov, Vol. 4, No. 4, pp. 736–739, July–August, 1968.     

Zur Theorie der erzwungenen Schwingungen des symmetrischen Kreisels

Summary The object of this paper is to give a theory of the experiments described in the foregoing paper. The applied system of non-linear differential equations byA. Föppl is first solved approximately for small angles, that means small deviations of the axis of the gyroscope from the verticaldirection, the cases without and with consideration of damping force being discussed separately. All characteristic features of the motion observed in the experiments are explained.—After that, an exact particular solution is given for the case of a circular periodic force. An approximate calculation is carried out for the case of a periodic elliptical force acting on afast rotating gyroscope. The solution contains an infinite number of resonance frequencies (subharmonic resonances and resonances with sums and differences of the forced and natural frequencies).     

A priori estimates on the semiaxis t≥0 for the solutions of the equations of motion of linear viscoelastic fluids with an infinite Dirichlet integral,and their applications

The solvability on the semiaxis t0 of initial-boundary value problems are investigated for the equations of the motion of linear viscoelastic fluids — Oldroyd fluids and Kelvin—Voight fluids—for which the right-hand sides satisfy the conditions f, f_t L(R⁺; L₂()). The existence of small stable solutions, periodic with respect to t, is proved for the equations of the motion of Oldroyd fluids and Kelvin—Voight fluids, with a small right-hand side f, periodic with respect to t.Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova Akademii Nauk SSSR, Vol. 182, pp. 86–101, 1990.     

Error-Correcting Codes over an Alphabet of Four Elements

The problem of finding the values of A_q(n,d)—the maximum size of a code of length n and minimum distance d over an alphabet of q elements—is considered. Upper and lower bounds on A₄(n,d) are presented and some values of this function are settled. A table of best known bounds on A₄(n,d) is given for n 12. When q M < 2q, all parameters for which A_q(n,d) = M are determined.     

Hamiltonian structures of nonlinear evolution equations connected with a polynomial pencil

For a generalized Zakharov-Shabat system in which the matrix potential is a polynomial in the spectral parameter a generating operator is constructed which makes it possible to compactly write out the nonlinear evolution equations (NEE) connected with the system. The eigenfunctions of the generating operator — the squares of solutions of the original system — are found. The Hamiltonian property of the NEE and the existence of a hierarchy of Hamiltonian structures are established.Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova AN SSSR, Vol. 120, pp. 55–68, 1982.