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.

A higher order Hopfield network for vector quantisation

A higher order version of the Hopfield neural network is presented which will perform a simple vector quantisation or clustering function. This model requires no penalty terms to impose constraints in the Hopfield energy, in contrast to the usual one where the energy involves only terms quadratic in the state vector. The energy function is shown to have no local minima within the unit hypercube of the state vector so the network only converges to valid final states. Optimisation trials show that the network can consistently find optimal clusterings for small, trial problems and near optimal ones for a large data set consisting of the intensity values from the digitised, grey-level image.

Issues in delivering multimedia content to mobile devices

The scalability of a computer system is its response to growth. It is also depended on its hardware, its operating system and the applications it is running. Most distributed systems technology today still depends on bus-based shared memory which do not scale well, and systems based on the grid or hypercube scheme requires significantly less connections than a full inter-connection that would exhibit a quadratic growth rate. The rapid convergence of mobile communication, digital broadcasting and network infrastructures calls for rich multimedia content that is adaptive and responsive to the needs of individuals, businesses and the public organisations. This paper will discuss the emergence of mobile Multimedia systems and provides an overview of the issues regarding design and delivery of multimedia content to mobile devices.

Optimizing the reliability of power electronics module isolation substrates

Optimal design of a power electronics module isolation substrate is assessed using a combination of finite element structural mechanics analysis and response surface optimisation technique. Primary failure modes in power electronics modules include the loss of structural integrity in the ceramic substrate materials due to stresses induced through thermal cycling. Analysis of the influence of ceramic substrate design parameters is undertaken using a design of experiments approach. Finite element analysis is used to determine the stress distribution for each design, and the results are used to construct a quadratic response surface function. A particle swarm optimisation algorithm is then used to determine the optimal substrate design. Analysis of response surface function gradients is used to perform sensitivity analysis and develop isolation substrate design rules. The influence of design uncertainties introduced through manufacturing tolerances is assessed using a Monte-Carlo algorithm, resulting in a stress distribution histogram. The probability of failure caused by the violation of design constraints has been analyzed. Six geometric design parameters are considered in this work and the most important design parameters have been identified. Overall analysis results can be used to enhance the design and reliability of the component.