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.

E. C. G. Sudarshan and Symmetry in Classical Dynamics, Optics and Quantum Mechanics

We review work initiated and inspired by Sudarshan in relativistic dynamics, beam optics, partial coherence theory, Wigner distribution methods, multimode quantum optical squeezing, and geometric phases. The 1963 No Interaction Theorem using Dirac's instant form and particle World Line Conditions is recalled. Later attempts to overcome this result exploiting constrained Hamiltonian theory, reformulation of the World Line Conditions and extending Dirac's formalism, are reviewed. Dirac's front form leads to a formulation of Fourier Optics for the Maxwell field, determining the actions of First Order Systems (corresponding to matrices of Sp(2,R) and Sp(4,R)) on polarization in a consistent manner. These groups also help characterize properties and propagation of partially coherent Gaussian Schell Model beams, leading to invariant quality parameters and the new Twist phase. The higher dimensional groups Sp(2n,R) appear in the theory of Wigner distributions and in quantum optics. Elegant criteria for a Gaussian phase space function to be a Wigner distribution, expressions for multimode uncertainty principles and squeezing are described. In geometric phase theory we highlight the use of invariance properties that lead to a kinematical formulation and the important role of Bargmann invariants. Special features of these phases arising from unitary Lie group representations, and a new formulation based on the idea of Null Phase Curves, are presented.

Can one electrochemically measure the statistical morphology of a rough electrode

We have developed a theory for an electrochemical way of measuring the statistical properties of a nonfractally rough electrode. We obtained the expression for the current transient on a rough electrode which shows three times regions: short and long time limits and the transition region between them. The expressions for these time ranges are exploited to extract morphological information about the surface roughness. In the short and long time regimes, we extract information regarding various morphological features like the roughness factor, average roughness, curvature, correlation length, dimensionality of roughness, and polynomial approximation for the correlation function. The formulas for the surface structure factors (the measure of surface roughness) of rough surfaces in terms of measured reversible and diffusion-limited current transients are also obtained. Finally, we explore the feasibility of making such measurements.

Popular matchings with variable item copies

We consider the problem of matching people to items, where each person ranks a subset of items in an order of preference, possibly involving ties. There are several notions of optimality about how to best match a person to an item; in particular, popularity is a natural and appealing notion of optimality. A matching M* is popular if there is no matching M such that the number of people who prefer M to M* exceeds the number who prefer M* to M. However, popular matchings do not always provide an answer to the problem of determining an optimal matching since there are simple instances that do not admit popular matchings. This motivates the following extension of the popular matchings problem: Given a graph G = (A U 3, E) where A is the set of people and 2 is the set of items, and a list < c(1),...., c(vertical bar B vertical bar)> denoting upper bounds on the number of copies of each item, does there exist < x(1),...., x(vertical bar B vertical bar)> such that for each i, having x(i) copies of the i-th item, where 1 <= xi <= c(i), enables the resulting graph to admit a popular matching? In this paper we show that the above problem is NP-hard. We show that the problem is NP-hard even when each c(i) is 1 or 2. We show a polynomial time algorithm for a variant of the above problem where the total increase in copies is bounded by an integer k. (C) 2011 Elsevier B.V. All rights reserved.

Multiple UAV Coalitions for a Search and Prosecute Mission

Unmanned aerial vehicles (UAVs) have the potential to carry resources in support of search and prosecute operations. Often to completely prosecute a target, UAVs may have to simultaneously attack the target with various resources with different capacities. However, the UAVs are capable of carrying only limited resources in small quantities, hence, a group of UAVs (coalition) needs to be assigned that satisfies the target resource requirement. The assigned coalition must be such that it minimizes the target prosecution delay and the size of the coalition. The problem of forming coalitions is computationally intensive due to the combinatorial nature of the problem, but for real-time applications computationally cheap solutions are required. In this paper, we propose decentralized sub-optimal (polynomial time) and decentralized optimal coalition formation algorithms that generate coalitions for a single target with low computational complexity. We compare the performance of the proposed algorithms to that of a global optimal solution for which we need to solve a centralized combinatorial optimization problem. This problem is computationally intensive because the solution has to (a) provide a coalition for each target, (b) design a sequence in which targets need to be prosecuted, and (c) take into account reduction of UAV resources with usage. To solve this problem we use the Particle Swarm Optimization (PSO) technique. Through simulations, we study the performance of the proposed algorithms in terms of mission performance, complexity of the algorithms and the time taken to form the coalition. The simulation results show that the solution provided by the proposed algorithms is close to the global optimal solution and requires far less computational resources.

