Computational complexity of norm-maximization

This paper discusses the problem of maximizing a quasiconvex function over a convex polytopeP inn-space that is presented as the intersection of a finite number of halfspaces. The problem is known to beNP-hard (for variablen) when is thep ^th power of the classicalp-norm. The present reexamination of the problem establishesNP-hardness for a wider class of functions, and for thep-norm it proves theNP-hardness of maximization overn-dimensionalparallelotopes that are centered at the origin or have a vertex there. This in turn implies theNP-hardness of {–1, 1}-maximization and {0, 1}-maximization of a positive definite quadratic form. On the good side, there is an efficient algorithm for maximizing the Euclidean norm over an arbitraryrectangular parallelotope.The authors are indebted to J. O'Rourke, P, Pardalos and R. Freund for useful references. The second and third authors are indebted to the Institute for Mathematics and its Applications in Minneapolis, where much of this paper was written: they acknowledge additional support from the Alexander von Humboldt Stiftung and the National Science Foundation, respectively.     

Asymptotic Density and the Asymptotics of Partition Functions

Let A be a set of positive integers with gcd (A) = 1, and let p _A (n) be the partition function of A. Let c ₀ = 2/3. If A has lower asymptotic density and upper asymptotic density , then lim inf log p _A (n)/c ₀ n and lim sup log p _A (n)/c ₀ n . In particular, if A has asymptotic density > 0, then log p _A (n) c₀n. Conversely, if > 0 and log p _A (n) c ₀ n, then the set A has asymptotic density .     

Partially ordered permutation groups

In this note we discuss permutation groups (G, ) in which the set admits aG-invariant order. By aG-invariant partial order (G-partial order) we mean a partial order < of such that < implies g<g, for all and in andg inG. If the set admits aG-partial order which is a total order, then (G, ) is an O-permutation group (orderable permutation group).The main concern of this paper is the development of a foundation for partially ordered permutation groups analogous to the existing one for partially ordered groups, as found in Fuchs [2].     

The imaginary zeros of a mixed Bessel function

In the present work we study the existence and monotonicity properties of the imaginary zeros of the mixed Bessel functionM _v(z)=(z²+)J_v(z)+zJ_v(z). Such a function includes as particular cases the functionsJ _v(z)(==0), J_v(z)(=–v²,=1)x andH _v(z)=J_v(z)+zJ_v(z), whereJ _v(z) is the Bessel function of the first kind and of orderv>–1 andJ _v(z), J_v(z) are the first two derivatives ofJ _v(z). Upper and lower bounds found for the imaginary zeros of the functionsJ _v(z), J_v(z) andH _v(z) improve previously known bounds.

---

Zusammenfassung Dieser Artikel betrifft die Existenz und Monotonie von Eigenschaften imaginärer Nullen der gemischten BesselfunktionM _v(z)=(z²+)J_v(z)+zJ_v(z). Eine solche Funktion enthält als Spezialfall die FunktionenJ _v(z)(==0), J_v(z)(=–v²,=1) undH _v(z)=J_v(z)+zJ_v(z), woJ _v(z)die Besselfunktion von erster Art und Ordnungv>–1 andJ _v(z), J_v(z) sind die erste und zweite Ableitung vonJ _v(z). Untere und obere Schranken, die für die imaginären Nullen der FunktionenJ _v(z), J_v(z) undH _v(z) gefunden wurden, verbessern früher bekannte Resultate.

     

p-Frames in Separable Banach Spaces

Let X be a separable Banach space with dual X ^*. A countable family of elements {g _i }X ^* is a p-frame (1 p ) if the norm _X is equivalent to the ^p -norm of the sequence {g _i ()}. Without further assumptions, we prove that a p-frame allows every gX ^* to be represented as an unconditionally convergent series g=d _i g _i for coefficients {d _i } ^q , where 1/p+1/q=1. A p-frame {g _i } is not necessarily linear independent, so {g _i } is some kind of overcomplete basis for X ^*. We prove that a q-Riesz basis for X ^* is a p-frame for X and that the associated coefficient functionals {f _i } constitutes a p-Riesz basis allowing us to expand every fX (respectively gX ^*) as f=g _i (f)f _i (respectively g=g(f _i )g _i ). In the general case of a p-frame such expansions are only possible under extra assumptions.     

MP-algebras with relative types

In this paper we define anMP-algebra with relative types (B, s, t ₁ t ₂,t ₃) where (B,s) is a monadic algebra and wheret ₁,t ₂,t ₃ arerelative types fromB to itself satisfying:t ₁ (ps(q))=t _i (p)s(q),s(t _i (p))=t _i (p),s(p)t ₁ (p)t ₂ (p)t ₃ (p), ifi j thent _i (p)t _j (p)=0, ifp q) thent ₃ (p) =t ₃ (q) andt ₂(p) t₃ (p) t ₂ (q) t ₃ (q), ifp q =0 thent _i ,(p) t _j (q) t _k (pq) withk=min(i + j, 3). Every relation algebra has anMP-algebra with relative types associated with it. We prove by Givant's results that everyMP-algebra with relative types arises in this way from some relation algebra generated by its rectangles.Presented by B. Jónsson.     

