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.

High temperature thermoelectric properties of Zr and Hf based transition metal dichalcogenides: A first principles study

We investigate the electronic and thermal transport properties of bulk MX2 compounds (M = Zr, Hf and X = S, Se) by first-principles calculations and semi-classical Boltzmann transport theory. The band structure shows the confinement of heavy and light bands along the out of plane and in-plane directions, respectively. This results in high electrical conductivity (sigma) and large thermopower leading to a high power factor (S-2 sigma) for moderate n-type doping. The phonon dispersion demonstrates low frequency flat acoustical modes, which results in low group velocities (v(g)). Consequently, lowering the lattice thermal conductivity (kappa(latt)) below 2 W/m K. Low kappa(latt) combined with high power factor results in ZT > 0.8 for all the bulk MX2 compounds at high temperature of 1200 K. In particular, the ZT(max) of HfSe2 exceeds 1 at 1400 K. Our results show that Hf/Zr based dichalcogenides are very promising for high temperature thermoelectric application. (C) 2015 AIP Publishing LLC.

Maximum Spreading of Liquid Drops Impacting on Groove-Textured Surfaces: Effect of Surface Texture

Maximum, spreading of liquid drops impacting on solid surfaces textured with unidirectional parallel grooves is studied for drop Weber number in the range 1-100 focusing on the role of texture geometry and wettability. The maximum spread factor of impacting drops measured perpendicular to grooves; beta(m,perpendicular to) is seen to be less than, that:measured parallel to grooves, beta(m,perpendicular to).The difference between beta(m,perpendicular to), and beta(m,parallel to) increases with drop impact velocity. This deviation of beta(m,perpendicular to) from beta(m,parallel to) is analyzed by considering the possible mechanisms, correspond, ing to experimental observations (1) impregnation of drop into the grooves, (2) convex shape of liquid vapor interface near contact line at maximum spreading, and (3) contact line pinning of spreading drop at the pillar edges by incorporating them into an energy conservation-based model. The analysis reveals that contact line pinning offers a physically meaningful justification of the observed: deviation of beta(m,perpendicular to) from beta(m,parallel to) compared to other possible candidates. A unified model, incorporating all the above-mentioned mechanisms, is formulated, which predicts beta(m,perpendicular to) on several groove-textured surfaces made of intrinsically hydrophilic and hydrophobic materials with an average error of 8.3%. The effect of groove-texture geometrical parameters,on maximum drop spreading is explained using this unified model. A special case of the unified model, with contact line pinning, absent, predicts beta(m,parallel to) with an average error of 6.3%.