A constant factor approximation algorithm for boxicity of circular arc graphs

The boxicity (resp. cubicity) of a graph G(V, E) is the minimum integer k such that G can be represented as the intersection graph of axis parallel boxes (resp. cubes) in R-k. Equivalently, it is the minimum number of interval graphs (resp. unit interval graphs) on the vertex set V, such that the intersection of their edge sets is E. The problem of computing boxicity (resp. cubicity) is known to be inapproximable, even for restricted graph classes like bipartite, co-bipartite and split graphs, within an O(n(1-epsilon))-factor for any epsilon > 0 in polynomial time, unless NP = ZPP. For any well known graph class of unbounded boxicity, there is no known approximation algorithm that gives n(1-epsilon)-factor approximation algorithm for computing boxicity in polynomial time, for any epsilon > 0. In this paper, we consider the problem of approximating the boxicity (cubicity) of circular arc graphs intersection graphs of arcs of a circle. Circular arc graphs are known to have unbounded boxicity, which could be as large as Omega(n). We give a (2 + 1/k) -factor (resp. (2 + log n]/k)-factor) polynomial time approximation algorithm for computing the boxicity (resp. cubicity) of any circular arc graph, where k >= 1 is the value of the optimum solution. For normal circular arc (NCA) graphs, with an NCA model given, this can be improved to an additive two approximation algorithm. The time complexity of the algorithms to approximately compute the boxicity (resp. cubicity) is O(mn + n(2)) in both these cases, and in O(mn + kn(2)) = O(n(3)) time we also get their corresponding box (resp. cube) representations, where n is the number of vertices of the graph and m is its number of edges. Our additive two approximation algorithm directly works for any proper circular arc graph, since their NCA models can be computed in polynomial time. (C) 2014 Elsevier B.V. All rights reserved.

Fixed-orientation equilateral triangle matching of point sets

Given a point set P and a class C of geometric objects, G(C)(P) is a geometric graph with vertex set P such that any two vertices p and q are adjacent if and only if there is some C is an element of C containing both p and q but no other points from P. We study G(del)(P) graphs where del is the class of downward equilateral triangles (i.e., equilateral triangles with one of their sides parallel to the x-axis and the corner opposite to this side below that side). For point sets in general position, these graphs have been shown to be equivalent to half-Theta(6) graphs and TD-Delaunay graphs. The main result in our paper is that for point sets P in general position, G(del)(P) always contains a matching of size at least vertical bar P vertical bar-1/3] and this bound is tight. We also give some structural properties of G(star)(P) graphs, where is the class which contains both upward and downward equilateral triangles. We show that for point sets in general position, the block cut point graph of G(star)(P) is simply a path. Through the equivalence of G(star)(P) graphs with Theta(6) graphs, we also derive that any Theta(6) graph can have at most 5n-11 edges, for point sets in general position. (C) 2013 Elsevier B.V. All rights reserved.

Combining data sets of satellite-retrieved products for basin-scale water balance study: 2. Evaluation on the Mississippi Basin and closure correction model

In this study, we applied the integration methodology developed in the companion paper by Aires (2014) by using real satellite observations over the Mississippi Basin. The methodology provides basin-scale estimates of the four water budget components (precipitation P, evapotranspiration E, water storage change Delta S, and runoff R) in a two-step process: the Simple Weighting (SW) integration and a Postprocessing Filtering (PF) that imposes the water budget closure. A comparison with in situ observations of P and E demonstrated that PF improved the estimation of both components. A Closure Correction Model (CCM) has been derived from the integrated product (SW+PF) that allows to correct each observation data set independently, unlike the SW+PF method which requires simultaneous estimates of the four components. The CCM allows to standardize the various data sets for each component and highly decrease the budget residual (P - E - Delta S - R). As a direct application, the CCM was combined with the water budget equation to reconstruct missing values in any component. Results of a Monte Carlo experiment with synthetic gaps demonstrated the good performances of the method, except for the runoff data that has a variability of the same order of magnitude as the budget residual. Similarly, we proposed a reconstruction of Delta S between 1990 and 2002 where no Gravity Recovery and Climate Experiment data are available. Unlike most of the studies dealing with the water budget closure at the basin scale, only satellite observations and in situ runoff measurements are used. Consequently, the integrated data sets are model independent and can be used for model calibration or validation.

