Approximation Algorithms for a Symmetric Quadratic Knapsack Problem and its Scheduling Applications

We consider a knapsack problem to minimize a symmetric quadratic function. We demonstrate that this symmetric quadratic knapsack problem is relevant to two problems of single machine scheduling: the problem of minimizing the weighted sum of the completion times with a single machine non-availability interval under the non-resumable scenario; and the problem of minimizing the total weighted earliness and tardiness with respect to a common small due date. We develop a polynomial-time approximation algorithm that delivers a constant worst-case performance ratio for a special form of the symmetric quadratic knapsack problem. We adapt that algorithm to our scheduling problems and achieve a better performance. For the problems under consideration no fixed-ratio approximation algorithms have been previously known.

Multiple-locus sequence typing analysis of Bacillus thuringiensis recovered from the phylloplane of clover (Trifolium hybridum) in vegetative form

The chromosomal genotype, as judged by multi locus sequence typing, and the episomal genotype, as judged by plasmid profile and cry gene content, were analyzed for a collection of strains of Bacillus thuringiensis. These had been recovered in vegetative form over a period of several months from the leaves of a small plot of clover (Trifolium hybridum). A clonal population structure was indicated, although greater variation in sequence types (STs) was discovered than in previous collections of B. cereus/B. thuringiensis. Isolates taken at the same time had quite different genotypes, whereas those of identical genotypes were recovered at different times. The profiles of plasmid content and cry genes generally bore no relation to each other nor to the STs. Evidently, although relatively little recombination was occurring in the seven chromosomal genes analyzed, a great deal of conjugal transfer, and perhaps recombination, was occurring involving plasmids. A clinical diarrheal isolate of B. cereus and the commercial biopesticide strain HD-1 of B. thuringiensis, both included as out-groups, were found to have very similar STs. This further emphasizes the role of episomal elements in the characteristics and differentiation of these two species.

Recovery of Bacillus thuringiensis in vegetative form from the phylloplane of clover (Trifolium hybridum) during a growing season

Two media were developed which specifically allow the cultivation of Bacillus thuringiensis while it is in the vegetative as opposed to the spore form. Using these media B. thuringiensis was shown conclusively for the first time to exist in an active form on the phylloplane. The profile of its appearance in vegetative and spore form was followed over a growing season on clover (Trifolium hybridum) in the field. Three simultaneous and sudden rises and declines of both spore and vegetative cell densities were observed. The most common other spore-former on these leaves was Bacillus cereus but the fluctuations in appearance of these two very closely related species were not co-incident. Using specific PCR primers a considerable diversity of cry toxin gene types was found in isolates that had been recovered in vegetative form ([`]vegetative isolates') with the majority possessing multiple [delta]-endotoxin genes while some had only one of those tested. Bioassays against a lepidopteran insect of purified [delta]-endotoxins showed that they were no more potent than those from a laboratory-adapted strain. PCR primers for an internal region of the vip3A gene produced amplification in 70% of the vegetative isolates compared to 25% of the laboratory-adapted strains tested.