Optimal multicommodity flow through the complete graph with random edge capacities

We consider a multicommodity flow problem on a complete graph whose edges have random, independent, and identically distributed capacities. We show that, as the number of nodes tends to infinity, the maximumutility, given by the average of a concave function of each commodity How, has an almost-sure limit. Furthermore, the asymptotically optimal flow uses only direct and two-hop paths, and can be obtained in a distributed manner.

Cytocompatibility property evaluation of gas pressure sintered SiAlON-SiC composites with L929 fibroblast cells and Saos-2 osteoblast-like cells

Although the oxide ceramics have widely been investigated for their biocompatibility, non-oxide ceramics, such as SiAlON and SiC are yet to be explored in detail. Lack of understanding of the biocompatibility restricts the use of these ceramics in clinical trials. It is hence, essential to carry out proper and thorough study to assess cell adhesion, cytocompatibility and cell viability on the non-oxide ceramics for the potential applications. In this perspective, the present research work reports the cytocompatibility of gas pressure sintered SiAlON monolith and SiAlON-SiC composites with varying amount of SIC, using connective tissue cells (L929) and bone cells (Saos-2). The quantification of cell viability using MTT assay reveals the non-cytotoxic response. The cell viability has been found to be cell type dependent. An attempt has been made to discuss the cytocompatibility of the developed composites in the light of SiC content and type of sinter additives. (C) 2011 Elsevier B.V. All rights reserved.

Effect of high gold salt concentrations on the size and polydispersity of gold nanoparticles prepared by an extended Turkevich-Frens method

The Turkevich-Frens synthesis starting conditions are expanded, ranging the gold salt concentrations up to 2 mM and citrate/gold(III) molar ratios up to 18:1. For each concentration of the initial gold salt solution, the citrate/gold(III) molar ratios are systematically varied from 2:1 to 18:1 and both the size and size distribution of the resulting gold nanoparticles are compared. This study reveals a different nanoparticle size evolution for gold salt solutions ranging below 0.8 mM compared to the case of gold salt solutions above 0.8 mM. In the case of Au3+]<0.8 mM, both the size and size distribution vary substantially with the citrate/gold(III) ratio, both displaying plateaux that evolve inversely to Au3+] at larger ratios. Conversely, for Au3+]>= 0.8 mM, the size and size distribution of the synthesized gold nanoparticles continuously rise as the citrate/gold(III) ratio is increased. A starting gold salt concentration of 0.6 mM leads to the formation of the most monodisperse gold nanoparticles (polydispersity index<0.1) for a wide range of citrate/gold(III) molar ratios (from 4:1 to 18:1). Via a model for the formation of gold nanoparticles by the citrate method, the experimental trends in size could be qualitatively predicted:the simulations showed that the destabilizing effect of increased electrolyte concentration at high initial Au3+] is compensated by a slight increase in zeta potential of gold nanoparticles to produce concentrated dispersion of gold nanoparticles of small sizes.

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.

Belief propagation for minimum weight many-to-one matchings in the random complete graph

In a complete bipartite graph with vertex sets of cardinalities n and n', assign random weights from exponential distribution with mean 1, independently to each edge. We show that, as n -> infinity, with n' = n/alpha] for any fixed alpha > 1, the minimum weight of many-to-one matchings converges to a constant (depending on alpha). Many-to-one matching arises as an optimization step in an algorithm for genome sequencing and as a measure of distance between finite sets. We prove that a belief propagation (BP) algorithm converges asymptotically to the optimal solution. We use the objective method of Aldous to prove our results. We build on previous works on minimum weight matching and minimum weight edge cover problems to extend the objective method and to further the applicability of belief propagation to random combinatorial optimization problems.