New Approximation Algorithms for Minimum Cycle Bases of Graphs

We consider the problem of computing an approximate minimum cycle basis of an undirected non-negative edge-weighted graph G with m edges and n vertices; the extension to directed graphs is also discussed. In this problem, a {0,1} incidence vector is associated with each cycle and the vector space over F-2 generated by these vectors is the cycle space of G. A set of cycles is called a cycle basis of G if it forms a basis for its cycle space. A cycle basis where the sum of the weights of the cycles is minimum is called a minimum cycle basis of G. Cycle bases of low weight are useful in a number of contexts, e.g. the analysis of electrical networks, structural engineering, chemistry, and surface reconstruction. Although in most such applications any cycle basis can be used, a low weight cycle basis often translates to better performance and/or numerical stability. Despite the fact that the problem can be solved exactly in polynomial time, we design approximation algorithms since the performance of the exact algorithms may be too expensive for some practical applications. We present two new algorithms to compute an approximate minimum cycle basis. For any integer k >= 1, we give (2k - 1)-approximation algorithms with expected running time O(kmn(1+2/k) + mn((1+1/k)(omega-1))) and deterministic running time O(n(3+2/k) ), respectively. Here omega is the best exponent of matrix multiplication. It is presently known that omega < 2.376. Both algorithms are o(m(omega)) for dense graphs. This is the first time that any algorithm which computes sparse cycle bases with a guarantee drops below the Theta(m(omega) ) bound. We also present a 2-approximation algorithm with expected running time O(M-omega root n log n), a linear time 2-approximation algorithm for planar graphs and an O(n(3)) time 2.42-approximation algorithm for the complete Euclidean graph in the plane.

Central Limit Theorem for truncated heavy tailed Banach valued random vectors

In this paper the question of the extent to which truncated heavy tailed random vectors, taking values in a Banach space, retain the characteristic features of heavy tailed random vectors, is answered from the point of view of the central limit theorem.

Localization of light in coherently amplifying random media

We derive and analyze the statistics of reflection coefficient of light backscattered coherently from an amplifying and disordered optical medium modeled by a spatially random refractive index having a uniform imaginary part in one dimension. We find enhancement of reflected intensity owing to a synergy between wave confinement by Anderson localization and coherent amplification by the active medium. This is not the same as that due to enhanced optical path lengths expected from photon diffusion in the random active medium. Our study is relevant to the physical realizability of a mirrorless laser by photon confinement due to Anderson localization.

Probing the inter-tube transport in aligned and random multiwall carbon nanotubes

The temperature and magnetic field dependence of conductivity has been used to probe the inter-tube transport in multiwall carbon nanotubes (MWNTs). The scanning electron microscopy images show highly aligned and random distribution of MWNTs. The conductivity in aligned carbon nanotube (ACNT) and random carbon nanotube (RCNT) samples at low temperature follows T-1/2 (at T < 8 K) and T-3/4 (at T > 8 K) dependence in accordance with the weak localization and electron-electron (e-e) interaction model. The values of diffusion coefficient in ACNT and RCNT are 0.25 x 10(-2) and 0.71 x 10(-2) cm(2) s(-1), respectively, indicating that larger number of inter-tube junctions in later enhances the bulk transport. The positive magnetoconductance (MC) data in both samples show that the weak localization contribution is dominant. However, the saturation of MC at higher fields and lower temperatures indicate that e-e interaction is quite significant in RCNT. The T-3/4 and T-1/2 dependence of inelastic scattering length (l(in)) in ACNT and RCNT samples show that the inelastic e-e scattering is more important in aligned tubes. (C) 2011 American Institute of Physics. doi:10.1063/1.3552911]

An Efficient Random Walk Strategy for Sampling Based Robot Motion Planners

Sampling based planners have been successful in path planning of robots with many degrees of freedom, but still remains ineffective when the configuration space has a narrow passage. We present a new technique based on a random walk strategy to generate samples in narrow regions quickly, thus improving efficiency of Probabilistic Roadmap Planners. The algorithm substantially reduces instances of collision checking and thereby decreases computational time. The method is powerful even for cases where the structure of the narrow passage is not known, thus giving significant improvement over other known methods.

Convergence of Power Control in a Random Channel Environment

In this paper, we study the Foschini Miljanic algorithm, which was originally proposed in a static channel environment. We investigate the algorithm in a random channel environment, study its convergence properties and apply the Gerschgorin theorem to derive sufficient conditions for the convergence of the algorithm. We apply the Foschini and Miljanic algorithm to cellular networks and derive sufficient conditions for the convergence of the algorithm in distribution and validate the results with simulations. In cellular networks, the conditions which ensure convergence in distribution can be easily verified.

Pulsed laser deposition of strontium titanate thin films for dynamic random access memory applications

Polycrystalline strontium titanate (SrTiO3) films were prepared by a pulsed laser deposition technique on p-type silicon and platinum-coated silicon substrates. The films exhibited good structural and dielectric properties which were sensitive to the processing conditions. The small signal dielectric constant and dissipation factor at a frequency of 100 kHz were about 225 and 0.03 respectively. The capacitance-voltage (C-V) characteristics in metal-insulator-semiconductor structures exhibited anomalous frequency dispersion behavior and a hysteresis effect. The hysteresis in the C-V curve was found to be about 1 V and of a charge injection type. The density of interface states was about 1.79 x 10(12) cm(-2). The charge storage density was found to be 40 fC mu m(-2) at an applied electric field of 200 kV cm(-1). Studies on current-voltage characteristics indicated an ohmic nature at lower voltages and space charge conduction at higher voltages. The films also exhibited excellent time-dependent dielectric breakdown behavior.