Context dependent non canonical WNT signaling mediates activation of fibroblasts by transforming growth factor-beta

Actions of transforming growth factor-beta are largely context dependent. For instance, TGF-beta is growth inhibitory to epithelial cells and many tumor cell-lines while it stimulates the growth of mesenchymal cells. TGF-beta also activates fibroblast cells to a myofibroblastic phenotype. In order to understand how the responsiveness of fibroblasts to TGF-beta would change in the context of transformation, we have compared the differential gene regulation by TGF-beta in immortal fibroblasts (hFhTERT), transformed fibroblasts (hFhTERT-LTgRAS) and a human fibrosarcoma cell-line (HT1080). The analysis revealed regulation of 6735, 4163, and 3478 probe-sets by TGF-beta in hFhTERT, hFhTERT-LTgRAS and HT1080 cells respectively. Intriguingly, 5291 probe-sets were found to be either regulated in hFhTERT or hFhTERT-LTgRAS cells while 2274 probe-sets were regulated either in hFhTERT or HT1080 cells suggesting that the response of immortal hFhTERT cells to TGF-beta is vastly different compared to the response of both the transformed cells hFhTERT-LTgRAS and HT1080 to TGF-beta. Strikingly, WNT pathway showed enrichment in the hFhTERT cells in Gene Set Enrichment Analysis. Functional studies showed induction of WNT4 by TGF-beta in hFhTERT cells and TGF-beta conferred action of these cells was mediated by WNT4. While TGF-beta activated both canonical and non-canonical WNT pathways in hFhTERT cells, Erk1/2 and p38 Mitogen Activated Protein Kinase pathways were activated in hFhTERT-LTgRAS and HT1080 cells. This suggests that transformation of immortal hFhTERT cells by SV40 large T antigen and activated RAS caused a switch in their response to TGF-beta which matched with the response of HT1080 cells to TGF-beta. These data suggest context dependent activation of non-canonical signaling by TGF-beta. (C) 2015 Published by Elsevier Inc.

Construction of Singer Subgroup Orbit Codes Based on Cyclic Difference Sets

A recent approach for the construction of constant dimension subspace codes, designed for error correction in random networks, is to consider the codes as orbits of suitable subgroups of the general linear group. In particular, a cyclic orbit code is the orbit of a cyclic subgroup. Hence a possible method to construct large cyclic orbit codes with a given minimum subspace distance is to select a subspace such that the orbit of the Singer subgroup satisfies the distance constraint. In this paper we propose a method where some basic properties of difference sets are employed to select such a subspace, thereby providing a systematic way of constructing cyclic orbit codes with specified parameters. We also present an explicit example of such a construction.

NUMERICAL STUDIES OF DYNAMO ACTION IN A TURBULENT SHEAR FLOW. I.

We perform numerical experiments to study the shear dynamo problem where we look for the growth of a large-scale magnetic field due to non-helical stirring at small scales in a background linear shear flow in previously unexplored parameter regimes. We demonstrate the large-scale dynamo action in the limit where the fluid Reynolds number (Re) is below unity while the magnetic Reynolds number (Rm) is above unity; the exponential growth rate scales linearly with shear, which is consistent with earlier numerical works. The limit of low Re is particularly interesting, as seeing the dynamo action in this limit would provide enough motivation for further theoretical investigations, which may focus attention on this analytically more tractable limit of Re < 1 compared to the more formidable limit of Re > 1. We also perform simulations in the regimes where (i) both (Re, Rm) < 1, and (ii) Re > 1 and Rm < 1, and compute all of the components of the turbulent transport coefficients (alpha(ij) and alpha(ij)) using the test-field method. A reasonably good agreement is observed between our results and the results of earlier analytical works in similar parameter regimes.

An Optical How Feature and McFIS Based Approach for 3-Dimensional Human Action Recognition

