A local 2-approximation algorithm for the vertex cover problem

We present a distributed 2-approximation algorithm for the minimum vertex cover problem. The algorithm is deterministic, and it runs in (Δ + 1)2 synchronous communication rounds, where Δ is the maximum degree of the graph. For Δ = 3, we give a 2-approximation algorithm also for the weighted version of the problem.

A local 2-approximation algorithm for the vertex cover problem

We present a distributed 2-approximation algorithm for the minimum vertex cover problem. The algorithm is deterministic, and it runs in (Δ + 1)2 synchronous communication rounds, where Δ is the maximum degree of the graph. For Δ = 3, we give a 2-approximation algorithm also for the weighted version of the problem.

A Direct Approach to the Problem of Diffraction by a Half-Plane under Mixed Boundary Conditions

A general direct technique of solving a mixed boundary value problem in the theory of diffraction by a semi-infinite plane is presented. Taking account of the correct edge-conditions, the unique solution of the problem is derived, by means of Jones' method in the theory of Wiener-Hopf technique, in the case of incident plane wave. The solution of the half-plane problem is found out in exact form. (The far-field is derived by the method of steepest descent.) It is observed that it is not the Wiener-Hopf technique which really needs any modification but a new technique is certainly required to handle the peculiar type of coupled integral equations which the Wiener-Hopf technique leads to. Eine allgemeine direkte Technik zur Lösung eines gemischten Randwertproblems in der Theorie der Beugung an einer halbunendlichen Ebene wird vorgestellt. Unter Berücksichtigung der korrekten Eckbedingungen wird mit der Methode von Jones aus der Theorie der Wiener-Hopf-Technik die eindeutige Lösung für den Fall der einfallenden ebenen Welle hergeleitet. Die Lösung des Halbebenenproblems wird in exakter Form angegeben. (Das Fernfeld wurde mit der Methode des steilsten Abstiegs bestimmt.) Es wurde bemerkt, daß es nicht die Wiener-Hopf-Technik ist, die wirklich irgend welcher Modifikationen bedurfte. Gewiß aber wird eine neue Technik zur Behandlung des besonderen Typs gekoppelter Integralgleichungen benötigt, auf die die Wiener-Hopf-Technik führt.

Inverse problem for the wave equation : partial data and novel boundary sources

An inverse problem for the wave equation is a mathematical formulation of the problem to convert measurements of sound waves to information about the wave speed governing the propagation of the waves. This doctoral thesis extends the theory on the inverse problems for the wave equation in cases with partial measurement data and also considers detection of discontinuous interfaces in the wave speed. A possible application of the theory is obstetric sonography in which ultrasound measurements are transformed into an image of the fetus in its mother's uterus. The wave speed inside the body can not be directly observed but sound waves can be produced outside the body and their echoes from the body can be recorded. The present work contains five research articles. In the first and the fifth articles we show that it is possible to determine the wave speed uniquely by using far apart sound sources and receivers. This extends a previously known result which requires the sound waves to be produced and recorded in the same place. Our result is motivated by a possible application to reflection seismology which seeks to create an image of the Earth s crust from recording of echoes stimulated for example by explosions. For this purpose, the receivers can not typically lie near the powerful sound sources. In the second article we present a sound source that allows us to recover many essential features of the wave speed from the echo produced by the source. Moreover, these features are known to determine the wave speed under certain geometric assumptions. Previously known results permitted the same features to be recovered only by sequential measurement of echoes produced by multiple different sources. The reduced number of measurements could increase the number possible applications of acoustic probing. In the third and fourth articles we develop an acoustic probing method to locate discontinuous interfaces in the wave speed. These interfaces typically correspond to interfaces between different materials and their locations are of interest in many applications. There are many previous approaches to this problem but none of them exploits sound sources varying freely in time. Our use of more variable sources could allow more robust implementation of the probing.

Vehicle Routing Problem with Load Compatibility Constraints