On the performance of strain smoothing for quadratic and enriched finite element approximations (XFEM/GFEM/PUFEM)

By using the strain smoothing technique proposed by Chen et al. (Comput. Mech. 2000; 25: 137-156) for meshless methods in the context of the finite element method (FEM), Liu et al. (Comput. Mech. 2007; 39(6): 859-877) developed the Smoothed FEM (SFEM). Although the SFEM is not yet well understood mathematically, numerical experiments point to potentially useful features of this particularly simple modification of the FEM. To date, the SFEM has only been investigated for bilinear and Wachspress approximations and is limited to linear reproducing conditions. The goal of this paper is to extend the strain smoothing to higher order elements and to investigate numerically in which condition strain smoothing is beneficial to accuracy and convergence of enriched finite element approximations. We focus on three widely used enrichment schemes, namely: (a) weak discontinuities; (b) strong discontinuities; (c) near-tip linear elastic fracture mechanics functions. The main conclusion is that strain smoothing in enriched approximation is only beneficial when the enrichment functions are polynomial (cases (a) and (b)), but that non-polynomial enrichment of type (c) lead to inferior methods compared to the standard enriched FEM (e.g. XFEM). Copyright (C) 2011 John Wiley & Sons, Ltd.

Nonlinear static and dynamic damped response of a composite rectangular plate resting on a two-parameter elastic foundation

Nonlinear static and dynamic response analyses of a clamped. rectangular composite plate resting on a two-parameter elastic foundation have been studied using von Karman's relations. Incorporating the material damping, the governing coupled, nonlinear partial differential equations are obtained for the plate under step pressure pulse load excitation. These equations have been solved by a one-term solution and by applying Galerkin's technique to the deflection equation. This yields an ordinary nonlinear differential equation in time. The nonlinear static solution is obtained by neglecting the time-dependent variables. Thc nonlinear dynamic damped response is obtained by applying the ultraspherical polynomial approximation (UPA) technique. The influences of foundation modulus, shear modulus, orthotropy, etc. upon the nonlinear static and dynamic responses have been presented.

Hierarchies of circuit classes that are closed under complement

We examine three hierarchies of circuit classes and show they are closed under complementation. (1) The class of languages recognized by a family of polynomial size skew circuits with width O(w), are closed under complement. (2) The class of languages recognized by family of polynomial size circuits with width O(w) and polynomial tree-size, are closed under complement. (3) The class of languages recognized by a family of polynomial size, O(log(n)) depth, bounded AND fan-in with OR fan-in f (f⩾log(n)) circuits are closed under complement. These improve upon the results of (i) Immerman (1988) and Szelepcsenyi (1988), who show that 𝒩L𝒪𝒢 is closed under complementation, and (ii) Borodin et al. (1989), who show that L𝒪𝒢𝒞ℱL is closed under complement

Recursive parametrization of quark flavour mixing matrices

We examine quark flavour mixing matrices for three and four generations using the recursive parametrization of U(n) and SU(n) matrices developed earlier. After a brief summary of the recursive parametrization, we obtain expressions for the independent rephasing invariants and also the constraints on them that arise from the requirement of mod symmetry of the flavour mixing matrix.

Fast computation of Legendre and Zernike moments

This paper presents recursive algorithms for fast computation of Legendre and Zernike moments of a grey-level image intensity distribution. For a binary image, a contour integration method is developed for the evaluation of Legendre moments using only the boundary information. A method for recursive calculation of Zernike polynomial coefficients is also given. A square-to-circular image transformation scheme is introduced to minimize the computation involved in Zernike moment functions. The recursive formulae can also be used in inverse moment transforms to reconstruct the original image from moments. The mathematical framework of the algorithms is given in detail, and illustrated with binary and grey-level images.

Photochemical intramolecular gamma-hydrogen abstraction in a ketone and an alkene and the role of tunneling of hydrogen

Intramolecular gamma-hydrogen abstraction reactions were examined in pentane-2-one and 2-methyl-1-pentene in their lowest triplet states using the AM1 semi-empirical molecular orbital method with the complete geometry optimization in the unrestricted Hartree-Fock frame. The results reveal that the oxygen atom of the carbonyl group and the end carbon atom of the olefinic bond acquire high free valence and spin density indices in their respective lowest triplet states, leading to abstraction of hydrogen from the gamma-position relative to the carbonyl and olefinic bonds. The theoretical energy profiles fit with a polynomial and the probability of tunneling of hydrogen was estimated by the WKB (Wentzel, Kramer and Brillouin) method. The results, after thermal averaging of the rate constants, reveal that tunneling of hydrogen is significant at room temperature.

