BELIEF PROPAGATION FOR OPTIMAL EDGE COVER IN THE RANDOM COMPLETE GRAPH

We apply the objective method of Aldous to the problem of finding the minimum-cost edge cover of the complete graph with random independent and identically distributed edge costs. The limit, as the number of vertices goes to infinity, of the expected minimum cost for this problem is known via a combinatorial approach of Hessler and Wastlund. We provide a proof of this result using the machinery of the objective method and local weak convergence, which was used to prove the (2) limit of the random assignment problem. A proof via the objective method is useful because it provides us with more information on the nature of the edge's incident on a typical root in the minimum-cost edge cover. We further show that a belief propagation algorithm converges asymptotically to the optimal solution. This can be applied in a computational linguistics problem of semantic projection. The belief propagation algorithm yields a near optimal solution with lesser complexity than the known best algorithms designed for optimality in worst-case settings.

Rainbow Connection Number of Graph Power and Graph Products

Rainbow connection number, rc(G), of a connected graph G is the minimum number of colors needed to color its edges so that every pair of vertices is connected by at least one path in which no two edges are colored the same (note that the coloring need not be proper). In this paper we study the rainbow connection number with respect to three important graph product operations (namely the Cartesian product, the lexicographic product and the strong product) and the operation of taking the power of a graph. In this direction, we show that if G is a graph obtained by applying any of the operations mentioned above on non-trivial graphs, then rc(G) a parts per thousand currency sign 2r(G) + c, where r(G) denotes the radius of G and . In general the rainbow connection number of a bridgeless graph can be as high as the square of its radius 1]. This is an attempt to identify some graph classes which have rainbow connection number very close to the obvious lower bound of diameter (and thus the radius). The bounds reported are tight up to additive constants. The proofs are constructive and hence yield polynomial time -factor approximation algorithms.

On the Maximum Number of Linearly Independent Cycles and Paths in a Network

Central to network tomography is the problem of identifiability, the ability to identify internal network characteristics uniquely from end-to-end measurements. This problem is often underconstrained even when internal network characteristics such as link delays are modeled as additive constants. While it is known that the network topology can play a role in determining the extent of identifiability, there is a lack in the fundamental understanding of being able to quantify it for a given network. In this paper, we consider the problem of identifying additive link metrics in an arbitrary undirected network using measurement nodes and establishing paths/cycles between them. For a given placement of measurement nodes, we define and derive the ``link rank'' of the network-the maximum number of linearly independent cycles/paths that may be established between the measurement nodes. We achieve this in linear time. The link rank helps quantify the exact extent of identifiability in a network. We also develop a quadratic time algorithm to compute a set of cycles/paths that achieves the maximum rank.

Equilibrium and equivariant triangulations of some small covers with minimum number of vertices

Small covers were introduced by Davis and Januszkiewicz in 1991. We introduce the notion of equilibrium triangulations for small covers. We study equilibrium and vertex minimal 4-equivariant triangulations of 2-dimensional small covers. We discuss vertex minimal equilibrium triangulations of RP3#RP3, S-1 x RP2 and a nontrivial S-1 bundle over RP2. We construct some nice equilibrium triangulations of the real projective space RPn with 2(n) + n 1 vertices. The main tool is the theory of small covers.

Behaviour of turbulent Prandtl/Schmidt number in compressible mixing layer

The behaviour of turbulent Prandtl/Schmidt number is explored through the model-free simulation results. It has been observed that compressibility affects the Reynolds scalar flux vectors. Reduced peak values are also observed for compressible convective Mach number mixing layer as compared with the incompressible convective Mach number counterpart, indicating a reduction in the mixing of enthalpy and species. Pr-t and Sc-t variations also indicate a reduction in mixing. It is observed that unlike the incompressible case, it is difficult to assign a constant value to these numbers due to their continuous variation in space. Modelling of Pr-t and Sc-t would be necessary to cater for this continuous spatial variation. However, the turbulent Lewis number is evaluated to be near unity for the compressible case, making it necessary to model only one of the Pr-t and Sc-t..

Simultaneous perturbation methods for adaptive labor staffing in service systems

We consider the problem of optimizing the workforce of a service system. Adapting the staffing levels in such systems is non-trivial due to large variations in workload and the large number of system parameters do not allow for a brute force search. Further, because these parameters change on a weekly basis, the optimization should not take longer than a few hours. Our aim is to find the optimum staffing levels from a discrete high-dimensional parameter set, that minimizes the long run average of the single-stage cost function, while adhering to the constraints relating to queue stability and service-level agreement (SLA) compliance. The single-stage cost function balances the conflicting objectives of utilizing workers better and attaining the target SLAs. We formulate this problem as a constrained parameterized Markov cost process parameterized by the (discrete) staffing levels. We propose novel simultaneous perturbation stochastic approximation (SPSA)-based algorithms for solving the above problem. The algorithms include both first-order as well as second-order methods and incorporate SPSA-based gradient/Hessian estimates for primal descent, while performing dual ascent for the Lagrange multipliers. Both algorithms are online and update the staffing levels in an incremental fashion. Further, they involve a certain generalized smooth projection operator, which is essential to project the continuous-valued worker parameter tuned by our algorithms onto the discrete set. The smoothness is necessary to ensure that the underlying transition dynamics of the constrained Markov cost process is itself smooth (as a function of the continuous-valued parameter): a critical requirement to prove the convergence of both algorithms. We validate our algorithms via performance simulations based on data from five real-life service systems. For the sake of comparison, we also implement a scatter search based algorithm using state-of-the-art optimization tool-kit OptQuest. From the experiments, we observe that both our algorithms converge empirically and consistently outperform OptQuest in most of the settings considered. This finding coupled with the computational advantage of our algorithms make them amenable for adaptive labor staffing in real-life service systems.

