On the Arrangement of Cliques in Chordal Graphs with respect to the Cuts

A cut (A, B) (where B = V - A) in a graph G = (V, E) is called internal if and only if there exists a vertex x in A that is not adjacent to any vertex in B and there exists a vertex y is an element of B such that it is not adjacent to any vertex in A. In this paper, we present a theorem regarding the arrangement of cliques in a chordal graph with respect to its internal cuts. Our main result is that given any internal cut (A, B) in a chordal graph G, there exists a clique with kappa(G) + vertices (where kappa(G) is the vertex connectivity of G) such that it is (approximately) bisected by the cut (A, B). In fact we give a stronger result: For any internal cut (A, B) of a chordal graph, and for each i, 0 <= i <= kappa(G) + 1 such that vertical bar K-i vertical bar = kappa(G) + 1, vertical bar A boolean AND K-i vertical bar = i and vertical bar B boolean AND K-i vertical bar = kappa(G) + 1 - i. An immediate corollary of the above result is that the number of edges in any internal cut (of a chordal graph) should be Omega(k(2)), where kappa(G) = k. Prompted by this observation, we investigate the size of internal cuts in terms of the vertex connectivity of the chordal graphs. As a corollary, we show that in chordal graphs, if the edge connectivity is strictly less than the minimum degree, then the size of the mincut is at least kappa(G)(kappa(G)+1)/2 where kappa(G) denotes the vertex connectivity. In contrast, in a general graph the size of the mincut can be equal to kappa(G). This result is tight.

Learning dynamic prices in multiseller electronic retail markets with price sensitive customers, stochastic demands, and inventory replenishments

In this paper, we use reinforcement learning (RL) as a tool to study price dynamics in an electronic retail market consisting of two competing sellers, and price sensitive and lead time sensitive customers. Sellers, offering identical products, compete on price to satisfy stochastically arriving demands (customers), and follow standard inventory control and replenishment policies to manage their inventories. In such a generalized setting, RL techniques have not previously been applied. We consider two representative cases: 1) no information case, were none of the sellers has any information about customer queue levels, inventory levels, or prices at the competitors; and 2) partial information case, where every seller has information about the customer queue levels and inventory levels of the competitors. Sellers employ automated pricing agents, or pricebots, which use RL-based pricing algorithms to reset the prices at random intervals based on factors such as number of back orders, inventory levels, and replenishment lead times, with the objective of maximizing discounted cumulative profit. In the no information case, we show that a seller who uses Q-learning outperforms a seller who uses derivative following (DF). In the partial information case, we model the problem as a Markovian game and use actor-critic based RL to learn dynamic prices. We believe our approach to solving these problems is a new and promising way of setting dynamic prices in multiseller environments with stochastic demands, price sensitive customers, and inventory replenishments.

Reinforcement learning applications in dynamic pricing of retail markets

In this paper, we investigate the use of reinforcement learning (RL) techniques to the problem of determining dynamic prices in an electronic retail market. As representative models, we consider a single seller market and a two seller market, and formulate the dynamic pricing problem in a setting that easily generalizes to markets with more than two sellers. We first formulate the single seller dynamic pricing problem in the RL framework and solve the problem using the Q-learning algorithm through simulation. Next we model the two seller dynamic pricing problem as a Markovian game and formulate the problem in the RL framework. We solve this problem using actor-critic algorithms through simulation. We believe our approach to solving these problems is a promising way of setting dynamic prices in multi-agent environments. We illustrate the methodology with two illustrative examples of typical retail markets.

GPU-based normalized cuts for road extraction using satellite imagery