Approximations for optimal Laplace transform inversion

A function (p) of the Laplace transform operatorp is approximated by a finite linear combination of functions (p+ _r ), where (p) is a specific function ofp having a known analytic inverse (t), and is chosen in accordance with various considerations. Then parameters _r ,r=1, 2,...,n, and then corresponding coefficientsA _r of the (p + _r ) are determined by a least-square procedure. Then, the corresponding approximation to the inversef(t) of (p) is given by analytic inversion of _r=1 ⁿ A _r (p+ _r ). The method represents a generalization of a method of best rational function approximation due to the author [which corresponds to the particular choice (t)1], but is capable of yielding considerably greater accuracy for givenn.The computations for this paper were carried out on the CDC-6600 computer at the Computation Center of Tel-Aviv University. The author is grateful to Dr. H. Jarosch of the Weizmann Institute of Science Computer Center for use of their Powell minimization subroutine (Ref. 1).     

Syzygies of Veronese Embeddings

We prove that the Veronese embedding _O ⁿ (d): ^{n N} with n2, d3 does not satisfy property N _p (according to Green and Lazarsfeld) if p3d–2. We make the conjecture that also the converse holds. This is true for n=2 and for n=d=3.     

Weyl group extension of quantized current algebras

In this paper we extend Drinfeld's current realization of quantum affine algebrasU _q() and of the Yangians in several directions: we construct current operators for non-simple roots of g, define a new braid group action in terms of the current operators, and describe the universalR-matrix for the corresponding Drinfeld comultiplication in the forms of an infinite product and of certain integrals over current operators.     

First-order differentiability of the flow of a system withL p controls

This paper considers the study of the regularity of the flow of a nonautonomous nonlinear control process when the set of control maps is endowed with theL ^p -topology. Roughly speaking, it is proved that, if the norm of the mapf(t, x, u) defining the process together with its first derivatives goes to infinity, with the norm ofu not faster thanu ^p ,p>1, then the flow isC ¹ in theL ^p -topology. This property implies that, if the control maps are bounded, then the flow is differentiable in anyL ^p ,p>1. Moreover, it is proved that the only systems for which the flow is differentiable inL ¹ are the affine ones.This research was supported by a grant from Ministero dell'Universitá e della Ricerca Scientifica e Tecnologica, Rome, Italy.     

Interpolation of weighted spaces of differentiable functions onR d

Summary Let W _p ^m (w) be the Sobolev space of functions f such thatD fL _p(w) for ||m.     

A Strong Maximum Principle for some quasilinear elliptic equations

In its simplest form the Strong Maximum Principle says that a nonnegative superharmonic continuous function in a domain ⁿ ,n 1, is in fact positive everywhere. Here we prove that the same conclusion is true for the weak solutions of – u + (u) = f with a nondecreasing function ,(0)=0, andf0 a.e. in if and only if the integral((s)s) ^–1/2 ds diverges ats=0+. We extend the result to more general equations, in particular to – _p u + (u) =f where _p (u) = div(|Du| ^p-2 Du), 1 <p < . Our main result characterizes the nonexistence of a dead core in some reaction-diffusion systems.This work was partly done while the author was visiting the University of Minnesota as a Fulbright Scholar.     

Ausheilung von Strahlungsschäden in Si-Transistoren

Summary Si-planar transistors were irradiated with fast neutrons and with -rays (Co⁶⁰). The reverse currentI _CBO and the current amplification factorh _FB at small emitter currents vary with irradiation dose as expected. With -rays however saturation is observed at rather small -flux.Radiation damage in Si-transistors may be totally annealed at 300°C. The annealing after neutron irradiation proceeds in two distinct steps at 120°C and at 280°C respectively, whereas -irradiation defects anneal in one step at 120°C.Comparison with measurements on homogeneous crystals leads us to the conclusion that theE-center (Combination of a vacancy with a phosphorous atom) is responsible for most of the radiation damage observed in npn-Si-planar transistors.     

On the dimensions of ordered sets of bounded degree

Let P be a partially ordered set. Define k = k (P) = max _p |{x P : p < x or p = x}|, i.e., every element is comparable with at most k others. Here it is proven that there exists a constant c (c < 50) such that dim P < ck(log k)². This improves an earlier result of Rödl and Trotter (dim P 2 k ²+2). Our proof is nonconstructive, depending in part on Lovász' local lemma.Supported in part by NSF under Grant No. MCS83-01867 and by a Sloan Research Fellowship.     

