Vertex Cover Gets Faster and Harder on Low Degree Graphs

The problem of finding an optimal vertex cover in a graph is a classic NP-complete problem, and is a special case of the hitting set question. On the other hand, the hitting set problem, when asked in the context of induced geometric objects, often turns out to be exactly the vertex cover problem on restricted classes of graphs. In this work we explore a particular instance of such a phenomenon. We consider the problem of hitting all axis-parallel slabs induced by a point set P, and show that it is equivalent to the problem of finding a vertex cover on a graph whose edge set is the union of two Hamiltonian Paths. We show the latter problem to be NP-complete, and also give an algorithm to find a vertex cover of size at most k, on graphs of maximum degree four, whose running time is 1.2637(k) n(O(1)).

Lower Bounds for Sums of Powers of Low Degree Univariates

We consider the problem of representing a univariate polynomial f(x) as a sum of powers of low degree polynomials. We prove a lower bound of Omega(root d/t) for writing an explicit univariate degree-d polynomial f(x) as a sum of powers of degree-t polynomials.

Influence of surface chemistry of mesoporous alumina with wide pore distribution on controlled drug release

The crucial role of the drug carrier surface chemical moeities on the uptake and in vitro release of drug is discussed here in a systematic manner. Mesoporous alumina with a wide pore size distribution (2-7 nm) functionalized with various hydrophilic and hydrophobic surface chemical groups was employed as the carrier for delivery of the model drug ibuprofen. Surface functionalization with hydrophobic groups resulted in low degree of drug loading (approximately 20%) and fast rate of release (85% over a period of 5 h) whereas hydrophilic groups resulted in a significantly higher drug payloads (21%-45%) and slower rate of release (12%-40% over a period of 5 h). Depending on the chemical moiety, the diffusion controlled (proportional to time(-0.5)) drug release was additionally observed to be dependent on the mode of arrangement of the functional groups on the alumina surface as well as on the pore characteristics of the matrix. For all mesoporous alumina systems the drug dosages were far lower than the maximum recommended therapeutic dosages (MRTD) for oral delivery. We envisage that the present study would aid in the design of delivery systems capable of sustained release of multiple drugs.

Optimal incentive timing strategies for product marketing on social networks

We consider the problem of devising incentive strategies for viral marketing of a product. In particular, we assume that the seller can influence penetration of the product by offering two incentive programs: a) direct incentives to potential buyers (influence) and b) referral rewards for customers who influence potential buyers to make the purchase (exploit connections). The problem is to determine the optimal timing of these programs over a finite time horizon. In contrast to algorithmic perspective popular in the literature, we take a mean-field approach and formulate the problem as a continuous-time deterministic optimal control problem. We show that the optimal strategy for the seller has a simple structure and can take both forms, namely, influence-and-exploit and exploit-and-influence. We also show that in some cases it may optimal for the seller to deploy incentive programs mostly for low degree nodes. We support our theoretical results through numerical studies and provide practical insights by analyzing various scenarios.

Semi-active vibration isolation using a near-zero-spring-rate device:steady state analysis of a single-degree-of-freedom model

A vibration isolator is described which incorporates a near-zero-spring-rate device within its operating range. The device is an assembly of a vertical spring in parallel with two inclined springs. A low spring rate is achieved by combining the equivalent stiffness in the vertical direction of the inclined springs with the stiffness of the vertical central spring. It is shown that there is a relation between the geometry and the stiffness of the individual springs that results in a low spring rate. Computer simulation studies of a single-degree-of-freedom model for harmonic base input show that the performance of the proposed scheme is superior to that of the passive schemes with linear springs and skyhook damping configuration. The response curves show that, for small to large amplitudes of base disturbance, the system goes into resonance at low frequencies of excitation. Thus, it is possible to achieve very good isolation over a wide low-frequency band. Also, the damper force requirements for the proposed scheme are much lower than for the damper force of a skyhook configuration or a conventional linear spring with a semi-active damper.

Geometric Representation of Graphs in Low Dimension Using Axis Parallel Boxes