The major contribution of this paper is to introduce load compatibility constraints in the mathematical model for the capacitated vehicle routing problem with pickup and deliveries. The employee transportation problem in the Indian call centers and transportation of hazardous materials provided the motivation for this variation. In this paper we develop a integer programming model for the vehicle routing problem with load compatibility constraints. Specifically two types of load compatability constraints are introduced, namely mutual exclusion and conditional exclusion. The model is demonstrated with an application from the employee transportation problem in the Indian call centers.

Neural network approach for the two-dimensional assignment problem

A neural network approach for solving the two-dimensional assignment problem is proposed. The design of the neural network is discussed and simulation results are presented. The neural network obtains 10-15% lower cost placements on the examples considered, than the adjacent pairwise exchange method.

A New Approach to the Problem of Scattering of Water Waves by Vertical Barriers

Using a modified Green's function technique the two well-known basic problems of scattering of surface water waves by vertical barriers are reduced to the problem of solving a pair of uncoupled integral equations involving the “jump” and “sum” of the limiting values of the velocity potential on the two sides of the barriers in each case. These integral equations are then solved, in closed form, by the aid of an integral transform technique involving a general trigonometric kernel as applicable to the problems associated with a radiation condition.

Dynamical Resolution of Redundancy for Robot Manipulators

A large class of work in the robot manipulator literature deals with the kinematical resolution of redundancy based on the pseudo-inverse of the manipulator Jacobian. In this paper an alternative dynamical approach to redundancy resolution is developed which utilizes the mapping between the actuator torques and the acceleration of the end-effector, at a given dynamic state of the manipulator. The potential advantages of the approach are discussed and an example of a planar 3R manipulator following a circular end-effector trajectory is used to illustrate the proposed approach as well as to compare it with the more well-known approach based on the pseudo-inverse.

The shear dynamo problem for small magnetic Reynolds numbers

We study large-scale kinematic dynamo action due to turbulence in the presence of a linear shear flow in the low-conductivity limit. Our treatment is non-perturbative in the shear strength and makes systematic use of both the shearing coordinate transformation and the Galilean invariance of the linear shear flow. The velocity fluctuations are assumed to have low magnetic Reynolds number (Re-m), but could have arbitrary fluid Reynolds number. The equation for the magnetic fluctuations is expanded perturbatively in the small quantity, Re-m. Our principal results are as follows: (i) the magnetic fluctuations are determined to the lowest order in Rem by explicit calculation of the resistive Green's function for the linear shear flow; (ii) the mean electromotive force is then calculated and an integro-differential equation is derived for the time evolution of the mean magnetic field. In this equation, velocity fluctuations contribute to two different kinds of terms, the 'C' and 'D' terms, respectively, in which first and second spatial derivatives of the mean magnetic field, respectively, appear inside the space-time integrals; (iii) the contribution of the D term is such that its contribution to the time evolution of the cross-shear components of the mean field does not depend on any other components except itself. Therefore, to the lowest order in Re-m, but to all orders in the shear strength, the D term cannot give rise to a shear-current-assisted dynamo effect; (iv) casting the integro-differential equation in Fourier space, we show that the normal modes of the theory are a set of shearing waves, labelled by their sheared wavevectors; (v) the integral kernels are expressed in terms of the velocity-spectrum tensor, which is the fundamental dynamical quantity that needs to be specified to complete the integro-differential equation description of the time evolution of the mean magnetic field; (vi) the C term couples different components of the mean magnetic field, so they can, in principle, give rise to a shear-current-type effect. We discuss the application to a slowly varying magnetic field, where it can be shown that forced non-helical velocity dynamics at low fluid Reynolds number does not result in a shear-current-assisted dynamo effect.

Maximum-entropy calculation of the electron density at 4 A resolution of Pf1 filamentous bacteriophage

