Stochastic on-line knapsack problems

Different classes of on-line algorithms are developed and analyzed for the solution of {0, 1} and relaxed stochastic knapsack problems, in which both profit and size coefficients are random variables. In particular, a linear time on-line algorithm is proposed for which the expected difference between the optimum and the approximate solution value isO(log^3/2 n). An(1) lower bound on the expected difference between the optimum and the solution found by any on-line algorithm is also shown to hold.Corresponding author.Partially supported by the Basic Research Action of the European Communities under Contract 3075 (Alcom).Partially supported by research project Models and Algorithms for Optimization of the Italian Ministry of University and Scientific and Technological Research (MURST 40%).     

Complete rotation hypersurfaces with Hk constant in space forms

In this paper we classify all complete rotation hypersurfaces withH _k constant in ⁿ⁺¹ andH ⁿ⁺¹, is the normalizedk-th symmetric function of the principal curvatures. Partial results are also given forH ⁿ⁺¹.Partially supported by DGAPA-UNAM, México, CONACYT, México, under Project 1068P, and CNPp, Brazil.     

Translation planes admitting many homologies

The translation planes with spreads inPG(3,2 ^r ) that admit >2 ^r +1 axes (coaxes) of homologies of orderu1 are classified.Partially supported by FONDECYT Project No. 890-1061     

A remark on Nehari's problem

An example of a strickly contractive Hankel matrix is given such that the central contractive extensionf _c of satisfies f _c =1. This way we answer a problem raised by Ciprian Foias.Partially supported by a Georgia State University Research Grant.     

Waiting times: Positive and negative results on the Wyner-Ziv problem

