DETERMINISTIC ALGORITHMS FOR MATCHING AND PACKING PROBLEMS BASED ON REPRESENTATIVE SETS

In this work, we study the well-known r-DIMENSIONAL k-MATCHING ((r, k)-DM), and r-SET k-PACKING ((r, k)-SP) problems. Given a universe U := U-1 ... U-r and an r-uniform family F subset of U-1 x ... x U-r, the (r, k)-DM problem asks if F admits a collection of k mutually disjoint sets. Given a universe U and an r-uniform family F subset of 2(U), the (r, k)-SP problem asks if F admits a collection of k mutually disjoint sets. We employ techniques based on dynamic programming and representative families. This leads to a deterministic algorithm with running time O(2.851((r-1)k) .vertical bar F vertical bar. n log(2)n . logW) for the weighted version of (r, k)-DM, where W is the maximum weight in the input, and a deterministic algorithm with running time O(2.851((r-0.5501)k).vertical bar F vertical bar.n log(2) n . logW) for the weighted version of (r, k)-SP. Thus, we significantly improve the previous best known deterministic running times for (r, k)-DM and (r, k)-SP and the previous best known running times for their weighted versions. We rely on structural properties of (r, k)-DM and (r, k)-SP to develop algorithms that are faster than those that can be obtained by a standard use of representative sets. Incorporating the principles of iterative expansion, we obtain a better algorithm for (3, k)-DM, running in time O(2.004(3k).vertical bar F vertical bar . n log(2)n). We believe that this algorithm demonstrates an interesting application of representative families in conjunction with more traditional techniques. Furthermore, we present kernels of size O(e(r)r(k-1)(r) logW) for the weighted versions of (r, k)-DM and (r, k)-SP, improving the previous best known kernels of size O(r!r(k-1)(r) logW) for these problems.

Dynamos driven by weak thermal convection and heterogeneous outer boundary heat flux

We use numerical dynamo models with heterogeneous core-mantle boundary (CMB) heat flux to show that lower mantle lateral thermal variability may help support a dynamo under weak thermal convection. In our reference models with homogeneous CMB heat flux, convection is either marginally supercritical or absent, always below the threshold for dynamo onset. We find that lateral CMB heat flux variations organize the flow in the core into patterns that favour the growth of an early magnetic field. Heat flux patterns symmetric about the equator produce non-reversing magnetic fields, whereas anti-symmetric patterns produce polarity reversals. Our results may explain the existence of the geodynamo prior to inner core nucleation under a tight energy budget. Furthermore, in order to sustain a strong geomagnetic field, the lower mantle thermal distribution was likely dominantly symmetric about the equator. (C) 2015 Elsevier B.V. All rights reserved.

Urea-Functionalized Self-Assembled Molecular Prism for Heterogeneous Catalysis in Water

Reaction of a ditopic urea ``strut'' (L-1) with cis-(tmen)Pd(NO3)(2) yielded a 3+3] self-assembled molecular triangle (T)L-1 = 1,4-di(4-pyridylureido)benzene; tmen = N,N,N',N'-tetrame-thylethane-1,2-diamine]. Replacing cis-(tmen)Pd(NO3)(2) in the above reaction with an equimolar mixture of Pd(NO3)(2) and a clip-type donor (L-2) yielded a template-free multicomponent 3D trigonal prism (P) decorated with multiple urea moieties L-2 = 3,3'-(1H-1,2,4-triazole-3,5-diyl)dipyridine]. This prism (P) was characterized by NMR. spectroscopy, and the structure was confirmed by X-ray crystallography. The P was employed as an effective hydrogen-bond-donor catalyst for Michael reactions of a series of water-insoluble nitro-olefins in an aqueous medium. The P showed better catalytic activity compared to the urea based ligand L-1 and the triangle T. Moreover, the confined nanospace of P in addition to large product outlet windows makes this 3D architecture a perfect molecular vessel to catalyze Diels-Alder reactions of 9-hydroxymethylanthracene with N-substituted maleimide in the aqueous medium. The present results demonstrate new observations on catalytic aqueous Diels-Alder and Michael reactions in heterogeneous fashion employing a discrete 3D architecture of Pd(II). The prism was recycled by simple filtration and reused several tithes without significant loss of activity.