This paper presents a GPU implementation of normalized cuts for road extraction problem using panchromatic satellite imagery. The roads have been extracted in three stages namely pre-processing, image segmentation and post-processing. Initially, the image is pre-processed to improve the tolerance by reducing the clutter (that mostly represents the buildings, vegetation,. and fallow regions). The road regions are then extracted using the normalized cuts algorithm. Normalized cuts algorithm is a graph-based partitioning `approach whose focus lies in extracting the global impression (perceptual grouping) of an image rather than local features. For the segmented image, post-processing is carried out using morphological operations - erosion and dilation. Finally, the road extracted image is overlaid on the original image. Here, a GPGPU (General Purpose Graphical Processing Unit) approach has been adopted to implement the same algorithm on the GPU for fast processing. A performance comparison of this proposed GPU implementation of normalized cuts algorithm with the earlier algorithm (CPU implementation) is presented. From the results, we conclude that the computational improvement in terms of time as the size of image increases for the proposed GPU implementation of normalized cuts. Also, a qualitative and quantitative assessment of the segmentation results has been projected.

On a Special Co-cycle Basis of Graphs

In this paper we consider the problems of computing a minimum co-cycle basis and a minimum weakly fundamental co-cycle basis of a directed graph G. A co-cycle in G corresponds to a vertex partition (S,V ∖ S) and a { − 1,0,1} edge incidence vector is associated with each co-cycle. The vector space over ℚ generated by these vectors is the co-cycle space of G. Alternately, the co-cycle space is the orthogonal complement of the cycle space of G. The minimum co-cycle basis problem asks for a set of co-cycles that span the co-cycle space of G and whose sum of weights is minimum. Weakly fundamental co-cycle bases are a special class of co-cycle bases, these form a natural superclass of strictly fundamental co-cycle bases and it is known that computing a minimum weight strictly fundamental co-cycle basis is NP-hard. We show that the co-cycle basis corresponding to the cuts of a Gomory-Hu tree of the underlying undirected graph of G is a minimum co-cycle basis of G and it is also weakly fundamental.

On measurement of top polarization as a probe of t(t)over-bar production mechanisms at the LHC

In this note we demonstrate the use of top polarization in the study of t (t) over bar resonances at the LHC, in the possible case where the dynamics implies a non-zero top polarization. As a probe of top polarization we construct an asymmetry in the decay-lepton azimuthal angle distribution (corresponding to the sign of cos phi(l)) in the laboratory. The asymmetry is non-vanishing even for a symmetric collider like the LHC, where a positive z axis is not uniquely defined. The angular distribution of the leptons has the advantage of being a faithful top-spin analyzer, unaffected by possible anomalous tbW couplings, to linear order. We study, for purposes of demonstration, the case of a Z' as might exist in the little Higgs models. We identify kinematic cuts which ensure that our asymmetry reflects the polarization in sign and magnitude. We investigate possibilities at the LHC with two energy options: root s = 14TeV and root s = 7TeV, as well as at the Tevatron. At the LHC the model predicts net top quark polarization of the order of a few per cent for M-Z' similar or equal to 1200GeV, being as high as 10% for a smaller mass of the Z' of 700GeV and for the largest allowed coupling in the model, the values being higher for the 7TeV option. These polarizations translate to a deviation from the standard-model value of azimuthal asymmetry of up to about 4% (7%) for 14 (7) TeV LHC, whereas for the Tevatron, values as high as 12% are attained. For the 14TeV LHC with an integrated luminosity of 10 fb(-1), these numbers translate into a 3 sigma sensitivity over a large part of the range 500 less than or similar to M-Z' less than or similar to 1500GeV.

Experimental studies of a distorted turbulent spot in a three-dimensional flow

We report here on the results of a series of experiments carried out on a turbulent spot in a distorted duct to study the effects of a divergence with straight streamlines preceded by a short stretch of transverse streamline curvature, both in the absence of any pressure gradient. It is found that the distortion produces substantial asymmetry in the spot: the angles at which the spot cuts across the local streamlines are altered dramatically (in contradiction of a hypothesis commonly made in transition zone modelling), and the Tollmien-Schlichting waves that accompany the wing tips of the spot are much stronger on the outside of the bend than on the inside. However there is no strong effect on the internal structure of the spot and the eddies therein, or on such propagation characteristics as overall spread rate and the celerities of the leading and trailing edges. Both lateral streamline curvature and non-homogeneity of the laminar boundary layer into which the spot propagates are shown to be strong factors responsible for the observed asymmetry. It is concluded that these factors produce chiefly a geometric distortion of the coherent structure in the spot, but do not otherwise affect its dynamics in any significant way.

Localized data gathering paradigms for small and marginal farm lands in Semi-Arid region – Issues and Concerns

In this work we explore the application of wireless sensor technologies for the benefit of small and marginal farmers in semi-arid regions. The focus in this paper is to discuss the merits and demerits of data gathering & relay paradigms that collect localized data over a wide area. The data gathered includes soil moisture, temperature, pressure, rain data and humidity. The challenge to technology intervention comes mainly due to two reasons: (a) Farmers in general are interested in crop yield specific to their piece of land. This is because soil texture can vary rapidly over small regions. (b) Due to a high run-off, the soil moisture retention can vary from region to region depending on the topology of the farm. Both these reasons alter the needs drastically. Additionally, small and marginal farms can be sandwiched between rich farm lands. The village has very little access to grid power. Power cuts can extend up to 12 hours in a day and upto 3 or 4 days during some months in the year. In this paper, we discuss 3 technology paradigms for data relaying. These include Wi-Fi (Wireless Fidelity), GPRS (General Packet Radio Service) and DTN (Delay and Disruption Tolerant Network) technologies. We detail the merits and demerits of each of these solutions and provide our final recommendations. The project site is a village called Chennakesavapura in the state of Karnataka, India.

DMT of Wireless Networks: An overview

The e�cient operation of single-source, single-sink wireless network is considered with the diversity-multiplexing gain tradeo� (DMT) as the measure of performance. Whereas in the case of a point-to-point MIMO channel the DMT is determined by the fading statistics, in the case of a network, the DMT is additionally, a function of the time schedule according to which the network is operated, as well as the protocol that dictates the mode of operation of the intermediate relays.In general, it is only possible at present, to provide upper bounds on the DMT of the network in terms of the DMT of the MIMO channel appearing across cuts in the network. This paper presents a tutorial overview on the DMT of half-duplex multi-hop wireless networks that also attempts to identify where possible, codes that achieve the DMT.For example, it is shown how one can construct codes that achieve the DMT of a network under a given schedule and either an amplify-and-forward or decode-and-forward protocol. Also contained in the paper,are discussions on the DMT of the multiple-access channel as well as the impact of feedback on the DMT of a MIMO channel.

Efficient Algorithms for Computing All Low s-t Edge Connectivities and Related Problems

Given an undirected unweighted graph G = (V, E) and an integer k ≥ 1, we consider the problem of computing the edge connectivities of all those (s, t) vertex pairs, whose edge connectivity is at most k. We present an algorithm with expected running time Õ(m + nk3) for this problem, where |V| = n and |E| = m. Our output is a weighted tree T whose nodes are the sets V1, V2,..., V l of a partition of V, with the property that the edge connectivity in G between any two vertices s ε Vi and t ε Vj, for i ≠ j, is equal to the weight of the lightest edge on the path between Vi and Vj in T. Also, two vertices s and t belong to the same Vi for any i if and only if they have an edge connectivity greater than k. Currently, the best algorithm for this problem needs to compute all-pairs min-cuts in an O(nk) edge graph; this takes Õ(m + n5/2kmin{k1/2, n1/6}) time. Our algorithm is much faster for small values of k; in fact, it is faster whenever k is o(n5/6). Our algorithm yields the useful corollary that in Õ(m + nc3) time, where c is the size of the global min-cut, we can compute the edge connectivities of all those pairs of vertices whose edge connectivity is at most αc for some constant α. We also present an Õ(m + n) Monte Carlo algorithm for the approximate version of this problem. This algorithm is applicable to weighted graphs as well. Our algorithm, with some modifications, also solves another problem called the minimum T-cut problem. Given T ⊆ V of even cardinality, we present an Õ(m + nk3) algorithm to compute a minimum cut that splits T into two odd cardinality components, where k is the size of this cut.

Banking psychographics: an Indian empirical study

India has been witnessing an economic boom which fuelling a huge growth in the financial sector especially the banks. The spending power and consumerism has been increasing along with the growth in GDP. The numbers of banks are around 3000 (data according to Reserve Bank of India). With a population base of close to 1.1 billion and a diverse culture that has been dictating the mindset and lifestyle of the population, it has been a challenge for the banks to understand the customer better and hence a the need of the hour is a proper psychographic study of retail banking customers.

A unification-based decision procedure for cryptographic protocol analysis

We present a sound and complete decision procedure for the bounded process cryptographic protocol insecurity problem, based on the notion of normal proofs [2] and classical unification. We also show a result about the existence of attacks with “high” normal cuts. Our proof of correctness provides an alternate proof and new insights into the fundamental result of Rusinowitch and Turuani [9] for the same setting.

Jatropha cultivation in southern India: assessing farmers' experiences

Together with 106 farmers who started growing Jatropha (Jatropha curcas L.) in 20042006, this research sought to increase the knowledge around the real-life experience of Jatropha farming in the southern India states of Tamil Nadu and Andhra Pradesh. Launched as an alternative for diesel in India, Jatropha has been promoted as a non-edible plant that could grow on poor soils, yield oil-rich seeds for production of bio-diesel, and not compete directly with food production. Through interviews with the farmers, information was gathered regarding their socio-economic situation, the implementation and performance of their Jatropha plantations, and their reasons for continuing or discontinuing Jatropha cultivation. Results reveal that 82% of the farmers had substituted former cropland for their Jatropha cultivation. By 2010, 85% (n = 90) of the farmers who cultivated Jatropha in 2004 had stopped. Cultivating the crop did not give the economic returns the farmers anticipated, mainly due to a lack of information about the crop and its maintenance during cultivation and due to water scarcity. A majority of the farmers irrigated and applied fertilizer, and even pesticides. Many problems experienced by the farmers were due to limited knowledge about cultivating Jatropha caused by poor planning and implementation of the national Jatropha program. Extension services, subsidies, and other support were not provided as promised. The farmers who continued cultivation had means of income other than Jatropha and held hopes of a future Jatropha market. The lack of market structures, such as purchase agreements and buyers, as well as a low retail price for the seeds, were frequently stated as barriers to Jatropha cultivation. For Jatropha biodiesel to perform well, efforts are needed to improve yield levels and stability through genetic improvements and drought tolerance, as well as agriculture extension services to support adoption of the crop. Government programs will -probably be more effective if implementing biodiesel production is conjoined with stimulating the demand for Jatropha biodiesel. To avoid food-biofuel competition, additional measures may be needed such as land-use restrictions for Jatropha producers and taxes on biofuels or biofuel feedstocks to improve the competitiveness of the food sector compared to the bioenergy sector. (c) 2012 Society of Chemical Industry and John Wiley & Sons, Ltd

A Compliant End-Effector to Passively Limit the Force in Tele-Operated Tissue-Cutting

This paper presents a compliant end-effector that cuts soft tissues and senses the cutting forces. The end-effector is designed to have an upper threshold on cutting forces to facilitate safe handling of tissue during automated cutting. This is demonstrated with nonlinear finite element analysis and experimental results obtained by cutting inhomogeneous phantom tissue. The cutting forces are estimated using a vision-based technique that uses amplified elastic deformation of the compliant end-effector. We also demonstrate an immersive tele-operated tissue-cutting system together with a haptic device that gives real-time force feedback to the user. DOI: 10.1115/1.4007638]

Probing the spin-parity of the Higgs boson via jet kinematics in vector boson fusion

Determining the spin and the parity quantum numbers of the recently discovered Higgs-like boson at the LHC is a matter of great importance. In this Letter, we consider the possibility of using the kinematics of the tagging jets in Higgs production via the vector boson fusion (VBF) process to test the tensor structure of the Higgs-vector boson (HVV) interaction and to determine the spin and CP properties of the observed resonance. We show that an anomalous HVV vertex, in particular its explicit momentum dependence, drastically affects the rapidity between the two scattered quarks and their transverse momenta and, hence, the acceptance of the kinematical cuts that allow to select the VBF topology. The sensitivity of these observables to different spin-parity assignments, including the dependence on the LHC center of mass energy, are evaluated. In addition, we show that in associated Higgs production with a vector boson some kinematical variables, such as the invariant mass of the system and the transverse momenta of the two bosons and their separation in rapidity, are also sensitive to the spin-parity assignments of the Higgs-like boson.