An estimate of the number of tropical tree species

The high species richness of tropical forests has long been recognized, yet there remains substantial uncertainty regarding the actual number of tropical tree species. Using a pantropical tree inventory database from closed canopy forests, consisting of 657,630 trees belonging to 11,371 species, we use a fitted value of Fisher's alpha and an approximate pantropical stem total to estimate the minimum number of tropical forest tree species to fall between similar to 40,000 and similar to 53,000, i.e., at the high end of previous estimates. Contrary to common assumption, the Indo-Pacific region was found to be as species-rich as the Neotropics, with both regions having a minimum of similar to 19,000-25,000 tree species. Continental Africa is relatively depauperate with a minimum of similar to 4,500-6,000 tree species. Very few species are shared among the African, American, and the Indo-Pacific regions. We provide a methodological framework for estimating species richness in trees that may help refine species richness estimates of tree-dependent taxa.

Minimization Problems Based on Relative alpha-Entropy I: Forward Projection

Minimization problems with respect to a one-parameter family of generalized relative entropies are studied. These relative entropies, which we term relative alpha-entropies (denoted I-alpha), arise as redundancies under mismatched compression when cumulants of compressed lengths are considered instead of expected compressed lengths. These parametric relative entropies are a generalization of the usual relative entropy (Kullback-Leibler divergence). Just like relative entropy, these relative alpha-entropies behave like squared Euclidean distance and satisfy the Pythagorean property. Minimizers of these relative alpha-entropies on closed and convex sets are shown to exist. Such minimizations generalize the maximum Renyi or Tsallis entropy principle. The minimizing probability distribution (termed forward I-alpha-projection) for a linear family is shown to obey a power-law. Other results in connection with statistical inference, namely subspace transitivity and iterated projections, are also established. In a companion paper, a related minimization problem of interest in robust statistics that leads to a reverse I-alpha-projection is studied.

Minimization Problems Based on Relative alpha-Entropy II: Reverse Projection

In part I of this two-part work, certain minimization problems based on a parametric family of relative entropies (denoted I-alpha) were studied. Such minimizers were called forward I-alpha-projections. Here, a complementary class of minimization problems leading to the so-called reverse I-alpha-projections are studied. Reverse I-alpha-projections, particularly on log-convex or power-law families, are of interest in robust estimation problems (alpha > 1) and in constrained compression settings (alpha < 1). Orthogonality of the power-law family with an associated linear family is first established and is then exploited to turn a reverse I-alpha-projection into a forward I-alpha-projection. The transformed problem is a simpler quasi-convex minimization subject to linear constraints.

Onset of plane layer magnetoconvection at low Ekman number

We study the onset of magnetoconvection between two infinite horizontal planes subject to a vertical magnetic field aligned with background rotation. In order to gain insight into the convection taking place in the Earth's tangent cylinder, we target regimes of asymptotically strong rotation. The critical Rayleigh number Ra-c and critical wavenumber a(c) are computed numerically by solving the linear stability problem in a systematic way, with either stress-free or no-slip kinematic boundary conditions. A parametric study is conducted, varying the Ekman number E (ratio of viscous to Coriolis forces) and the Elsasser number. (ratio of the Lorentz force to the Coriolis force). E is varied from 10(-9) to 10(-2) and. from 10(-3) to 1. For a wide range of thermal and magnetic Prandtl numbers, our results verify and confirm previous experimental and theoretical results showing the existence of two distinct unstable modes at low values of E-one being controlled by the magnetic field, the other being controlled by viscosity (often called the viscous mode). It is shown that oscillatory onset does not occur in the range of parameters we are interested in. Asymptotic scalings for the onset of these modes are numerically confirmed and their domain of validity is precisely quantified. We show that with no-slip boundary conditions, the asymptotic behavior is reached for E < 10(-6) and establish a map in the (E, Lambda) plane. We distinguish regions where convection sets in either through the magnetic mode or through the viscous mode. Our analysis gives the regime in which the transition between magnetic and viscous modes may be observed. We also show that within the asymptotic regime, the role played by the kinematic boundary conditions is minimal. (C) 2015 AIP Publishing LLC.

Upper bound on cubicity in terms of boxicity for graphs of low chromatic number

The boxicity (respectively cubicity) of a graph G is the least integer k such that G can be represented as an intersection graph of axis-parallel k-dimensional boxes (respectively k-dimensional unit cubes) and is denoted by box(G) (respectively cub(G)). It was shown by Adiga and Chandran (2010) that for any graph G, cub(G) <= box(G) log(2) alpha(G], where alpha(G) is the maximum size of an independent set in G. In this note we show that cub(G) <= 2 log(2) X (G)] box(G) + X (G) log(2) alpha(G)], where x (G) is the chromatic number of G. This result can provide a much better upper bound than that of Adiga and Chandran for graph classes with bounded chromatic number. For example, for bipartite graphs we obtain cub(G) <= 2(box(G) + log(2) alpha(G)] Moreover, we show that for every positive integer k, there exist graphs with chromatic number k such that for every epsilon > 0, the value given by our upper bound is at most (1 + epsilon) times their cubicity. Thus, our upper bound is almost tight. (c) 2015 Elsevier B.V. All rights reserved.