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 simple local 3-approximation algorithm for vertex cover

We present a local algorithm (constant-time distributed algorithm) for finding a 3-approximate vertex cover in bounded-degree graphs. The algorithm is deterministic, and no auxiliary information besides port numbering is required. (c) 2009 Elsevier B.V. All rights reserved.

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.

An optimal local approximation algorithm for max-min linear programs

In a max-min LP, the objective is to maximise ω subject to Ax ≤ 1, Cx ≥ ω1, and x ≥ 0 for nonnegative matrices A and C. We present a local algorithm (constant-time distributed algorithm) for approximating max-min LPs. The approximation ratio of our algorithm is the best possible for any local algorithm; there is a matching unconditional lower bound.

Unified Galerkin- and DAE-Based Approximation of Fractional Order Systems

We consider numerical solutions of nonlinear multiterm fractional integrodifferential equations, where the order of the highest derivative is fractional and positive but is otherwise arbitrary. Here, we extend and unify our previous work, where a Galerkin method was developed for efficiently approximating fractional order operators and where elements of the present differential algebraic equation (DAE) formulation were introduced. The DAE system developed here for arbitrary orders of the fractional derivative includes an added block of equations for each fractional order operator, as well as forcing terms arising from nonzero initial conditions. We motivate and explain the structure of the DAE in detail. We explain how nonzero initial conditions should be incorporated within the approximation. We point out that our approach approximates the system and not a specific solution. Consequently, some questions not easily accessible to solvers of initial value problems, such as stability analyses, can be tackled using our approach. Numerical examples show excellent accuracy. DOI: 10.1115/1.4002516]

Time-Dependent Dynamics of a Planar Galaxy Model

Time-dependent models of collisionless stellar systems with harmonic potentials allowing for an essentially exact analytic description have recently been described. These include oscillating spheres and spheroids. This paper extends the analysis to time-dependent elliptic discs. Although restricted to two space dimensions, the systems are richer in that their parameters form a 10-dimensional phase space (in contrast to six for the earlier models). Apart from total energy and angular momentum, two additional conserved quantities emerge naturally. These can be chosen as the areas of extremal sections of the ellipsoidal region of phase space occupied by the system (their product gives the conserved volume). The present paper describes the construction of these models. An application to a tidal encounter is given which allows one to go beyond the impulse approximation and demonstrates the effects of rotation of the perturbed system on energy and angular-momentum transfer. The angular-momentum transfer is shown to scale inversely as the cube of the encounter velocity for an initial configuration of the perturbed galaxy with zero quadrupole moment.

On shock dynamics

This is in continuation of our paper On the propagation of a multi-dimensional shock of arbitrary strength’ published earlier in this journal (Srinivasan and Prasad [9]). We had shown in our paper that Whitham’s shock dynamics, based on intuitive arguments, cannot be relied on for flows other than those involving weak shocks and that too with uniform flow behind the shock. Whitham [12] refers to this as misinterpretation of his approximation and claims that his theory is not only correct but also provides a natural closure of the open system of the equations of Maslov [3]. The main aim of this note is to refute Whitham’s claim with the help of an example and a numerical integration of a problem in gasdynamics.

Effects of temper level on the dependence of fatigue crack growth threshold and crack closure on the prior austenitic grain size

An attempt has been made to systematically investigate the effects of microstructural parameters, such as the prior austenite grain size (PAGS), in influencing the resistance to fatigue crack growth (FCG) in the near-threshold region under three different temper levels in a quenched and tempered high-strength steel. By austenitizing at various temperatures, the PAGS was varied from about 0.7 to 96 μm. The microstructures with these grain sizes were tempered at 200 °C, 400 °C, and 530 °C and tested for fatigue thresholds and crack closure. It has been found that, in general, three different trends in the dependence of both the total threshold stress intensity range, ΔK th , and the intrinsic threshold stress intensity range, ΔK eff, th , on the PAGS are observable. By considering in detail the factors such as cyclic stress-strain behavior, environmental effects on FCG, and embrittlement during tempering, the present observations could be rationalized. The strong dependence of ΔK th and ΔK eff, th on PAGS in microstructures tempered at 530 °C has been primarily attributed to cyclic softening and thereby the strong interaction of the crack tip deformation field with the grain boundary. On the other hand, a less strong dependence of ΔK th and ΔK eff, th on PAGS is suggested to be caused by the cyclic hardening behavior of lightly tempered microstructures occurring in 200 °C temper. In both microstructures, crack closure influenced near-threshold FCG (NTFCG) to a significant extent, and its magnitude was large at large grain sizes. Microstructures tempered at the intermediate temperatures failed to show a systematic variation of ΔKth and ΔKeff, th with PAGS. The mechanisms of intergranular fracture vary between grain sizes in this temper. A transition from “microstructure-sensitive” to “microstructure-insensitive” crack growth has been found to occur when the zone of cyclic deformation at the crack tip becomes more or less equal to PAGS. Detailed observations on fracture morphology and crack paths corroborate the grain size effects on fatigue thresholds and crack closure.

Activation barriers for d.c. conductivity in ionic glasses: Classical calculations using the small-cluster approximation

A small-cluster approximation has been used to calculate the activation barriers for the d.c. conductivity in ionic glasses. The main emphasis of this approach is on the importance of the hitherto ignored polarization energy contribution to the total activation energy. For the first time it has been demonstrated that the d.c. conductivity activation energy can be calculated by considering ionic migration to a neighbouring vacancy in a smali cluster of ions consisting of face-sharing anion polyhedra. The activation energies from the model calculations have been compared with the experimental values in the case of highly modified lithium thioborate glasses.

Attitude estimation using moment invariants

The problem of estimating the three-dimensional rotational parameters of a rigid body from its monocular image data has been considered using the method of moment invariants. Second- and third-order moment invariants are used to construct the feature vector for the scale and orientation independent identification of the camera view axis direction in the body-fixed reference frame. The camera rotation angle about the view axis is derived from second-order central moments. The relative attitude of the rigid body is then expressed in terms of quaternion parameters to model the outputs of a video sensor in attitude control simulations. Experimental results and simulation outputs are presented using the mathematical model of a spacecraft.