Vortex sheet simulation of a plane �canonical� mixing layer

Discrete vortex simulations of the mixing layer carried out in the past have usually involved large induced velocity fluctuations, and thus demanded rather long time-averaging to obtain satisfactory values of Reynolds stresses and third-order moments. This difficulty has been traced here, in part, to the use of discrete vortices to model what in actuality are continuous vortex sheets. We propose here a novel two-dimensional vortex sheet technique for computing mixing layer flow in the limit of infinite Reynolds number. The method divides the vortex sheet into constant-strength linear elements, whose motions are computed using the Biot-Savart law. The downstream far-field is modelled by a steady vorticity distribution derived by application of conical similarity from the solution obtained in a finite computational domain. The boundary condition on the splitter plate is satisfied rigorously using a doublet sheet. The computed large-scale roll-up of the vortex sheet is qualitatively similar to experimentally obtained shadow-graphs of the plane turbulent mixing layer. The mean streamwise velocity profile and the growth rate agree well with experimental data. The presently computed Reynolds stresses and third-order moments are comparable with experimental and previous vortex-dynamical results, without using any external parameter (such as the vortex core-size) of the kind often used in the latter. The computed autocorrelations are qualitatively similar to experimental results along the top and bottom edges of the mixing layer, and show a well-defined periodicity along the centreline. The accuracy of the present computation is independently established by demonstrating negligibly small changes in the five invariants (including the Hamiltonian) in vortex dynamics.

Uniform algebras generated by holomorphic and close-to-harmonic functions

The initial motivation for this paper is to discuss a more concrete approach to an approximation theorem of Axler and Shields, which says that the uniform algebra on the closed unit disc (D) over bar generated by z and h, where h is a nowhere-holomorphic harmonic function on D that is continuous up to partial derivative D, equals C((D) over bar). The abstract tools used by Axler and Shields make harmonicity of h an essential condition for their result. We use the concepts of plurisubharmonicity and polynomial convexity to show that, in fact, the same conclusion is reached if h is replaced by h + R, where R is a non-harmonic perturbation whose Laplacian is ``small'' in a certain sense.

Modelling plane mixing layers using vortex points and sheets

We present here a critical assessment of two vortex approaches (both two-dimensional) to the modelling of turbulent mixing layers. In the first approach the flow is represented by point vortices, and in the second it is simulated as the evolution of a continuous vortex sheet composed of short linear elements or ''panels''. The comparison is based on fresh simulations using approximately the same number of elements in either model, paying due attention in both to the boundary conditions far downstream as well as those on the splitter plate from which the mixing layer issues. The comparisons show that, while both models satisfy the well-known invariants of vortex dynamics approximately to the same accuracy, the vortex panel model, although ultimately not convergent, leads to smoother roll-up and values of stresses and moments that are in closer agreement with the experiment, and has a higher computational efficiency for a given degree of convergence on moments. The point vortex model, while faster for a given number of elements, produces an unsatisfactory roll-up which (for the number of elements used) is rendered worse by the incorporation of the Van der Vooren correction for sheet curvature.

Popular mixed matchings

We study the problem of matching applicants to jobs under one-sided preferences; that is, each applicant ranks a non-empty subset of jobs under an order of preference, possibly involving ties. A matching M is said to be more popular than T if the applicants that prefer M to T outnumber those that prefer T to M. A matching is said to be popular if there is no matching more popular than it. Equivalently, a matching M is popular if phi(M, T) >= phi(T, M) for all matchings T, where phi(X, Y) is the number of applicants that prefer X to Y. Previously studied solution concepts based on the popularity criterion are either not guaranteed to exist for every instance (e.g., popular matchings) or are NP-hard to compute (e.g., least unpopular matchings). This paper addresses this issue by considering mixed matchings. A mixed matching is simply a probability distribution over matchings in the input graph. The function phi that compares two matchings generalizes in a natural manner to mixed matchings by taking expectation. A mixed matching P is popular if phi(P, Q) >= phi(Q, P) for all mixed matchings Q. We show that popular mixed matchings always exist and we design polynomial time algorithms for finding them. Then we study their efficiency and give tight bounds on the price of anarchy and price of stability of the popular matching problem. (C) 2010 Elsevier B.V. All rights reserved.