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))).

On the hardness and elastic modulus of bulk metallic glass matrix composites

The influences of the amorphous matrix and crystalline dendrite phases on the hardness and elastic moduli of Zr/Ti-based bulk metallic glass matrix composites have been assessed. While the moduli of the composites correspond to those predicted by the rule of mixtures, the hardness of the composites is similar to that of the matrix, suggesting that the plastic flow in the composites under constrained conditions such as indentation is controlled by the flow resistance of the contiguous matrix. (C) 2010 Acta Materialia Inc. Published by Elsevier Ltd. All rights reserved.

The hardness of approximating the boxicity, cubicity and threshold dimension of a graph

A k-dimensional box is the Cartesian product R-1 X R-2 X ... X R-k where each R-i is a closed interval on the real line. The boxicity of a graph G, denoted as box(G), is the minimum integer k such that G can be represented as the intersection graph of a collection of k-dimensional boxes. A unit cube in k-dimensional space or a k-cube is defined as the Cartesian product R-1 X R-2 X ... X R-k where each R-i is a closed interval oil the real line of the form a(i), a(i) + 1]. The cubicity of G, denoted as cub(G), is the minimum integer k such that G can be represented as the intersection graph of a collection of k-cubes. The threshold dimension of a graph G(V, E) is the smallest integer k such that E can be covered by k threshold spanning subgraphs of G. In this paper we will show that there exists no polynomial-time algorithm for approximating the threshold dimension of a graph on n vertices with a factor of O(n(0.5-epsilon)) for any epsilon > 0 unless NP = ZPP. From this result we will show that there exists no polynomial-time algorithm for approximating the boxicity and the cubicity of a graph on n vertices with factor O(n(0.5-epsilon)) for any epsilon > 0 unless NP = ZPP. In fact all these hardness results hold even for a highly structured class of graphs, namely the split graphs. We will also show that it is NP-complete to determine whether a given split graph has boxicity at most 3. (C) 2010 Elsevier B.V. All rights reserved.

The influence of chemical additives on surface charge and hardness of hematite

The zeta potential of high-purity hematite at pH 6 and in a 10−3N NaCl solution has been determined at different concentrations of acetone using the streaming potential technique and the results correlated with the microhardness of the mineral. The zeta potential has been found to decrease as the hardness increases reaching a minimum at 10 cc per litre concentration of acetone when the hardness reaches a maximum. The results have been explained on the basis of competitive adsorption of chloride ions and acetone molecules at low concentrations of acetone and coadsorption of both species above 10 cc per litre concentration. Acetone in distilled water and 10−3N NaCl in distilled water decrease the microhardness of hematite individually between pH 5 to 7 and in combination increase the microhardness reaching a maximum at pH 6.

Effect of microstructure and hardness on the grinding abrasive wear resistance of a ball bearing steel

Grinding media wear appears to be non-linear with the time of grinding in a laboratory-scale ball mill. The kinetics of wear can be expressed as a power law of the type w=atb, where the numerical constant a represents wear of a particular microstructure at time t = 1 min and b is the wear exponent which is independent of the particle size prevailing inside a ball mill at any instant of time of grinding. The wear exponent appears to be an indicator of the cutting wear mechanism in dry grinding: a plot of the inverse of the normalised wear exponent (Image ) versusHs (where Hs is the worn surface hardness of the media) yields a curve similar to that of a wear resistance plot obtained in the case of two-body sliding abrasive wear. This method of evaluating the cutting wear resistance of media is demonstrated by employing 15 different microstructures of AISI-SAE 52100 steel balls in dry grinding of quartz in a laboratory-scale ball mill.

Role of Surface Texture, Roughness, and Hardness on Friction During Unidirectional Sliding

In the present investigation, experiments were conducted by unidirectional sliding of pins made of FCC metals (Pb, Al, and Cu) with significantly different hardness values against the steel plates of various surface textures and roughness using an inclined pin-on-plate sliding apparatus in ambient conditions under both the dry and lubricated conditions. For a given material pair, it was observed that transfer layer formation and the coefficient of friction along with its two components, namely adhesion and plowing, are controlled by the surface texture of the harder mating surfaces and are less dependent of surface roughness (R (a)) of the harder mating surfaces. The effect of surface texture on the friction was attributed to the variation of the plowing component of friction for different surfaces. It was also observed that the variation of plowing friction as a function of hardness depends on surface textures. More specifically, the plowing friction varies with hardness of the soft materials for a given type of surface texture and it is independent of hardness of soft materials for other type of surface texture. These variations could be attributed to the extent of plane strain conditions taking place at the asperity level during sliding. It was also observed that among the surface roughness parameters, the mean slope of the profile, Delta (a), correlated best with the friction. Furthermore, dimensionless quantifiable roughness parameters were formulated to describe the degree of plowing taking place at the asperity level.

The scratch hardness and friction of a soft rigid-plastic solid