An axis-parallel k-dimensional box is a Cartesian product R-1 x R-2 x...x R-k where R-i (for 1 <= i <= k) is a closed interval of the form [a(i), b(i)] on the real line. For a graph G, its boxicity box(G) is the minimum dimension k, such that G is representable as the intersection graph of (axis-parallel) boxes in k-dimensional space. The concept of boxicity finds applications in various areas such as ecology, operations research etc. A number of NP-hard problems are either polynomial time solvable or have much better approximation ratio on low boxicity graphs. For example, the max-clique problem is polynomial time solvable on bounded boxicity graphs and the maximum independent set problem for boxicity d graphs, given a box representation, has a left perpendicular1 + 1/c log n right perpendicular(d-1) approximation ratio for any constant c >= 1 when d >= 2. In most cases, the first step usually is computing a low dimensional box representation of the given graph. Deciding whether the boxicity of a graph is at most 2 itself is NP-hard. We give an efficient randomized algorithm to construct a box representation of any graph G on n vertices in left perpendicular(Delta + 2) ln nright perpendicular dimensions, where Delta is the maximum degree of G. This algorithm implies that box(G) <= left perpendicular(Delta + 2) ln nright perpendicular for any graph G. Our bound is tight up to a factor of ln n. We also show that our randomized algorithm can be derandomized to get a polynomial time deterministic algorithm. Though our general upper bound is in terms of maximum degree Delta, we show that for almost all graphs on n vertices, their boxicity is O(d(av) ln n) where d(av) is the average degree.

An SIMD machine for low-level vision

This paper presents an SIMD machine which has been tuned to execute low-level vision algorithms employing the relaxation labeling paradigm. Novel features of the design include: 1. (1) a communication scheme capable of window accessing under a single instruction. 2. (2) flexible I/O instructions to load overlapped data segments; and 3. (3) data-conditional instructions which can be nested to an arbitrary degree. A time analysis of the stereo correspondence problem, as implemented on a simulated version of the machine using the probabilistic relaxation technique, shows a speed up of almost N2 for an N × N array of PEs.

High-temperature low-cycle fatigue behavior of a NIMONIC PE-16 superalloy—Correlation with deformation and fracture

Low-cycle fatigue (LCF) responses of NIMONIC PE-16 for various prior microstructures and strain amplitudes have been evaluated and the fatigue behavior has been explained in terms of the operative deformation mechanisms. Total strain-controlled LCF tests were performed at 923 K on samples possessing three different prior microstructures: alloy A in solution-annealed condition (free of γ′ and carbides), alloy B with double aging treatment (spherical γ′ of 18-nm diameter and M23C6), and alloy C with another double aging treatment (γ′ of size 35 nm, MC and M23C6). All three microstructures exhibited an intial cyclic hardening followed by a period of gradual softening at 923 K. Coffin-Manson plots describing the plastic strain amplitudevs number of reversals to failure showed that alloy A had maximum fatigue life while C showed the least. Alloy B exhibited a two-slope behavior in the Coffin-Manson plot over the strain amplitudes investigated. This has been ascribed to the change in the degree of homogeneity of deformation at high and low strain amplitudes. Transmission electron microscopic studies were carried out to characterize the various deformation mechanisms and precipitation reactions occurring during fatigue testign. Fresh precipitation of fine γ′ was confirmed by the development of “mottled contrast” in alloy C. Evidence for the shearing of the ordered γ′ precipitates was revealed by the presence of superdislocations in alloy C. Repeated shearing during cyclic loading led to the reduction in the size of the γ′ and consequent softening. Coarser γ′ precipitates were associated with Orowan loops. The observed fatigue behavior has been rationalized based on the micromechanisms stated above and on the degree of homogenization of slip assessed by slipband spacing measurements on tested samples.

Nonlinear dynamics and chaotic motions in feedback-controlled two- and three-degree-of-freedom robots

The dynamics of a feedback-controlled rigid robot is most commonly described by a set of nonlinear ordinary differential equations. In this paper we analyze these equations, representing the feedback-controlled motion of two- and three-degrees-of-freedom rigid robots with revolute (R) and prismatic (P) joints in the absence of compliance, friction, and potential energy, for the possibility of chaotic motions. We first study the unforced or inertial motions of the robots, and show that when the Gaussian or Riemannian curvature of the configuration space of a robot is negative, the robot equations can exhibit chaos. If the curvature is zero or positive, then the robot equations cannot exhibit chaos. We show that among the two-degrees-of-freedom robots, the PP and the PR robot have zero Gaussian curvature while the RP and RR robots have negative Gaussian curvatures. For the three-degrees-of-freedom robots, we analyze the two well-known RRP and RRR configurations of the Stanford arm and the PUMA manipulator respectively, and derive the conditions for negative curvature and possible chaotic motions. The criteria of negative curvature cannot be used for the forced or feedback-controlled motions. For the forced motion, we resort to the well-known numerical techniques and compute chaos maps, Poincare maps, and bifurcation diagrams. Numerical results are presented for the two-degrees-of-freedom RP and RR robots, and we show that these robot equations can exhibit chaos for low controller gains and for large underestimated models. From the bifurcation diagrams, the route to chaos appears to be through period doubling.

