Improved Bounds for Acyclic Job Shop Scheduling

In acyclic job shop scheduling problems there are n jobs and m machines. Each job is composed of a sequence of operations to be performed on different machines. A legal schedule is one in which within each job, operations are carried out in order, and each machine performs at most one operation in any unit of time. If D denotes the length of the longest job, and C denotes the number of time units requested by all jobs on the most loaded machine, then clearly lb = max[C,D] is a lower bound on the length of the shortest legal schedule. A celebrated result of Leighton, Maggs, and Rao shows that if all operations are of unit length, then there always is a legal schedule of length O(lb), independent of n and m. For the case that operations may have different lengths, Shmoys, Stein and Wein showed that there always is a legal schedule of length , where the notation is used to suppress terms. We improve the upper bound to . We also show that our new upper bound is essentially best possible, by proving the existence of instances of acyclic job shop scheduling for which the shortest legal schedule is of length . This resolves (negatively) a known open problem of whether the linear upper bound of Leighton, Maggs, and Rao applies to arbitrary job shop scheduling instances (without the restriction to acyclicity and unit length operations). Received June 30, 1998 RID="*" ID="*" Incumbent of the Joseph and Celia Reskin Career Development Chair RID="†" ID="†" Research was done while staying at the Weizmann Institute, supported by a scholarship from the Minerva foundation.     

Pompeiu sets in compact Heisenberg manifolds

A necessary and sufficient condition is presented for a set to be a Pompeiu subset of any compact homogeneous space with a finite invariant measure. The condition, which is expressed in terms of the intertwining operators of each primary summand of the quasi-regular representation, is then interpreted in the case of the compact Heisenberg manifolds. Examples are presented demonstrating that the condition to be Pompeiu in these manifolds is quite different from the corresponding condition for a torus of the same dimension. This provides a contrast with the existing comparison between the Heisenberg group itself and Euclidean space in terms of Pompeiu sets. In addition, the closed linear span of all translates of any square integrable function on any compact homogeneous space is determined.     

Some recent results in metric fixed point theory

This is a survey of recent results on best approximation and fixed point theory in certain geodesic spaces. Some of these results are related to fundamental fixed point theorems in topology that have been known for many years. However the metric approach is emphasized here. Dedicated to Edward Fadell and Albrecht Dold on the occasion of their 80th birthdays     

PRIME IDEALS IN RINGS WITH INVOLUTION

Abstract

Let R be a ring with involution *. We show that if R is a *-prime ring which is not a prime ring, then R is “essentially” a direct product of two prime rings. Moreover, if P is a *-prime *-ideal of R, which is not a prime ideal of R, and X is minimal among prime ideals of R containing P, then P is a prime ideal of X, P = X ∩ X* and either: (1) P is essential in X and X is essential in R; or (2) for any relative complement C of P in X, then C* is a relative complement of X in R. Further characterizations of *-primeness are provided.     

Multiple solutions of semilinear degenerate elliptic boundary value problems

The purpose of this paper is to study a class of semilinear elliptic boundary value problems with degenerate boundary conditions which include as particular cases the Dirichlet problem and the Robin problem. The approach here is based on the super‐sub‐solution method in the degenerate case, and is distinguished by the extensive use of an L^p Schauder theory elaborated for second‐order, elliptic differential operators with discontinuous zero‐th order term. By using Schauder's fixed point theorem, we prove that the existence of an ordered pair of sub‐ and supersolutions of our problem implies the existence of a solution of the problem. The results extend an earlier theorem due to Kazdan and Warner to the degenerate case. © 2011 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim     

A multiplicity result for periodic solutions of second order differential equations with a singularity

By the use of the Poincaré–Birkhoff fixed point theorem, we prove a multiplicity result for periodic solutions of a second order differential equation, where the nonlinearity exhibits a singularity of repulsive type at the origin and has linear growth at infinity. Our main theorem is related to previous results by Rebelo (1996, 1997)  and  and Rebelo and Zanolin (1996)  and , in connection with a problem raised by del Pino et al. (1992) [1].     

Random strict convexity and random uniform convexity in random normed modules

Based on the analysis of stratification structure on random normed modules, we first present random strict convexity and random uniform convexity in random normed modules. Then, we establish their respective relations to classical strict and uniform convexity: in the process some known important results concerning strict convexity and uniform convexity of Lebesgue-Bochner function spaces can be obtained as a special case of our results. Further, we also give their important applications to the theory of random conjugate spaces as well as best approximation. Finally, we conclude this paper with some remarks showing that the study of geometry of random normed modules will also motivate the further study of geometry of probabilistic normed spaces.