“Spatial nodes” in discrete location problems

Discrete location models often assume an underlying network where demands originate at point nodes. To apply these models to planar regions with continuously distributed demand, the region is usually partitioned into zones and the demand from each zone is assumed to originate at a point, usually the zone centroid. Thus, the point node in the underlying network represents a spatial zone with a finite area. This paper examines the effect of approximating these spatial nodes by point nodes. In some problem scenarios, the approximation does not affect the solution. However, especially when the locational criterion includes the consideration of intra-zonal travel cost variances (e.g. travel time variance) and demands may originate anywhere within zones of nonzero area, point nodes do not give an accurate evaluation of the performance of a locational design. To illustrate the application of the concept of spatial nodes, a model is formulated for locatingp (fire-fighting) units in a region having continuously distributed demand with the objective of minimizing a nonlinear function of arrival times of the first and second closest units to any (fire) incident. A heuristic site-substitution procedure is presented that solves the formulated model.     

Ein konvergentes Iterationsverfahren zur Bestimmung der Nullstellen eines Polynoms

Summary In order to determine the roots of a polynomialp, a sequence of numbers {x _k} is constructed such that the associated sequence {|p(x _k)|} decreases monotonically. To determine a new iteration pointx _k+1 such that |p(x _k+1)|<-|p(x _k)| ( is a positive real constant, <1, depending only on the degree ofp), we determine a circleK aroundx _k which contains no root ofp and compute the values ofp atN points which are distributed equally on the circumference ofK (N again depends only on the degree ofp); at least one of theN points is shown to satisfy the given condition. Computing the function values by means of Fourier synthesis according to Cooley-Tukey [2] and combining our iteration step with the normal step of the method of Nickel [1], we obtain a numerically safe and fast algorithm for determining the roots of arbitrary polynomials.     

Inequalities of Different Metrics for Differentiable Periodic Functions, Polynomials, and Splines

We obtain new inequalities of different metrics for differentiable periodic functions. In particular, for p, q (0, ], q > p, and s [p, q], we prove that functions satisfy the unimprovable inequality

Approximate solution of the transient free convection laminar boundary layer equations

Zusammenfassung Es wird eine angenäherte Lösung der Gleichungen der laminaren Grenzschicht in freier Konvektionsströmung an einer halbunendlichen senkrechten Platte angegeben. Obwohl bereits Ähnlichkeitsvariablen für die transiente Strömung dieses Typus angegeben wurden, ist bis heute kein numerisches Ergebnis bekannt. Daher wird im vorliegenden Aufsatz das System der nichtlinearen, gekoppelten partiellen Differentialgleichungen durch Approximation gelöst. Durch ein Integrationsverfahren kann das System der Differentialgleichungen mit drei unabhängigen Variablen (zwei Ortskoordinaten und Zeit) auf ein solches mit zwei unabhängigen Variablen zurückgeführt werden. Das so verbleibende Gleichungssystem wird auf zwei verschiedene Arten behandelt. Die eine wird als eine Methode der Integralrelationen bezeichnet, die andere als Linienmethode (ein Verfahren der Differenzenrechnung). Nach beiden Methoden werden für verschiedene Prandtl-Zahlen Geschwindigkeits- und Temperaturprofile berechnet und mit experimentellen Ergebnissen verglichen.

---

Nomenclature a constant - a _i approximating function, see equation (24) - b constant - b _i approximating function, see equation (24) - d _i approximating functions, see equation (33) - e _i approximating functions, see equation (34) - f _i weighting functions - g _i weighting functions - g acceleration due to gravity - G Grashof number - h heat transfer coefficient - k thermal conductivity - L characteristic length - L(u) differential operator onu - Nu Nusselt number - P Prandtl number - q heat flux - t time - T temperature - T ambient temperature - u ₁ dimensionless characteristic velocity,Gr ^–1/2(U₁ L/) - U velocity in theX direction - U ₁ dimensional characteristic velocity,U ₁=U/f(Y/GD) - V velocity in theY direction - W _k weighting functions, see equation (5) - X distance along plate - x dimensionless distance along plate,X/L - x increment onx for method of lines - Y distance from plate - y dimensionless distance from plate,Y/L - thermal diffusivity - coefficient of thermal expansion - dimensional boundary layer thickness - dimensionless boundary layer thickness, /L - a function of - dimensionless length,Y/ - temperature excess, (T-T) - _w wall temperature difference, (T _w–T) - _k approximating functions, see equation (4) - kinematic viscosity - dimensionless time,Gr ^–1/2( _t /L ²) - approximating functions, see equation (4) Work performed under the auspices of the U.S. Atomic Energy Commission.