Phase transformation and semiconductor-metal transition in thin films of VO2 deposited by low-pressure metalorganic chemical vapor deposition

Thin films of the semiconducting, monoclinic vanadium dioxide, VO2(M) have been prepared on ordinary glass by two methods: directly by low-pressure metalorganic chemical vapor deposition (MOCVD), and by argon-annealing films of the VO2(B) phase deposited by MOCVD. The composition and microstructure of the films have been examined by x-ray diffraction, scanning electron microscopy, and transmission electron microscopy. Films made predominantly of either the B or the M phase, as deposited, can only be obtained over a narrow range of deposition temperatures. At the lower end of this temperature range, the as-deposited films are strongly oriented, although the substrate is glass. This can be understood from the drive to minimize surface energy. Films of the B phase have a platelet morphology, which leads to an unusual microstructure at the lower-deposition temperatures. Those grown at similar to370 degreesC convert to the metallic, rutile (R) phase when annealed at 550 degreesC, whereas those deposited at 420 degreesC transform to the R phase only at 580 degreesC. (When cooled to room temperature, the annealed films convert reversibly from the R phase to the M phase.) Electron microscopy shows that annealing leads to disintegration of the single crystalline VO2(B) platelets into small crystallites of VO2(R), although the platelet morphology is retained. When the annealing temperature is relatively low, these crystallites are nanometer sized. At a higher-annealing temperature, the transformation leads to well-connected and similarly oriented large grains of VO2(R), enveloped in the original platelet. The semiconductor-metal transition near 68 degreesC leads to a large jump in resistivity in all the VO2(M) films, nearly as large as in epitaxial films on single-crystal substrates. When the annealed films contain well-connected large grains, the transition is very sharp. Even when preferred orientation is present, the transition is not as sharp in as-deposited VO2(M), because the crystallites are not densely packed as in annealed VO2(B). However, the high degree of orientation in these films leads to a narrow temperature hysteresis. (C) 2002 American Institute of Physics.

Geometric representations of graphs in low dimension

We give an efficient randomized algorithm to construct a box representation of any graph G on n vertices in $1.5 (\Delta + 2) \ln n$ dimensions, where $\Delta$ is the maximum degree of G. We also show that $\boxi(G) \le (\Delta + 2) \ln n$ for any graph G. Our bound is tight up to a factor of $\ln n$. We also show that our randomized algorithm can be derandomized to get a polynomial time deterministic algorithm. Though our general upper bound is in terms of maximum degree $\Delta$, we show that for almost all graphs on n vertices, its boxicity is upper bound by $c\cdot(d_{av} + 1) \ln n$ where d_{av} is the average degree and c is a small constant. Also, we show that for any graph G, $\boxi(G) \le \sqrt{8 n d_{av} \ln n}$, which is tight up to a factor of $b \sqrt{\ln n}$ for a constant b.

Effect of morphology on electrical treeing in low density polyethylene nanocomposites

Influence of polymer morphology on the inception and the growth of electrical trees in unfilled low density polyethylene (LDPE) as well as LDPE filled with 1, 3 and 5% by weight nanoalumina samples stressed with 50 Hz ac voltage has been studied. It is seen that there is a significant improvement in tree inception voltage with filler loading in LDPE filled with nanoparticles. Tree inception voltage increased with the filler loading up to 3% by weight nanoalumina loading and showed a reduction at 5% by weight loading. Change in tree growth patterns from branch to bush as well as a slower tree growth with increase in filler loading in LDPE alumina nanocomposites were observed. The degree of crystallinity and change in crystalline morphology induced by the presence of alumina nanoparticles in LDPE was studied using differential scanning calorimetry (DSC) and scanning electron microscopy (SEM). DSC results show a similar melting behaviour for both unfilled LDPE and LDPE nanocomposites. However, there is a reduction in the degree of crystallinity for LDPE filled with 5% by weight nanoalumina. An increase in lamellae packing with increase in filler loadings and a highly disordered spherulitic structure for LDPE filled with 5% by weight nanoalumina was observed from the SEM images. The slow propagation of tree growth as well as reduction in tree inception voltage with increase in filler loadings were attributed to the morphological changes observed in the LDPE nanocomposites.