A 4 A electron-density map of Pf1 filamentous bacterial virus has been calculated from x-ray fiber diffraction data by using the maximum-entropy method. This method produces a map that is free of features due to noise in the data and enables incomplete isomorphous-derivative phase information to be supplemented by information about the nature of the solution. The map shows gently curved (banana-shaped) rods of density about 70 A long, oriented roughly parallel to the virion axis but slewing by about 1/6th turn while running from a radius of 28 A to one of 13 A. Within these rods, there is a helical periodicity with a pitch of 5 to 6 A. We interpret these rods to be the helical subunits of the virion. The position of strongly diffracted intensity on the x-ray fiber pattern shows that the basic helix of the virion is right handed and that neighboring nearly parallel protein helices cross one another in an unusual negative sense.

Structural refinement using high-resolution powder X-ray diffraction data of Ca0.5Ti2P3O12, a low-thermal-expansion material

The structures of Ca0.5Ti2P3O12 and Sr0.5Ti2P3O12, low-thermal-expansion materials, have been refined by the Rietveld method using high-resolution powder X-ray diffraction (XRD) data. The assignment of space group R[3 with combining macron] to NASICON-type compounds containing divalent cations is confirmed. 31P magic-angle spinning nuclear magnetic resonance (MASNMR) data are presented as supporting data. A comparison of changes in the polyhedral network resulting from the cation distribution, is made with NaTi2P3O12 and Nb2P3O12. Factors that may govern thermal expansion in this family of compounds are discussed.

Structure of Sesbania Mosaic Virus at 4·7 Å Resolution and Partial Sequence of the Coat Protein

Sesbania mosaic virus (SMV) is a plant virus infecting Sesbania grandiflora plants in Andhra Pradesh, India. Amino acid sequence of the tryptic peptides of SMV coat protein were determined using a gas phase sequenator. These sequences showed identical amino acids at 69% of the positions when aligned with the corresponding residues of southern bean mosaic virus (SBMV).Crystals diffracting to better than 3 Å resolution were obtained by precipitating the virus with ammonium sulphate. The crystals belonged to rhombohedral space group R3 with α = 291·4 Å and α = 61·9°. Three-dimensional X-ray diffraction data on these crystals were collected to a resolution of 4·7 Å, using a Siemens-Nicolet area detector system. Self-rotation function studies revealed the icosahedral symmetry of the virus particles, as well as their precise orientation in the unit cell. Cross-rotation function and modelling studies with SBMV showed that it is a valid starting model for SMV structure determination. Low resolution phases computed using a polyalanine model of SBMV were subjected to refinement and extension by real-space electron density averaging and solvent flattening. The final electron density map revealed a polypeptide fold similar to SBMV. The single disulphide bridge of SBMV coat protein is retained in SMV. Four icosahedrally independent cation binding sites have been tentatively identified. Three of these sites, related by a quasi threefold axis, are also found in SBMV. The fourth site is situated on the quasi threefold axis. Aspartic acid residues, which replace Ile218 of SBMV from the quasi threefold-related subunits are suitable ligands to the cation at this site

A Feature-Based Solution to Forward Problem in Electrical Capacitance Tomography of Conductive Materials

A new feature-based technique is introduced to solve the nonlinear forward problem (FP) of the electrical capacitance tomography with the target application of monitoring the metal fill profile in the lost foam casting process. The new technique is based on combining a linear solution to the FP and a correction factor (CF). The CF is estimated using an artificial neural network (ANN) trained using key features extracted from the metal distribution. The CF adjusts the linear solution of the FP to account for the nonlinear effects caused by the shielding effects of the metal. This approach shows promising results and avoids the curse of dimensionality through the use of features and not the actual metal distribution to train the ANN. The ANN is trained using nine features extracted from the metal distributions as input. The expected sensors readings are generated using ANSYS software. The performance of the ANN for the training and testing data was satisfactory, with an average root-mean-square error equal to 2.2%.