Molecular Cage Impregnated Palladium Nanoparticles: Efficient, Additive-Free Heterogeneous Catalysts for Cyanation of Aryl Halides

Two shape-persistent covalent cages (CC1(r) and CC2(r)) have been devised from triphenyl amine-based trialdehydes and cyclohexane diamine building blocks utilizing the dynamic imine chemistry followed by imine bond reduction. The cage compounds have been characterized by several spectroscopic techniques which suggest that CC1(r) and CC2(r) are 2+3] and 8+12] self-assembled architectures, respectively. These state-of-the-art molecules have a porous interior and stable aromatic backbone with multiple palladium binding sites to engineer the controlled synthesis and stabilization of ultrafine palladium nanoparticles (PdNPs). As-synthesized cage-embedded PdNPs have been characterized by transmission electron microscopy (TEM), scanning electron microscopy (SEM), and powder X-ray diffraction (PXRD). Inductively coupled plasma optical emission spectrometry reveals that Pd@CC1(r) and Pd@CC2(r) have 40 and 25 wt% palladium loading, respectively. On the basis of TEM analysis, it has been estimated that as small as similar to 1.8 nm PdNPs could be stabilized inside the CC1(r), while larger CC2(r) could stabilize similar to 3.7 nm NPs. In contrast, reduction of palladium salts in the absence of the cages form structure less agglomerates. The well-dispersed cage-embedded NPs exhibit efficient catalytic performance in the cyanation of aryl halides under heterogeneous, additive-free condition. Moreover, these materials have excellent stability and recyclability without any agglomeration of PdNPs after several cycles.

Campaigning in Heterogeneous Social Networks: Optimal Control of SI Information Epidemics

We study the optimal control problem of maximizing the spread of an information epidemic on a social network. Information propagation is modeled as a susceptible-infected (SI) process, and the campaign budget is fixed. Direct recruitment and word-of-mouth incentives are the two strategies to accelerate information spreading (controls). We allow for multiple controls depending on the degree of the nodes/individuals. The solution optimally allocates the scarce resource over the campaign duration and the degree class groups. We study the impact of the degree distribution of the network on the controls and present results for Erdos-Renyi and scale-free networks. Results show that more resource is allocated to high-degree nodes in the case of scale-free networks, but medium-degree nodes in the case of Erdos-Renyi networks. We study the effects of various model parameters on the optimal strategy and quantify the improvement offered by the optimal strategy over the static and bang-bang control strategies. The effect of the time-varying spreading rate on the controls is explored as the interest level of the population in the subject of the campaign may change over time. We show the existence of a solution to the formulated optimal control problem, which has nonlinear isoperimetric constraints, using novel techniques that is general and can be used in other similar optimal control problems. This work may be of interest to political, social awareness, or crowdfunding campaigners and product marketing managers, and with some modifications may be used for mitigating biological epidemics.

High Loading of Pd Nanoparticles by Interior Functionalization of MOFs for Heterogeneous Catalysis

In this report, the issue related to nanoparticle (NP) agglomeration upon increasing their loading amount into metal-organic frameworks (MOFs) has been addressed by functionalization of MOFs with alkyne groups. The alkynophilicity of the Pd2+ (or other noble metals) ions has been utilized successfully for significant loading of Pd NPs into alkyne functionalized MOFs. It has been shown here that the size and loading amount of Pd NPs are highly dependent on the surface area and pore width of the MOFs. The loading amount of Pd NPs was increased monotonically without altering their size distribution on a particular MOF. Importantly, the distinct role of alkyne groups for Pe(2+) stabilization has also been demonstrated by performing a control experiment considering a MOF without an alkyne moiety. The preparation of NPs involved two distinct steps viz. adsorption of metal ions inside MOFs and reduction of metal ions. Both of these steps were monitored by microscopic techniques. This report also demonstrates the applicability of Pd@MOF NPs as extremely efficient heterogeneous catalysts for Heck-coupling and hydrogenation reactions of aryl bromides or iodides and alkenes, respectively.