Hardness of approximation results for the problem of finding the stopping distance in Tanner graphs

Tanner Graph representation of linear block codes is widely used by iterative decoding algorithms for recovering data transmitted across a noisy communication channel from errors and erasures introduced by the channel. The stopping distance of a Tanner graph T for a binary linear block code C determines the number of erasures correctable using iterative decoding on the Tanner graph T when data is transmitted across a binary erasure channel using the code C. We show that the problem of finding the stopping distance of a Tanner graph is hard to approximate within any positive constant approximation ratio in polynomial time unless P = NP. It is also shown as a consequence that there can be no approximation algorithm for the problem achieving an approximation ratio of 2(log n)(1-epsilon) for any epsilon > 0 unless NP subset of DTIME(n(poly(log n))).

Protein sequence design on the basis of topology optimization techniques -Using continuous modeling of discrete amino acid types

The notion of optimization is inherent in protein design. A long linear chain of twenty types of amino acid residues are known to fold to a 3-D conformation that minimizes the combined inter-residue energy interactions. There are two distinct protein design problems, viz. predicting the folded structure from a given sequence of amino acid monomers (folding problem) and determining a sequence for a given folded structure (inverse folding problem). These two problems have much similarity to engineering structural analysis and structural optimization problems respectively. In the folding problem, a protein chain with a given sequence folds to a conformation, called a native state, which has a unique global minimum energy value when compared to all other unfolded conformations. This involves a search in the conformation space. This is somewhat akin to the principle of minimum potential energy that determines the deformed static equilibrium configuration of an elastic structure of given topology, shape, and size that is subjected to certain boundary conditions. In the inverse-folding problem, one has to design a sequence with some objectives (having a specific feature of the folded structure, docking with another protein, etc.) and constraints (sequence being fixed in some portion, a particular composition of amino acid types, etc.) while obtaining a sequence that would fold to the desired conformation satisfying the criteria of folding. This requires a search in the sequence space. This is similar to structural optimization in the design-variable space wherein a certain feature of structural response is optimized subject to some constraints while satisfying the governing static or dynamic equilibrium equations. Based on this similarity, in this work we apply the topology optimization methods to protein design, discuss modeling issues and present some initial results.

Component Inventory Costs in an Assembly Problem with Uncertain Supplier Lead-Times

We present a generic study of inventory costs in a factory stockroom that supplies component parts to an assembly line. Specifically, we are concerned with the increase in component inventories due to uncertainty in supplier lead-times, and the fact that several different components must be present before assembly can begin. It is assumed that the suppliers of the various components are independent, that the suppliers' operations are in statistical equilibrium, and that the same amount of each type of component is demanded by the assembly line each time a new assembly cycle is scheduled to begin. We use, as a measure of inventory cost, the expected time for which an order of components must be held in the stockroom from the time it is delivered until the time it is consumed by the assembly line. Our work reveals the effects of supplier lead-time variability, the number of different types of components, and their desired service levels, on the inventory cost. In addition, under the assumptions that inventory holding costs and the cost of delaying assembly are linear in time, we study optimal ordering policies and present an interesting characterization that is independent of the supplier lead-time distributions.

A note on the porous-wavemaker problem

A complete analytical solution is obtained, by using an integral transform method, for the porous-wavemaker problem, when the effect of surface tension is taken into account on the free surface of water of finite-depth in which surface waves are produced by small horizontal oscillations of a porous vertical plate. The final results are expressed in the form of convergent integrals as well as series and known results are reproduced when surface tension is neglected.

Adaptive dendron: A bile acid oligomer behaving as both normal and inverse micellar mimic

The normal and inverse micellar property of a bile-acid-based dendritic structure was established through dye solubilization studies in both polar and nonpolar media.

Analysis of clearance fit pin joints

The analysis of clearance fit joints falls within the realm of mixed boundary problems with moving boundaries. In this paper, this problem is solved by a simple continuum method of analysis applying an inverse technique; the region of contact is specified and the corresponding causative load is evaluated. Illustrations are given for a rigid clearance fit pin in a large elastic plate with smooth zero-shear interface between pin and plate, under biaxial plate stress at infinity and due to load transfer through pin.

A matrix identity and perturbation expressions

An identity expressing formally the diagonal and off-diagonal elements of an inverse of a matrix is deduced employing operator techniques. Several well-known perturbation expressions for the self-energy are deduced as special cases. A new approximation and other applications following from the above formalism are briefly indicated through illustrations from a perturbed harmonic oscillator, chemisorption approximations and Kelly's result in the problem of electron correlation.

Composite signal decomposition by digital inverse filtering

Inverse filters are conventionally used for resolving overlapping signals of identical waveshape. However, the inverse filtering approach is shown to be useful for resolving overlapping signals, identical or otherwise, of unknown waveshapes. Digital inverse filter design based on autocorrelation formulation of linear prediction is known to perform optimum spectral flattening of the input signal for which the filter is designed. This property of the inverse filter is used to accomplish composite signal decomposition. The theory has been presented assuming constituent signals to be responses of all-pole filters. However, the approach may be used for a general situation.

Steady compressible flow of granular materials through a wedge-shaped hopper: The smooth wall, radial gravity problem

A continuum model based on the critical state theory of soil mechanics is used to generate stress and density profiles, and to compute discharge velocities for the plane flow of cohesionless materials. Two types of yield loci are employed, namely, a yield locus with a corner, and a smooth yield locus. The yield locus with a corner leads to computational difficulties. For the smooth yield locus, results are found to be relatively insensitive to the shape of the yield locus, the location of the upper traction-free surface and the density specified on this surface. This insensitivity arises from the existence of asymptotic stress and density fields, to which the solution tends to converge on moving down the hopper. Numerical and approximate analytical solutions are obtained for these fields and the latter is used to derive an expression for the discharge velocity. This relation predicts discharge velocities to within 13% of the exact (numerical) values. While the assumption of incompressibility has been frequently used in the literature, it is shown here that in some cases, this leads to discharge velocities which are significantly higher than those obtained by the incorporation of density variation.

An integer arithmetic method to compute generalized matrix inverse and solve linear equations exactly

An algorithm that uses integer arithmetic is suggested. It transforms anm ×n matrix to a diagonal form (of the structure of Smith Normal Form). Then it computes a reflexive generalized inverse of the matrix exactly and hence solves a system of linear equations error-free.

On the Fekete-Szego problem for concave univalent functions

We consider the Fekete-Szego problem with real parameter lambda for the class Co(alpha) of concave univalent functions. (C) 2010 Elsevier Inc. All rights reserved.

Uniformly valid analytical solution to the problem of a decaying shock wave

An explicit representation of an analytical solution to the problem of decay of a plane shock wave of arbitrary strength is proposed. The solution satisfies the basic equations exactly. The approximation lies in the (approximate) satisfaction of two of the Rankine-Hugoniot conditions. The error incurred is shown to be very small even for strong shocks. This solution analyses the interaction of a shock of arbitrary strength with a centred simple wave overtaking it, and describes a complete history of decay with a remarkable accuracy even for strong shocks. For a weak shock, the limiting law of motion obtained from the solution is shown to be in complete agreement with the Friedrichs theory. The propagation law of the non-uniform shock wave is determined, and the equations for shock and particle paths in the (x, t)-plane are obtained. The analytic solution presented here is uniformly valid for the entire flow field behind the decaying shock wave.