An approximation algorithm for the generalized assignment problem

The generalized assignment problem can be viewed as the following problem of scheduling parallel machines with costs. Each job is to be processed by exactly one machine; processing jobj on machinei requires timep _ij and incurs a cost ofc _ij ; each machinei is available forT _i time units, and the objective is to minimize the total cost incurred. Our main result is as follows. There is a polynomial-time algorithm that, given a valueC, either proves that no feasible schedule of costC exists, or else finds a schedule of cost at mostC where each machinei is used for at most 2T _i time units.We also extend this result to a variant of the problem where, instead of a fixed processing timep _ij , there is a range of possible processing times for each machine—job pair, and the cost linearly increases as the processing time decreases. We show that these results imply a polynomial-time 2-approximation algorithm to minimize a weighted sum of the cost and the makespan, i.e., the maximum job completion time. We also consider the objective of minimizing the mean job completion time. We show that there is a polynomial-time algorithm that, given valuesM andT, either proves that no schedule of mean job completion timeM and makespanT exists, or else finds a schedule of mean job completion time at mostM and makespan at most 2T. Research partially supported by an NSF PYI award CCR-89-96272 with matching support from UPS, and Sun Microsystems, and by the National Science Foundation, the Air Force Office of Scientific Research, and the Office of Naval Research, through NSF grant DMS-8920550.Research supported in part by a Packard Fellowship, a Sloan Fellowship, an NSF PYI award, and by the National Science Foundation, the Air Force Office of Scientific Research, and the Office of Naval Research, through NSF grant DMS-8920550.     

任意长—维DFT的MIMD并行算法

本文提出了共享与分布式存储计算机上任意长—维ＤＦＴ的ＭＩＭＤ并行算法，若Ｎ＝Ｏ（ｐ，ｑ），则算法需要次算术运算。其中，Ｐ与Ｎ可为任意自然数，分别表示处理机台数与ＤＦＴ长度．本文算法具有很高的并行效率．     

Theoretical studies on microscopic and macroscopic nonuniformities in electric-discharge-excited XeCl lasers

The satbilit r of the pumping discharge for XeCI (Ne/Xe/HCI) lasers is investigated by using different one-dimensional models, considering both bulk discharge instabilities and filamentary ones. It is found that the bulk stability in a XeCl laser discharge can he improved, under certain conditions, due to the vihrational excitation of HCl molecules: this effect is studied by using different models for the HCl vihrational kinetics. It is established that the very short instability time found in experiments cannot he explained as a result of hulk instability of the discharge. On the other hand, a satisfactory comparison with experiments can he obtained by adding to the model a simplified microinstability which develops in the discharge.     

Time-stepping algorithms for semidiscretized linear parabolic PDEs based on rational approximants with distinct real poles

Time dependent problems in Partial Differential Equations (PDEs) are often solved by the Method Of Lines (MOL). For linear parabolic PDEs, the exact solution of the resulting system of first order Ordinary Differential Equations (ODEs) satisfies a recurrence relation involving the matrix exponential function. In this paper, we consider the development of a fourth order rational approximant to the matrix exponential function possessing real and distinct poles which, consequently, readily admits a partial fraction expansion, thereby allowing the distribution of the work in solving the corresponding linear algebraic systems in essentially Backward Euler-like solves on concurrent processors. The resulting parallel algorithm possesses appropriate stability properties, and is implemented on various parabolic PDEs from the literature including the forced heat equation and the advection-diffusion equation.Dedicated to Professor J. Crank on the occasion of his 80th birthday     

On a modification of the Clenshaw-Curtis quadrature formula

In this paper we discuss a modification of the Clenshaw-Curtis quadrature formula. It is shown that for integrals, where the integrand may be expanded in a sufficiently rapid convergent Chebyshev series, we may split the sequence of calculated approximations into two sequences, one which approximates the integral from above and one which approximates it from below. Thus, at any step during the calculation we obtain both upper and lower bounds for the true value of the integral.Work performed while the author was working as a visiting scientist at CERN/Geneve.     

Experiments with a symbolic programming system for complex analysis

The paper reports the results of work on the construction of LISP programs for various symbolic operations in complex analysis, including the evaluation of integrals around closed contours by the use of Cauchy's Theorem. It is concluded that the only difficulty in the way of the preparation of programs for all of the important and useful textbook calculations in complex analysis is that large amounts of fast storage in the computer are needed.     

A parallel variable-metric dynamic programming algorithm

This paper presents a potentially parallel iterative algorithm for the solution of the unconstrainedN-stage decision problem of dynamic programming. The basis of the algorithm is the use of variable-metric minimization techniques to develop a quadratic approximation to the cost function at each stage. The algorithm is applied to various problems, and comparisons with other algorithms are made.This research forms part of the author's PhD program, and is supported by the Department of Scientific and Industrial Research of the New Zealand Government. The author is indebted to Dr. B. A. Murtagh, PhD supervisor, for his encouragement and support during the preparation of this paper.     

Quantum-chemical study of the interface formed by carboxylic species on TiO<Subscript>2</Subscript> nanoparticles. 1. Nanoparticle surface

The current paper presents results of a quantum-chemical study of the surface structure of nanoparticles of both rutile and anatase crystallographic modifications. Different stages of the surface relaxation are discussed. Water adsorption is considered. The calculations were performed in the spd-basis by using semi-empirical quantum-chemical codes, both sequential and parallel. The results are mainly addressed to the study of the interface formed by titania nanoparticles and a set of carboxylated species, namely, benzoic, bi-isonicotinic acids as well as tris-(2,2′-dcbipyridine) Fe(II) complex placed on the surface of either rutile or anatase polymorphs.This revised version was published online in August 2005 with a corrected issue number.     

A structurally diverse heterocyclic library: A benzothiazepine-fused β -lactam library derived from reaction of 2,3-dihydro-1,5-benzothiazepines and acyl chlorides: Synthesis and stereochemistry

A 1H-azeto[2,1-d][1,5]benzothiazepin-1-one, -lactam derivatives of dihydrobenzothiazepines library derived from reactions of 2,4-disubstituted 2,3-dihydro-1,5-benzothiazepines and acyl chlorides, including phthalimidoacetyl chloride, chloroacetyl chloride, dichloroacetyl chloride and phenoxyacetyl chloride, was built up through parallel solution-phase synthesis. Stereochemistry of 1H-azeto[2,1-d][1,5]benzothiazepin-1-ones in the reaction process is discussed.     

Parallel Calculation of Accurate Path Lines in Virtual Environments through Exploitation of Multi-Block CFD Data Set Topology

The use of Virtual Reality (VR) techniques for the investigation of complex flow phenomena offers distinct advantages in comparison to conventional visualization techniques. Especially for unsteady flows, VR methodology provides an intuitive approach for the exploration of simulated fluid flows. However, the visualization of Computational Fluid Dynamics (CFD) data is often too time-consuming to be carried out in real-time, and thus violates essential constraints concerning real-time interaction and visualization. To overcome this obstacle, we make use of the fact that typically a multi-block approach is employed for domain decomposition, and we use the corresponding data structures for the computation of path lines and for parallelization. In this paper, we present the synthesis of fragmented multi-block data sets and our implementation of an accurate path line integration scheme in order to speed up path line computations. We report on the results of our efforts and describe a combination of this algorithm with a highly efficient visualization approach of large amounts of particle traces, thus considerably improving interactivity when exploring large scale CFD data sets.Mathematics Subject Classifications (2000) 76Mxx, 76M27, 76M28, 65M55, 65L05, 65L06, 65D05, 65Y05, 68U05.