Monte-Carlo estimation of time-dependent statistical characteristics of random dynamical systems

The problem of estimating the time-dependent statistical characteristics of a random dynamical system is studied under two different settings. In the first, the system dynamics is governed by a differential equation parameterized by a random parameter, while in the second, this is governed by a differential equation with an underlying parameter sequence characterized by a continuous time Markov chain. We propose, for the first time in the literature, stochastic approximation algorithms for estimating various time-dependent process characteristics of the system. In particular, we provide efficient estimators for quantities such as the mean, variance and distribution of the process at any given time as well as the joint distribution and the autocorrelation coefficient at different times. A novel aspect of our approach is that we assume that information on the parameter model (i.e., its distribution in the first case and transition probabilities of the Markov chain in the second) is not available in either case. This is unlike most other work in the literature that assumes availability of such information. Also, most of the prior work in the literature is geared towards analyzing the steady-state system behavior of the random dynamical system while our focus is on analyzing the time-dependent statistical characteristics which are in general difficult to obtain. We prove the almost sure convergence of our stochastic approximation scheme in each case to the true value of the quantity being estimated. We provide a general class of strongly consistent estimators for the aforementioned statistical quantities with regular sample average estimators being a specific instance of these. We also present an application of the proposed scheme on a widely used model in population biology. Numerical experiments in this framework show that the time-dependent process characteristics as obtained using our algorithm in each case exhibit excellent agreement with exact results. (C) 2010 Elsevier Inc. All rights reserved.

Conditional linearization in nonlinear random vibration

In this paper, an improved probabilistic linearization approach is developed to study the response of nonlinear single degree of freedom (SDOF) systems under narrow-band inputs. An integral equation for the probability density function (PDF) of the envelope is derived. This equation is solved using an iterative scheme. The technique is applied to study the hardening type Duffing's oscillator under narrow-band excitation. The results compare favorably with those obtained using numerical simulation. In particular, the bimodal nature of the PDF for the response envelope for certain parameter ranges is brought out.

Effect of dynamical asymmetry on the viscosity of a random copolymer melt

The variation of the viscosity as a function of the sequence distribution in an A-B random copolymer melt is determined. The parameters that characterize the random copolymer are the fraction of A monomers f, the parameter lambda which determines the correlation in the monomer identities along a chain and the Flory chi parameter chi(F) which determines the strength of the enthalpic repulsion between monomers of type A and B. For lambda>0, there is a greater probability of finding like monomers at adjacent positions along the chain, and for lambda<0 unlike monomers are more likely to be adjacent to each other. The traditional Markov model for the random copolymer melt is altered to remove ultraviolet divergences in the equations for the renormalized viscosity, and the phase diagram for the modified model has a binary fluid type transition for lambda>0 and does not exhibit a phase transition for lambda<0. A mode coupling analysis is used to determine the renormalization of the viscosity due to the dependence of the bare viscosity on the local concentration field. Due to the dissipative nature of the coupling. there are nonlinearities both in the transport equation and in the noise correlation. The concentration dependence of the transport coefficient presents additional difficulties in the formulation due to the Ito-Stratonovich dilemma, and there is some ambiguity about the choice of the concentration to be used while calculating the noise correlation. In the Appendix, it is shown using a diagrammatic perturbation analysis that the Ito prescription for the calculation of the transport coefficient, when coupled with a causal discretization scheme, provides a consistent formulation that satisfies stationarity and the fluctuation dissipation theorem. This functional integral formalism is used in the present analysis, and consistency is verified for the present problem as well. The upper critical dimension for this type of renormaliaation is 2, and so there is no divergence in the viscosity in the vicinity of a critical point. The results indicate that there is a systematic dependence of the viscosity on lambda and chi(F). The fluctuations tend to increase the viscosity for lambda<0, and decrease the viscosity for lambda>0, and an increase in chi(F) tends to decrease the viscosity. (C) 1996 American Institute of Physics.

On generating optimal signal probabilities for random tests: A genetic approach

Genetic Algorithms are robust search and optimization techniques. A Genetic Algorithm based approach for determining the optimal input distributions for generating random test vectors is proposed in the paper. A cost function based on the COP testability measure for determining the efficacy of the input distributions is discussed, A brief overview of Genetic Algorithms (GAs) and the specific details of our implementation are described. Experimental results based on ISCAS-85 benchmark circuits are presented. The performance pf our GA-based approach is compared with previous results. While the GA generates more efficient input distributions than the previous methods which are based on gradient descent search, the overheads of the GA in computing the input distributions are larger. To account for the relatively quick convergence of the gradient descent methods, we analyze the landscape of the COP-based cost function. We prove that the cost function is unimodal in the search space. This feature makes the cost function amenable to optimization by gradient-descent techniques as compared to random search methods such as Genetic Algorithms.

Chordal Bipartite Graphs with High Boxicity

The boxicity of a graph G is defined as the minimum integer k such that G is an intersection graph of axis-parallel k-dimensional boxes. Chordal bipartite graphs are bipartite graphs that do not contain an induced cycle of length greater than 4. It was conjectured by Otachi, Okamoto and Yamazaki that chordal bipartite graphs have boxicity at most 2. We disprove this conjecture by exhibiting an infinite family of chordal bipartite graphs that have unbounded boxicity.