Co-liposomes of redox-active alkyl-ferrocene modified low MW branched PEI and DOPE for efficacious gene delivery in serum

Herein, we present six new lipopolymers based on low molecular weight, branched polyethylenimine (BPEI 800 Da) which are hydrophobically modified using ferrocene terminated alkyl tails of variable lengths. The effects of degree of grafting, spacer length and the redox state of ferrocene in the lipopolymers on the self assembly properties were investigated in detail by TEM, AFM, DLS and zeta potential measurements. The assemblies displayed an oxidation induced increase in the size of the aggregates. The co-liposomes comprising the lipopolymer and a helper lipid, 1,2-dioleoyl phosphatidyl ethanolamine (DOPE), showed excellent gene (pDNA) delivery capability in a serum containing environment in two cancer cell lines (HeLa and U251 cells). Optimized formulations showed remarkably higher transfection activity than BPEI (25 kDa) and were also significantly better than a commercial transfection reagent, Lipofectamine 2000 as evidenced from both the luciferase activity and GFP expression analysis. Oxidation of ferrocene in the lipopolymers led to drastically reduced levels of gene transfection which was substantiated by reduced cellular internalization of fluorescently labelled pDNA as detected using confocal microscopy and flow cytometry. Moreover, the transfection inactive oxidized lipopolyplexes could be turned transfection active by exposure to ascorbic acid (AA) in cell culture medium during transfection. Endocytosis inhibition experiments showed that gene expression mediated by reduced formulations involved both clathrin and caveolae mediated pathways while the oxidized formulations were routed via the caveolae. Cytotoxicity assays revealed no obvious toxicity for the lipopolyplexes in the range of optimized transfection levels in both the cell lines studied. Overall, we have exploited the redox activity of ferrocene in branched PEI-based efficient polymeric gene carriers whose differential transfection activities could be harnessed for spatial or temporal cellular transfections.

Efficient QR Decomposition Using Low Complexity Column-wise Givens Rotation (CGR)

QR decomposition (QRD) is a widely used Numerical Linear Algebra (NLA) kernel with applications ranging from SONAR beamforming to wireless MIMO receivers. In this paper, we propose a novel Givens Rotation (GR) based QRD (GR QRD) where we reduce the computational complexity of GR and exploit higher degree of parallelism. This low complexity Column-wise GR (CGR) can annihilate multiple elements of a column of a matrix simultaneously. The algorithm is first realized on a Two-Dimensional (2 D) systolic array and then implemented on REDEFINE which is a Coarse Grained run-time Reconfigurable Architecture (CGRA). We benchmark the proposed implementation against state-of-the-art implementations to report better throughput, convergence and scalability.

A mobile robot with a two-degree-of-freedom suspension for traversing uneven terrain with minimal slip: Modeling, simulation and experiments

It is known in literature that a wheeled mobile robot (WMR) with fixed length axle will slip on an uneven terrain. One way to avoid wheel slip is to use a torus-shaped wheel with lateral tilt capability which allows the distance between the wheel-ground contact points to change even with a fixed length axle. Such an arrangement needs a two degree-of-freedom (DOF) suspension for the vertical and lateral tilting motion of the wheel. In this paper modeling, simulation, design and experimentation with a three-wheeled mobile robot, with torus-shaped wheels and a novel two DOF suspension allowing independent lateral tilt and vertical motion, is presented. The suspension is based on a four-bar mechanism and is called the double four-bar (D4Bar) suspension. Numerical simulations show that the three-wheeled mobile robot can traverse uneven terrain with low wheel slip. Experiments with a prototype three-wheeled mobile robot moving on a constructed uneven terrain along a straight line, a circular arc and a path representing a lane change, also illustrate the low slip capability of the three-wheeled mobile robot with the D4Bar suspension. (C) 2015 Elsevier Ltd. All rights reserved.