Complexity of distance paired-domination problem in graphs

Suppose G = (V, E) is a simple graph and k is a fixed positive integer. A subset D subset of V is a distance k-dominating set of G if for every u is an element of V. there exists a vertex v is an element of D such that d(G)(u, v) <= k, where d(G)(u, v) is the distance between u and v in G. A set D subset of V is a distance k-paired-dominating set of G if D is a distance k-dominating set and the induced subgraph GD] contains a perfect matching. Given a graph G = (V, E) and a fixed integer k > 0, the MIN DISTANCE k-PAIRED-DOM SET problem is to find a minimum cardinality distance k-paired-dominating set of G. In this paper, we show that the decision version of MIN DISTANCE k-PAIRED-DOM SET iS NP-complete for undirected path graphs. This strengthens the complexity of decision version Of MIN DISTANCE k-PAIRED-DOM SET problem in chordal graphs. We show that for a given graph G, unless NP subset of DTIME (n(0)((log) (log) (n)) MIN DISTANCE k-PAIRED-Dom SET problem cannot be approximated within a factor of (1 -epsilon ) In n for any epsilon > 0, where n is the number of vertices in G. We also show that MIN DISTANCE k-PAIRED-DOM SET problem is APX-complete for graphs with degree bounded by 3. On the positive side, we present a linear time algorithm to compute the minimum cardinality of a distance k-paired-dominating set of a strongly chordal graph G if a strong elimination ordering of G is provided. We show that for a given graph G, MIN DISTANCE k-PAIRED-DOM SET problem can be approximated with an approximation factor of 1 + In 2 + k . In(Delta(G)), where Delta(G) denotes the maximum degree of G. (C) 2012 Elsevier B.V All rights reserved.

TURBULENT PUMPING OF MAGNETIC FLUX REDUCES SOLAR CYCLE MEMORY AND THUS IMPACTS PREDICTABILITY OF THE SUN'S ACTIVITY

Prediction of the Sun's magnetic activity is important because of its effect on space environment and climate. However, recent efforts to predict the amplitude of the solar cycle have resulted in diverging forecasts with no consensus. Yeates et al. have shown that the dynamical memory of the solar dynamo mechanism governs predictability, and this memory is different for advection- and diffusion-dominated solar convection zones. By utilizing stochastically forced, kinematic dynamo simulations, we demonstrate that the inclusion of downward turbulent pumping of magnetic flux reduces the memory of both advection- and diffusion-dominated solar dynamos to only one cycle; stronger pumping degrades this memory further. Thus, our results reconcile the diverging dynamo-model-based forecasts for the amplitude of solar cycle 24. We conclude that reliable predictions for the maximum of solar activity can be made only at the preceding minimum-allowing about five years of advance planning for space weather. For more accurate predictions, sequential data assimilation would be necessary in forecasting models to account for the Sun's short memory.

A note on the inverse mode shape problem for bars, beams, and plates

Motivated by the idea of designing a structure for a desired mode shape, intended towards applications such as resonant sensors, actuators and vibration confinement, we present the inverse mode shape problem for bars, beams and plates in this work. The objective is to determine the cross-sectional profile of these structures, given a mode shape, boundary condition and the mass. The contribution of this article is twofold: (i) A numerical method to solve this problem when a valid mode shape is provided in the finite element framework for both linear and nonlinear versions of the problem. (ii) An analytical result to prove the uniqueness and existence of the solution in the case of bars. This article also highlights a very important question of the validity of a mode shape for any structure of given boundary conditions.

Active Sequential Hypothesis Testing with Application to a Visual Search Problem

We consider a visual search problem studied by Sripati and Olson where the objective is to identify an oddball image embedded among multiple distractor images as quickly as possible. We model this visual search task as an active sequential hypothesis testing problem (ASHT problem). Chernoff in 1959 proposed a policy in which the expected delay to decision is asymptotically optimal. The asymptotics is under vanishing error probabilities. We first prove a stronger property on the moments of the delay until a decision, under the same asymptotics. Applying the result to the visual search problem, we then propose a ``neuronal metric'' on the measured neuronal responses that captures the discriminability between images. From empirical study we obtain a remarkable correlation (r = 0.90) between the proposed neuronal metric and speed of discrimination between the images. Although this correlation is lower than with the L-1 metric used by Sripati and Olson, this metric has the advantage of being firmly grounded in formal decision theory.

Relay Selection for Geographical Forwarding in Sleep-Wake Cycling Wireless Sensor Networks

Our work is motivated by geographical forwarding of sporadic alarm packets to a base station in a wireless sensor network (WSN), where the nodes are sleep-wake cycling periodically and asynchronously. We seek to develop local forwarding algorithms that can be tuned so as to tradeoff the end-to-end delay against a total cost, such as the hop count or total energy. Our approach is to solve, at each forwarding node enroute to the sink, the local forwarding problem of minimizing one-hop waiting delay subject to a lower bound constraint on a suitable reward offered by the next-hop relay; the constraint serves to tune the tradeoff. The reward metric used for the local problem is based on the end-to-end total cost objective (for instance, when the total cost is hop count, we choose to use the progress toward sink made by a relay as the reward). The forwarding node, to begin with, is uncertain about the number of relays, their wake-up times, and the reward values, but knows the probability distributions of these quantities. At each relay wake-up instant, when a relay reveals its reward value, the forwarding node's problem is to forward the packet or to wait for further relays to wake-up. In terms of the operations research literature, our work can be considered as a variant of the asset selling problem. We formulate our local forwarding problem as a partially observable Markov decision process (POMDP) and obtain inner and outer bounds for the optimal policy. Motivated by the computational complexity involved in the policies derived out of these bounds, we formulate an alternate simplified model, the optimal policy for which is a simple threshold rule. We provide simulation results to compare the performance of the inner and outer bound policies against the simple policy, and also against the optimal policy when the source knows the exact number of relays. Observing the good performance and the ease of implementation of the simple policy, we apply it to our motivating problem, i.e., local geographical routing of sporadic alarm packets in a large WSN. We compare the end-to-end performance (i.e., average total delay and average total cost) obtained by the simple policy, when used for local geographical forwarding, against that obtained by the globally optimal forwarding algorithm proposed by Kim et al. 1].

On the Erdos-Szekeres n-interior point problem

The n-interior point variant of the Erdos-Szekeres problem is to show the following: For any n, n-1, every point set in the plane with sufficient number of interior points contains a convex polygon containing exactly n-interior points. This has been proved only for n-3. In this paper, we prove it for pointsets having atmost logarithmic number of convex layers. We also show that any pointset containing atleast n interior points, there exists a 2-convex polygon that contains exactly n-interior points.

Duty cycling and power management with a network of energy harvesting sensors

In this paper, we study duty cycling and power management in a network of energy harvesting sensor (EHS) nodes. We consider a one-hop network, where K EHS nodes send data to a destination over a wireless fading channel. The goal is to find the optimum duty cycling and power scheduling across the nodes that maximizes the average sum data rate, subject to energy neutrality at each node. We adopt a two-stage approach to simplify the problem. In the inner stage, we solve the problem of optimal duty cycling of the nodes, subject to the short-term power constraint set by the outer stage. The outer stage sets the short-term power constraints on the inner stage to maximize the long-term expected sum data rate, subject to long-term energy neutrality at each node. Albeit suboptimal, our solutions turn out to have a surprisingly simple form: the duty cycle allotted to each node by the inner stage is simply the fractional allotted power of that node relative to the total allotted power. The sum power allotted is a clipped version of the sum harvested power across all the nodes. The average sum throughput thus ultimately depends only on the sum harvested power and its statistics. We illustrate the performance improvement offered by the proposed solution compared to other naive schemes via Monte-Carlo simulations.

Optimal control problem for the time-dependent Kirchhoff-Love plate in a domain with rough boundary

In this paper, we study the asymptotic behavior of an optimal control problem for the time-dependent Kirchhoff-Love plate whose middle surface has a very rough boundary. We identify the limit problem which is an optimal control problem for the limit equation with a different cost functional.

High power microwave coupling with a buried twisted pair cable

This paper deals with the coupling of High Power Microwaves with a buried twisted pair cable. The electric field at a distance of 1km from the HPM antenna has been computed and is used for further computation of induced voltage and current. It is found that the peak of the induced current and voltage in a buried unshielded twisted pair cable at a distance of 1km from an HPM antenna of power level 10GW is 20A and 2kV respectively.

Comparison of one cycle control of charge and current for bi-directional boost rectifiers

Classical control and one cycle control of current are popular methods used to modulate pulses in active rectifiers for ac-dc power conversion. One cycle control has lower control complexity and can be implemented using linear analog circuits when compared with the classical approach. However, it also suffers from problems such as instability and offsets in current that is severe at light load conditions. A control strategy for bidirectional boost rectifiers based on one cycle control of charge is proposed for that overcomes these limitations. The integral of sensed current, which represents charge, is compared with a non-linear carrier, which is modified for ac-dc power conversion. This generates the gating signals for the switching devices. The modifications required for the control law governing one cycle control of charge is derived in the paper. Detailed simulation studies are carried out to compare one cycle control of current with the proposed method for ac-dc power conversion, which are validated on a laboratory hardware prototype.

An estimate of equilibrium sensitivity of global terrestrial carbon cycle using NCAR CCSM4

Increasing concentrations of atmospheric CO2 influence climate, terrestrial biosphere productivity and ecosystem carbon storage through its radiative, physiological and fertilization effects. In this paper, we quantify these effects for a doubling of CO2 using a low resolution configuration of the coupled model NCAR CCSM4. In contrast to previous coupled climate-carbon modeling studies, we focus on the near-equilibrium response of the terrestrial carbon cycle. For a doubling of CO2, the radiative effect on the physical climate system causes global mean surface air temperature to increase by 2.14 K, whereas the physiological and fertilization on the land biosphere effects cause a warming of 0.22 K, suggesting that these later effects increase global warming by about 10 % as found in many recent studies. The CO2-fertilization leads to total ecosystem carbon gain of 371 Gt-C (28 %) while the radiative effect causes a loss of 131 Gt-C (10 %) indicating that climate warming damps the fertilization-induced carbon uptake over land. Our model-based estimate for the maximum potential terrestrial carbon uptake resulting from a doubling of atmospheric CO2 concentration (285-570 ppm) is only 242 Gt-C. This highlights the limited storage capacity of the terrestrial carbon reservoir. We also find that the terrestrial carbon storage sensitivity to changes in CO2 and temperature have been estimated to be lower in previous transient simulations because of lags in the climate-carbon system. Our model simulations indicate that the time scale of terrestrial carbon cycle response is greater than 500 years for CO2-fertilization and about 200 years for temperature perturbations. We also find that dynamic changes in vegetation amplify the terrestrial carbon storage sensitivity relative to a static vegetation case: because of changes in tree cover, changes in total ecosystem carbon for CO2-direct and climate effects are amplified by 88 and 72 %, respectively, in simulations with dynamic vegetation when compared to static vegetation simulations.

Supercritical carbon dioxide Brayton cycle for concentrated solar power

Supercritical carbon dioxide based Brayton cycle for possible concentrated solar power applications is investigated and compared with trans- and sub-critical operations of the same fluid. Thermal efficiency, specific work output and magnitude of irreversibility generation are used as some of the performance indicators. While the thermal efficiency increases almost linearly with low side pressure in the sub- and trans-critical cycles, it attains a maximum in the supercritical regime at 85 bar after which there are diminishing returns on increasing the low side pressure. It is also found that supercritical cycle is capable of producing power with a thermal efficiency of >30% even at a lower source temperature (820K) and accounting for foreseeable non-idealities albeit with a higher turbine inlet pressure (similar to 300 bar) which is not matched by a conventional sub-critical cycle even with a high source temperature of 978K. The reasons for lower efficiency than in an ideal cycle are extracted from an irreversibility analysis of components, namely, compressor, regenerator, turbine and gas cooler. Low sensitivity to the source temperature and extremely small volumetric flow rates in the supercritical cycle could offset the drawback of high pressures through a compact system.

A novel Q-learning algorithm with function approximation for constrained Markov decision processes

We present a novel multi-timescale Q-learning algorithm for average cost control in a Markov decision process subject to multiple inequality constraints. We formulate a relaxed version of this problem through the Lagrange multiplier method. Our algorithm is different from Q-learning in that it updates two parameters - a Q-value parameter and a policy parameter. The Q-value parameter is updated on a slower time scale as compared to the policy parameter. Whereas Q-learning with function approximation can diverge in some cases, our algorithm is seen to be convergent as a result of the aforementioned timescale separation. We show the results of experiments on a problem of constrained routing in a multistage queueing network. Our algorithm is seen to exhibit good performance and the various inequality constraints are seen to be satisfied upon convergence of the algorithm.

Exact internal controllability for a hyperbolic problem in a domain with highly oscillating boundary

In this paper, by using the Hilbert Uniqueness Method (HUM), we study the exact controllability problem described by the wave equation in a three-dimensional horizontal domain bounded at the bottom by a smooth wall and at the top by a rough wall. The latter is assumed to consist in a plane wall covered with periodically distributed asperities whose size depends on a small parameter epsilon > 0, and with a fixed height. Our aim is to obtain the exact controllability for the homogenized equation. In the process, we study the asymptotic analysis of wave equation in two setups, namely solution by standard weak formulation and solution by transposition method.