We propose to develop a 3-D optical flow features based human action recognition system. Optical flow based features are employed here since they can capture the apparent movement in object, by design. Moreover, they can represent information hierarchically from local pixel level to global object level. In this work, 3-D optical flow based features a re extracted by combining the 2-1) optical flow based features with the depth flow features obtained from depth camera. In order to develop an action recognition system, we employ a Meta-Cognitive Neuro-Fuzzy Inference System (McFIS). The m of McFIS is to find the decision boundary separating different classes based on their respective optical flow based features. McFIS consists of a neuro-fuzzy inference system (cognitive component) and a self-regulatory learning mechanism (meta-cognitive component). During the supervised learning, self-regulatory learning mechanism monitors the knowledge of the current sample with respect to the existing knowledge in the network and controls the learning by deciding on sample deletion, sample learning or sample reserve strategies. The performance of the proposed action recognition system was evaluated on a proprietary data set consisting of eight subjects. The performance evaluation with standard support vector machine classifier and extreme learning machine indicates improved performance of McFIS is recognizing actions based of 3-D optical flow based features.

Action Recognition from Motion Capture Data using Meta-cognitive RBF Network Classifier

Action recognition plays an important role in various applications, including smart homes and personal assistive robotics. In this paper, we propose an algorithm for recognizing human actions using motion capture action data. Motion capture data provides accurate three dimensional positions of joints which constitute the human skeleton. We model the movement of the skeletal joints temporally in order to classify the action. The skeleton in each frame of an action sequence is represented as a 129 dimensional vector, of which each component is a 31) angle made by each joint with a fixed point on the skeleton. Finally, the video is represented as a histogram over a codebook obtained from all action sequences. Along with this, the temporal variance of the skeletal joints is used as additional feature. The actions are classified using Meta-Cognitive Radial Basis Function Network (McRBFN) and its Projection Based Learning (PBL) algorithm. We achieve over 97% recognition accuracy on the widely used Berkeley Multimodal Human Action Database (MHAD).

Human action recognition in H.264/AVC compressed domain using meta-cognitive radial basis function network

In this paper, we propose a H.264/AVC compressed domain human action recognition system with projection based metacognitive learning classifier (PBL-McRBFN). The features are extracted from the quantization parameters and the motion vectors of the compressed video stream for a time window and used as input to the classifier. Since compressed domain analysis is done with noisy, sparse compression parameters, it is a huge challenge to achieve performance comparable to pixel domain analysis. On the positive side, compressed domain allows rapid analysis of videos compared to pixel level analysis. The classification results are analyzed for different values of Group of Pictures (GOP) parameter, time window including full videos. The functional relationship between the features and action labels are established using PBL-McRBFN with a cognitive and meta-cognitive component. The cognitive component is a radial basis function, while the meta-cognitive component employs self-regulation to achieve better performance in subject independent action recognition task. The proposed approach is faster and shows comparable performance with respect to the state-of-the-art pixel domain counterparts. It employs partial decoding, which rules out the complexity of full decoding, and minimizes computational load and memory usage. This results in reduced hardware utilization and increased speed of classification. The results are compared with two benchmark datasets and show more than 90% accuracy using the PBL-McRBFN. The performance for various GOP parameters and group of frames are obtained with twenty random trials and compared with other well-known classifiers in machine learning literature. (C) 2015 Elsevier B.V. All rights reserved.

Compressed domain human action recognition in H.264/AVC video streams

This paper discusses a novel high-speed approach for human action recognition in H.264/AVC compressed domain. The proposed algorithm utilizes cues from quantization parameters and motion vectors extracted from the compressed video sequence for feature extraction and further classification using Support Vector Machines (SVM). The ultimate goal of the proposed work is to portray a much faster algorithm than pixel domain counterparts, with comparable accuracy, utilizing only the sparse information from compressed video. Partial decoding rules out the complexity of full decoding, and minimizes computational load and memory usage, which can result in reduced hardware utilization and faster recognition results. The proposed approach can handle illumination changes, scale, and appearance variations, and is robust to outdoor as well as indoor testing scenarios. We have evaluated the performance of the proposed method on two benchmark action datasets and achieved more than 85 % accuracy. The proposed algorithm classifies actions with speed (> 2,000 fps) approximately 100 times faster than existing state-of-the-art pixel-domain algorithms.