Asymptotic properties of the waiting timeW _k (x,y) until an initial segment of lengthk of a sample pathx of an ergodic finite-alphabet process is seen in an independently chosen sample pathy are discussed. Wyner and Ziv have shown that for irreducible Markov chains, (1/k) logW _k (x,y) converges in probability to the entropyH of the process. In this paper, almost sure convergence toH is established for the somewhat larger class of functions of irreducible Markov chains and convergence in probability toH is established for weak Bernoulli processes. A stationary coding of an i.i.d. process is constructed for which there is a subsequencek(n) such that (1/k(n) logW _k(n )(x,y), converges in probability to +. Positive and negative results for the case when only approximate matches are required are also obtained.Partially supported by NSF Grant DMS-9024240.From 9/1 to 12/1 earch year: Mathematies Institute, POB 127, 1364 Budapest, Hungary. 011-361-1-177-175. At other times: Department of Mathematics, University of Toledo, Toledo, Ohio 43606, (419) 537-2069.     

Density functions for prime and relatively prime numbers

Letr ^*(x) denote the maximum number of pairwiserelatively prime integers which can exist in an interval (y,y+x] of lengthx, and let ^*(x) denote the maximum number ofprime integers in any interval (y,y+x] whereyx. Throughout this paper we assume the primek-tuples hypothesis. (This hypothesis could be avoided by using an alternative sievetheoretic definition of ^*(x); cf. the beginning of Section 1.) We investigate the differencer ^*(x)—^*(x): that is we ask how many more relatively prime integers can exist on an interval of lengthx than the maximum possible number of prime integers. As a lower bound we obtainr ^*(x)—^*(x)<x ^c for somec>0 (whenx). This improves the previous lower bound of logx. As an upper bound we getr ^*(x)—^*(x)=o[x/(logx)²]. It is known that ^*(x)—(x)>const.[x/(logx)²];.; thus the difference betweenr ^*(x) and ^*(x) is negligible compared to ^*(x)—(x). The results mentioned so far involve the upper bound or maximizing sieve. In Section 2, similar comparisons are made between two types of minimum sieves. One of these is the erasing sieve, which completely eliminates an interval of lengthx; and the other, introduced by Erdös and Selfridge [1], involves a kind of minimax for sets of pairwise relatively prime numbers. Again these two sieving methods produce functions which are found to be closely related.     

The complexity of many cells in arrangements of planes and related problems

We consider several problems involving points and planes in three dimensions. Our main results are: (i) The maximum number of faces boundingm distinct cells in an arrangement ofn planes isO(m ^2/3 n logn +n ²); we can calculatem such cells specified by a point in each, in worst-case timeO(m ^2/3 n log³ n+n ² logn). (ii) The maximum number of incidences betweenn planes andm vertices of their arrangement isO(m ^2/3 n logn+n ²), but this number is onlyO(m ^3/5– n ^4/5+2 +m+n logm), for any>0, for any collection of points no three of which are collinear. (iii) For an arbitrary collection ofm points, we can calculate the number of incidences between them andn planes by a randomized algorithm whose expected time complexity isO((m ^3/4– n ^3/4+3 +m) log² n+n logn logm) for any>0. (iv) Givenm points andn planes, we can find the plane lying immediately below each point in randomized expected timeO([m ^3/4– n ^3/4+3 +m] log² n+n logn logm) for any>0. (v) The maximum number of facets (i.e., (d–1)-dimensional faces) boundingm distinct cells in an arrangement ofn hyperplanes ind dimensions,d>3, isO(m ^2/3 n ^d/3 logn+n ^d–1). This is also an upper bound for the number of incidences betweenn hyperplanes ind dimensions andm vertices of their arrangement. The combinatorial bounds in (i) and (v) and the general bound in (ii) are almost tight.Work on this paper by the first author has been supported by Amoco Fnd. Fac. Dev. Comput. Sci. 1-6-44862 and by NSF Grant CCR-8714565. Work by the third author has been supported by Office of Naval Research Grant N00014-87-K-0129, by National Science Foundation Grant DCR-82-20085, by grants from the Digital Equipment Corporation, and the IBM Corporation, and by a research grant from the NCRD—the Israeli National Council for Research and Development. An abstract of this paper has appeared in theProceedings of the 13th International Mathematical Programming Symposium, Tokyo, 1988, p. 147.     

Harmonic measures for elliptic operators of nondivergence form

Given any in (n–2, n–1), there exists a uniformly elliptic operator of nondivergence form in the upper half space ₊ ⁿ , so that the corresponding harmonic measure is supported on a set of Hausdorff dimension at most .Partially supported by the National Science Foundation     

Most standard spheres have smooth one fixed point actions ofA5. II

This paper proves that all standard spheresS ⁿ of dimension n=6 orn 9 have smooth one fixed point actions of the alternating groupA ₅ on five letters.Partially supported by the Yukawa Foundation, and also by Grant-in-Aid for Scientific Research 01740048.     

Tracking poles and representing Hankel operators directly from data

Summary We propose and analyse a method of estimating the poles near the unit circleT of a functionG whose values are given at a grid of points onT: we give an algorithm for performing this estimation and prove a convergence theorem. The method is to identify the phase for an estimate by considering the peaks of the absolute value ofG onT, and then to estimate the modulus by seeking a bestL ² fit toG over a small arc by a first order rational function. These pole estimates lead to the construction of a basis ofL ² which is well suited to the numerical representation of the Hankel operator with symbolG and thereby to the numerical solution of the Nehari problem (computing the bestH , analytic, approximation toG relative to theL norm), as analysed in [HY]. We present the results of numerical tests of these algorithms.Partially supported by grants from the AFOSR and NSF     

Regularity of invariant measures for a class of perturbed Ornstein-Uhlenbeck operators

In the framework of [5] we prove regularity of invariant measures for a class of Ornstein-Uhlenbeck operators perturbed by a drift which is not necessarily bounded or Lipschitz continuous. Regularity here means that is absolutely continuous with respect to the Gaussian invariant measure of the unperturbed operator with the square root of the Radon-Nikodym density in the corresponding Sobolev space of order 1.Partially supported by the International Science Foundation (Grant M 38000), the Russian Foundation of Fundamental Research (Grant 94-01-01556), and EC-Science Project SC1^*CT92-0784.Partially supported by the Italian National Project MURST Problemi nonlineari nell'AnalisiPartially supported by the DFG(SFB-256-Bonn, SFB-343-Bielefeld) and EC-Science Project SC1^*CT92-0784.     

Finite extinction time for some perturbed Hamilton-Jacobi equations

In this paper we study initial value problems likeu _t–R¦u¦^m+u^q=0 in ⁿ× ₊, u(·,0⁺)=u_o(·) in ^N, whereR > 0, 0 <q < 1,m 1, andu _o is a positive uniformly continuous function verifying –R¦u _o¦^m+u ₀ ^q 0 in ^N . We show the existence of the minimum nonnegative continuous viscosity solutionu, as well as the existence of the function t(·) defined byu(x, t) > 0 if 0<t<t (x) andu(x, t)=0 ift t (x). Regularity, extinction rate, and asymptotic behavior of t(x) are also studied. Moreover, form=1 we obtain the representation formulau(x, t)=max{([(u _o(x – t))^1–q –(1–q)t]₊)^1/(1–q): ¦¦R}, (x, t) ₊ ^N+1 .Partially supported by the DGICYT No. 86/0405 project.     

Metrics with finite sets of primitive extensions

In this paper, we give a complete characterization for the class of rational finite metrics with the property that the set () of primitive extensions of is finite. Here, for a metric on a setT, a positive extensionm of to a setV T is calledprimitive if none of the convex combinations of other extensions of toV is less than or equal tom. Our main theorem asserts that the following the properties are equivalent: (i) () is finite; (ii) Up to an integer factor, is a submetric of the path metric d ^H of a graphH with |(d ^H )=1; (iii) A certain bipartite graph associated with contains neither isometrick-cycles withk6 nor induced subgraphsK _3,3 ^– . We then show that () is finite if and only if the dimension of the tight span of is at most two. We also present other results, discuss applications to multicommodity flows, and raise open problems.This research was supported by grant 97-01-00115 from the Russian Foundation of Basic Research and a grant from the Sonderforschungsbereich 343, Bielefeld Universität, Bielefeld, Germany.     

Constructing arrangements optimally in parallel

We give two optimal parallel algorithms for constructing the arrangement ofn lines in the plane. The first nethod is quite simple and runs inO(log² n) time usingO(n ²) work, and the second method, which is more sophisticated, runs inO(logn) time usingO(n ²) work. This second result solves a well-known open problem in parallel computational geometry, and involves the use of a new algorithmic technique, the construction of an -pseudocutting. Our results immediately imply that the arrangement ofn hyperplanes in ^d inO(logn) time usingO(n ^d) work, for fixedd, can be optimally constructed. Our algorithms are for the CREW PRAM.This research was supported by the National Science Foundation under Grants CCR-8810568 and CCR-9003299, and by the NSF and DARPA under Grant CCR-8908092.     

The minimum of the antichains in the factor poset

Denote g(m, n) the minimum of min A, where A is a subset of {1, 2, ..., m} of size n and there do not exist two distinct x and y in A such that x divides y. We use a method of poset to prove that g(m, n)=2 ⁱ for positive integer ilog₃ m and 1+s(m, i–1), where s(m, i) is the number of odd integers x such that m/3 ⁱ .Research was supported by National Science Council of Republic of China under Grant NSC74-0201-M008d-02.     

Hofer'sL ∞-geometry: energy and stability of Hamiltonian flows,part I

Consider the group Ham ^c (M) of compactly supported Hamiltonian symplectomorphisms of the symplectic manifold (M, ) with the HoferL -norm. A path in Ham ^c (M) will be called a geodesic if all sufficiently short pieces of it are local minima for the Hofer length functional . In this paper, we give a necessary condition for a path to be a geodesic. We also develop a necessary condition for a geodesic to be stable, that is, a local minimum for . This condition is related to the existence of periodic orbits for the linearization of the path, and so extends Ustilovsky's work on the second variation formula. Using it, we construct a symplectomorphism ofS ² which cannot be reached from the identity by a shortest path. In later papers in this series, we will use holomorphic methods to prove the sufficiency of the condition given here for the characterisation of geodesics as well as the sufficiency of the condition for the stability of geodesics. We will also investigate conditions under which geodesics are absolutely length-minimizing.Oblatum 13-X-1994 & 8-V-1995Partially supported by NSERC grant OGP 0092913 and FCAR grant ER-1199Partially supported by NSF grant DMS 9103033 and NSF Visiting Professorship for Women GER 9350075     

Stable constant mean curvature hypersurfaces in ℝ n+1 and ℍ n+1(−1)

In this paper, we show that all complete stable hypersurfaces in ⁿ⁺¹(or ⁿ⁺¹ (-1)) (n = 3, 4, 5) with constant mean curvature H > 0 (or H > 1, respectively) and finite L ² norm of traceless second fundamental form are compact geodesic spheres. Keywords: stable hypersurface, constant mean curvature, isometric immersion, Bernstein theorem.*Supported by PolyU grant G-T575.**Partially supported by CNPq of Brazil.     

Dynamic partition trees

In this paper we study dynamic variants of conjugation trees and related structures that have recently been introduced for performing various types of queries on sets of points and line segments, like half-planar range searching, shooting, intersection queries, etc. For most of these types of queries dynamic structures are obtained with an amortized update time ofO(log² n) (or less) with only minor increases in query times. As an application of the method we obtain an output-sensitive method for hidden surface removal in a set ofn triangles that runs in timeO(nlogn+n ^· k ) where=log₂((1+5)/2) 0.695 andk is the size of the visibility map obtained.Research of the second author was partially supported by the ESPRIT II Basic Research Actions Program of the EC, under contract No. 3075 (project ALCOM).     

On certain locally homogeneous Clifford manifolds

Given a manifoldM, a Clifford structure of orderm onM is a family ofm anticommuting complex structures generating a subalgebra of dimension 2 ^m of End(T(M)). In this paper we investigate the existence of locally invariant Clifford structures of orderm2 on a class of locally homogeneous manifolds. We study the case of solvable extensions ofH-type groups, showing in particular that the solvable Lie groups corresponding to the symmetric spaces of negative curvature carry invariant Clifford structures of orderm2. We also show that for eachm and any finite groupF, there is a compact flat manifold with holonomy groupF and carrying a Clifford structure of orderm.Partially supported by Conicor (Argentina)Partially supported by grants from Conicet, Conicor, SECYTUNg (Argentina), and I.C.T.P. (Trieste)Partially supported by grants from Conicet, Conicor, SECYTUNC (Argentina), T.W.A.S and I.C.T.P. (Trieste)