The paper describes an experimental and analytical study of the normal and scratch hardnesses of a model soft rigid-plastic solid. The material known as ‘Plasticine’, a mixture of dry particles and a mineral oil, has been deformed with a range of rigid conical indentors with included angles of between 30° and 170°. The sliding velocity dependence of the computed scratch hardness and friction has been examined in the velocity range 0.19 mm/s to 7.3 m/s. Data are also described for the time dependence of the normal hardness and also the estimated rate dependence of the intrinsic flow stress. The latter values were estimated from data obtained during the upsetting of right cylinders. Three major conclusions are drawn from these data and the associated analysis. (1) A first-order account of the scratching force may be provided by adopting a model which sums the computed plastic deformation and interfacial sliding contributions to the total sliding work. This is tantamount to the adoption of the two-term non-interacting model of friction. (2) For this system during sliding, at high sliding velocities at least, the interface shear stress which defines the boundary condition is not directly related to the bulk shear stress. The interface rheological characteristics indicate an appreciable dependence on the imposed strain or strain rate. In particular, the relative contributions of the slip and stick boundary conditions appear to be a function of the imposed sliding velocity. (3) The computed normal and scratch hardness values are not simply interrelated primarily because of the evolving boundary conditions which appear to exist in the scratching experiments.

Microstructure evolution and hardness variation during annealing of equal channel angular pressed ultra-fine grained nickel subjected to 12 passes

The microstructure, thermal stability and hardness of ultra-fine grained (UFG) Ni produced by 12 passes of equal channel angular pressing (ECAP) through the route Bc were studied. Comparing the microstructure and hardness of the as-ECAPed samples with the published data on UFG Ni obtained after 8 passes of ECAP through the route Bc reveals a smaller average grain size (230 nm in the present case compared with 270 nm in 8-pass Ni), significantly lower dislocation density (1.08 x 10(14) m(-2) compared with 9 x 10(14) m(-2) in 8-pass Ni) and lower hardness (2 GPa compared with 2.45 GPa for 8-pass Ni). Study of the thermal stability of the 12-pass UFG Ni revealed that recovery is dominant in the temperature range 150-250A degrees C and recrystallisation occurred at temperatures > 250 A degrees C. The UFG microstructure is relatively stable up to about 400 A degrees C. Due to the lower dislocation density and consequently a lower stored energy, the recrystallisation of 12-pass ECAP Ni occurred at a higher temperature (similar to 250 A degrees C) compared with the 8-pass Ni (similar to 200 A degrees C). In the 12-pass Nickel, hardness variation shows that its dependence on grain size is inversely linear rather than the common grain size(-0.5) dependence.

Design and implementation of a PC-based FPGA tester

A new range of programmable logic devices are revolutionizing the way complex digital hardware is designed and built all over the world. Being able to test these devices in order to validate and dynamically improve on the design is crucial. This paper describes a low-cost FPGA tester that can test SRAM based FPGAs in the laboratory.

Effect of laser processing parameters on the structure of ductile iron

Laser processing of structure sensitive hypereutectic ductile iron, a cast alloy employed for dynamically loaded automative components, was experimentally investigated over a wide range of process parameters: from power (0.5-2.5 kW) and scan rate (7.5-25 mm s(-1)) leading to solid state transformation, all the way through to melting followed by rapid quenching. Superfine dendritic (at 10(5) degrees C s(-1)) or feathery (at 10(4) degrees C s(-1)) ledeburite of 0.2-0.25 mu m lamellar space, gamma-austenite and carbide in the laser melted and martensite in the transformed zone or heat-affected zone were observed, depending on the process parameters. Depth of geometric profiles of laser transformed or melt zone structures, parameters such as dendrile arm spacing, volume fraction of carbide and surface hardness bear a direct relationship with the energy intensity P/UDb2, (10-100 J mm(-3)). There is a minimum energy intensity threshold for solid state transformation hardening (0.2 J mm(-3)) and similarly for the initiation of superficial melting (9 J mm(-3)) and full melting (15 J mm(-3)) in the case of ductile iron. Simulation, modeling and thermal analysis of laser processing as a three-dimensional quasi-steady moving heat source problem by a finite difference method, considering temperature dependent energy absorptivity of the material to laser radiation, thermal and physical properties (kappa, rho, c(p)) and freezing under non-equilibrium conditions employing Scheil's equation to compute the proportion of the solid enabled determination of the thermal history of the laser treated zone. This includes assessment of the peak temperature attained at the surface, temperature gradients, the freezing time and rates as well as the geometric profile of the melted, transformed or heat-affected zone. Computed geometric profiles or depth are in close agreement with the experimental data, validating the numerical scheme.

A fixed-grid finite element based enthalpy formulation for generalized phase change problems: role of superficial mushy region

The enthalpy method is primarily developed for studying phase change in a multicomponent material, characterized by a continuous liquid volume fraction (phi(1)) vs temperature (T) relationship. Using the Galerkin finite element method we obtain solutions to the enthalpy formulation for phase change in 1D slabs of pure material, by assuming a superficial phase change region (linear (phi(1) vs T) around the discontinuity at the melting point. Errors between the computed and analytical solutions are evaluated for the fluxes at, and positions of, the freezing front, for different widths of the superficial phase change region and spatial discretizations with linear and quadratic basis functions. For Stefan number (St) varying between 0.1 and 10 the method is relatively insensitive to spatial discretization and widths of the superficial phase change region. Greater sensitivity is observed at St = 0.01, where the variation in the enthalpy is large. In general the width of the superficial phase change region should span at least 2-3 Gauss quadrature points for the enthalpy to be computed accurately. The method is applied to study conventional melting of slabs of frozen brine and ice. Regardless of the forms for the phi(1) vs T relationships, the thawing times were found to scale as the square of the slab thickness. The ability of the method to efficiently capture multiple thawing fronts which may originate at any spatial location within the sample, is illustrated with the microwave thawing of slabs and 2D cylinders. (C) 2002 Elsevier Science Ltd. All rights reserved.