Unique Covering Problems with Geometric Sets

The Exact Cover problem takes a universe U of n elements, a family F of m subsets of U and a positive integer k, and decides whether there exists a subfamily(set cover) F' of size at most k such that each element is covered by exactly one set. The Unique Cover problem also takes the same input and decides whether there is a subfamily F' subset of F such that at least k of the elements F' covers are covered uniquely(by exactly one set). Both these problems are known to be NP-complete. In the parameterized setting, when parameterized by k, Exact Cover is W1]-hard. While Unique Cover is FPT under the same parameter, it is known to not admit a polynomial kernel under standard complexity-theoretic assumptions. In this paper, we investigate these two problems under the assumption that every set satisfies a given geometric property Pi. Specifically, we consider the universe to be a set of n points in a real space R-d, d being a positive integer. When d = 2 we consider the problem when. requires all sets to be unit squares or lines. When d > 2, we consider the problem where. requires all sets to be hyperplanes in R-d. These special versions of the problems are also known to be NP-complete. When parameterizing by k, the Unique Cover problem has a polynomial size kernel for all the above geometric versions. The Exact Cover problem turns out to be W1]-hard for squares, but FPT for lines and hyperplanes. Further, we also consider the Unique Set Cover problem, which takes the same input and decides whether there is a set cover which covers at least k elements uniquely. To the best of our knowledge, this is a new problem, and we show that it is NP-complete (even for the case of lines). In fact, the problem turns out to be W1]-hard in the abstract setting, when parameterized by k. However, when we restrict ourselves to the lines and hyperplanes versions, we obtain FPT algorithms.

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.

The cis-Diammineplatinum(II) Complex of Curcumin: A Dual Action DNA Crosslinking and Photochemotherapeutic Agent

Pt(cur)(NH3)(2)](NO3) (1), a curcumin-bound cis-diammineplatinum(II) complex, nicknamed Platicur, as a novel photoactivated chemotherapeutic agent releases photoactive curcumin and an active platinum(II) species upon irradiation with visible light. The hydrolytic instability of free curcumin reduces upon binding to platinum(II). Interactions of 1 with 5'-GMP and ct-DNA indicated formation of platinum-bound DNA adducts upon exposure to visible light (lambda = 400-700 nm). It showed apoptotic photocytotoxicity in cancer cells (IC50 approximate to 15 mu M), thus forming (OH)-O-center dot, while remaining passive in the darkness (IC50 > 200 mu M). A comet assay and platinum estimation suggest Pt-DNA crosslink formation. The fluorescence microscopic images showed cytosolic localization of curcumin, thus implying possibility of dual action as a chemo-and phototherapeutic agent.

Action of Hopf on the twisted modular Hecke operator

Let Gamma subset of SL2(Z) be a principal congruence subgroup. For each sigma is an element of SL2(Z), we introduce the collection A(sigma)(Gamma) of modular Hecke operators twisted by sigma. Then, A(sigma)(Gamma) is a right A(Gamma)-module, where A(Gamma) is the modular Hecke algebra introduced by Connes and Moscovici. Using the action of a Hopf algebra h(0) on A(sigma)(Gamma), we define reduced Rankin-Cohen brackets on A(sigma)(Gamma). Moreover A(sigma)(Gamma) carries an action of H 1, where H 1 is the Hopf algebra of foliations of codimension 1. Finally, we consider operators between the levels A(sigma)(Gamma), sigma is an element of SL2(Z). We show that the action of these operators can be expressed in terms of a Hopf algebra h(Z).

Asymptotic behavior and interpretation of virtual states: The effects of confinement and of basis sets

A real-space high order finite difference method is used to analyze the effect of spherical domain size on the Hartree-Fock (and density functional theory) virtual eigenstates. We show the domain size dependence of both positive and negative virtual eigenvalues of the Hartree-Fock equations for small molecules. We demonstrate that positive states behave like a particle in spherical well and show how they approach zero. For the negative eigenstates, we show that large domains are needed to get the correct eigenvalues. We compare our results to those of Gaussian basis sets and draw some conclusions for real-space, basis-sets, and plane-waves calculations. (C) 2016 AIP Publishing LLC.