OpenRaiser/Intern-Atlas huggingface dataset:
Resource Allocation for Coordinated Multipoint Networks with Wireless Information and Power Transfer
Venue: arXiv cs.IT 2014
Year: 2014

This paper studies the resource allocation algorithm design for multiuser coordinated multipoint (CoMP) networks with simultaneous wireless information and power transfer (SWIPT). In particular, remote radio heads (RRHs) are connected to a central processor (CP) via capacity-limited backhaul links to facilitate CoMP joint transmission. Besides, the CP transfers energy to the RRHs for more efficient network operation. The considered resource allocation algorithm design is formulated as a non-convex optimization problem with a minimum required signal-to-interference-plus-noise ratio (SINR) constraint at multiple information receivers and a minimum required power transfer constraint at the energy harvesting receivers. By optimizing the transmit beamforming vectors at the CP and energy sharing between the CP and the RRHs, we aim at jointly minimizing the total network transmit power and the maximum capacity consumption per backhaul link. The resulting non-convex optimization problem is NP-hard. In light of the intractability of the problem, we reformulate it by replacing the non-convex objective function with its convex hull, which enables the derivation of an efficient iterative resource allocation algorithm. In each iteration, a non-convex optimization problem is solved by semi-definite programming (SDP) relaxation and the proposed iterative algorithm converges to a local optimal solution of the original problem. Simulation results illustrate that our proposed algorithm achieves a close-to-optimal performance and provides a significant reduction in backhaul capacity consumption compared to full cooperation. Besides, the considered CoMP network is shown to provide superior system performance as far as power consumption is concerned compared to a traditional system with multiple antennas co-located.
Block Motion Based Dynamic Texture Analysis: A Review
Venue: arXiv cs.CV 2014
Year: 2014

Dynamic texture refers to image sequences of non-rigid objects that exhibit some regularity in their movement. Videos of smoke, fire etc. fall under the category of dynamic texture. Researchers have investigated different ways to analyze dynamic textures since early nineties. Both appearance based (image intensities) and motion based approaches are investigated. Motion based approaches turn out to be more effective. A group of researchers have investigated ways to utilize the motion vectors readily available with the blocks in video codes like MGEG/H26X. In this paper we provide a review of the dynamic texture analysis methods using block motion. Research into dynamic texture analysis using block motion includes recognition, motion computation, segmentation, and synthesis. We provide a comprehensive review of these approaches.
On Compressive Sensing in Coding Problems: A Rigorous Approach
Venue: arXiv cs.IT 2014
Year: 2014

We take an information theoretic perspective on a classical sparse-sampling noisy linear model and present an analytical expression for the mutual information, which plays central role in a variety of communications/processing problems. Such an expression was addressed previously either by bounds, by simulations and by the (non-rigorous) replica method. The expression of the mutual information is based on techniques used in [1], addressing the minimum mean square error (MMSE) analysis. Using these expressions, we study specifically a variety of sparse linear communications models which include coding in different settings, accounting also for multiple access channels and different wiretap problems. For those, we provide single-letter expressions and derive achievable rates, capturing the communications/processing features of these timely models.
Probabilistic Analysis of Power Assignments
Venue: arXiv cs.DS 2014
Year: 2014

A fundamental problem for wireless ad hoc networks is the assignment of suitable transmission powers to the wireless devices such that the resulting communication graph is connected. The goal is to minimize the total transmit power in order to maximize the life-time of the network. Our aim is a probabilistic analysis of this power assignment problem. We prove complete convergence for arbitrary combinations of the dimension d and the distance-power gradient p. Furthermore, we prove that the expected approximation ratio of the simple spanning tree heuristic is strictly less than its worst-case ratio of 2. Our main technical novelties are two-fold: First, we find a way to deal with the unbounded degree that the communication network induced by the optimal power assignment can have. Minimum spanning trees and traveling salesman tours, for which strong concentration results are known in Euclidean space, have bounded degree, which is heavily exploited in their analysis. Second, we apply a recent generalization of Azuma-Hoeffding's inequality to prove complete convergence for the case p>=d for both power assignments and minimum spanning trees (MSTs). As far as we are aware, complete convergence for $p > d$ has not been proved yet for any Euclidean functional.
AIS-INMACA: A Novel Integrated MACA Based Clonal Classifier for Protein Coding and Promoter Region Prediction
Venue: arXiv cs.CE 2014
Year: 2014

Most of the problems in bioinformatics are now the challenges in computing. This paper aims at building a classifier based on Multiple Attractor Cellular Automata (MACA) which uses fuzzy logic. It is strengthened with an artificial Immune System Technique (AIS), Clonal algorithm for identifying a protein coding and promoter region in a given DNA sequence. The proposed classifier is named as AIS-INMACA introduces a novel concept to combine CA with artificial immune system to produce a better classifier which can address major problems in bioinformatics. This will be the first integrated algorithm which can predict both promoter and protein coding regions. To obtain good fitness rules the basic concept of Clonal selection algorithm was used. The proposed classifier can handle DNA sequences of lengths 54,108,162,252,354. This classifier gives the exact boundaries of both protein and promoter regions with an average accuracy of 89.6%. This classifier was tested with 97,000 data components which were taken from Fickett & Toung, MPromDb, and other sequences from a renowned medical university. This proposed classifier can handle huge data sets and can find protein and promoter regions even in mixed and overlapped DNA sequences. This work also aims at identifying the logicality between the major problems in bioinformatics and tries to obtaining a common frame work for addressing major problems in bioinformatics like protein structure prediction, RNA structure prediction, predicting the splicing pattern of any primary transcript and analysis of information content in DNA, RNA, protein sequences and structure. This work will attract more researchers towards application of CA as a potential pattern classifier to many important problems in bioinformatics
Parameterized Construction of Program Representations for Sparse Dataflow Analyses
Venue: arXiv cs.PL 2014
Year: 2014

Data-flow analyses usually associate information with control flow regions. Informally, if these regions are too small, like a point between two consecutive statements, we call the analysis dense. On the other hand, if these regions include many such points, then we call it sparse. This paper presents a systematic method to build program representations that support sparse analyses. To pave the way to this framework we clarify the bibliography about well-known intermediate program representations. We show that our approach, up to parameter choice, subsumes many of these representations, such as the SSA, SSI and e-SSA forms. In particular, our algorithms are faster, simpler and more frugal than the previous techniques used to construct SSI - Static Single Information - form programs. We produce intermediate representations isomorphic to Choi et al.'s Sparse Evaluation Graphs (SEG) for the family of data-flow problems that can be partitioned per variables. However, contrary to SEGs, we can handle - sparsely - problems that are not in this family.
File System Design Approaches
Venue: arXiv cs.OS 2014
Year: 2014

In this article, the file system development design approaches are discussed. The selection of the file system design approach is done according to the needs of the developers what are the needed requirements and specifications for the new design. It allowed us to identify where our proposal fitted in with relation to current and past file system development. Our experience with file system development is limited so the research served to identify the different techniques that can be used. The variety of file systems encountered show what an active area of research file system development is. The file systems may be from one of the two fundamental categories. In one category, the file system is developed in user space and runs as a user process. Another file system may be developed in the kernel space and runs as a privileged process. Another one is the mixed approach in which we can take the advantages of both aforesaid approaches. Each development option has its own pros and cons. In this article, these design approaches are discussed.
Brief Announcement: Almost-Tight Approximation Distributed Algorithm for Minimum Cut
Venue: arXiv cs.DS 2014
Year: 2014

In this short paper, we present an improved algorithm for approximating the minimum cut on distributed (CONGEST) networks. Let $λ$ be the minimum cut. Our algorithm can compute $λ$ exactly in $\tilde{O}((\sqrt{n}+D)\poly(λ))$ time, where $n$ is the number of nodes (processors) in the network, $D$ is the network diameter, and $\tilde{O}$ hides $\poly\log n$. By a standard reduction, we can convert this algorithm into a $(1+ε)$-approximation $\tilde{O}((\sqrt{n}+D)/\poly(ε))$-time algorithm. The latter result improves over the previous $(2+ε)$-approximation $\tilde{O}((\sqrt{n}+D)/\poly(ε))$-time algorithm of Ghaffari and Kuhn [DISC 2013]. Due to the lower bound of $\tildeΩ(\sqrt{n}+D)$ by Das Sarma et al. [SICOMP 2013], this running time is {\em tight} up to a $\poly\log n$ factor. Our algorithm is an extremely simple combination of Thorup's tree packing theorem [Combinatorica 2007], Kutten and Peleg's tree partitioning algorithm [J. Algorithms 1998], and Karger's dynamic programming [JACM 2000].
Problem Complexity in Parallel Problem Solving
Venue: arXiv cs.SI 2014
Year: 2014

Recent works examine the relationship between the communication structure and the performance of a group in a problem solving task. Some conclude that inefficient communication networks with long paths outperform efficient networks on the long run. Others find no influence of the network topology on group performance. We contribute to this discussion by examining the role of problem complexity. In particular, we study whether and how the complexity of the problem at hand moderates the influence of the communication network on group performance. Results obtained from multi-agent modelling suggest that problem complexity indeed has an influence. We observe an influence of the network only for problems of moderate difficulty. For easier or harder problems, the influence of network topology becomes weaker or irrelevant, which offers a possible explanation for inconsistencies in the literature.
Finding Shortest Paths between Graph Colourings
Venue: arXiv cs.CC 2014
Year: 2014

The $k$-colouring reconfiguration problem asks whether, for a given graph $G$, two proper $k$-colourings $α$ and $β$ of $G$, and a positive integer $\ell$, there exists a sequence of at most $\ell+1$ proper $k$-colourings of $G$ which starts with $α$ and ends with $β$ and where successive colourings in the sequence differ on exactly one vertex of $G$. We give a complete picture of the parameterized complexity of the $k$-colouring reconfiguration problem for each fixed $k$ when parameterized by $\ell$. First we show that the $k$-colouring reconfiguration problem is polynomial-time solvable for $k=3$, settling an open problem of Cereceda, van den Heuvel and Johnson. Then, for all $k \geq 4$, we show that the $k$-colouring reconfiguration problem, when parameterized by $\ell$, is fixed-parameter tractable (addressing a question of Mouawad, Nishimura, Raman, Simjour and Suzuki) but that it has no polynomial kernel unless the polynomial hierarchy collapses.
Modify-and-Forward for Securing Cooperative Relay Communications
Venue: arXiv cs.IT 2014
Year: 2014

We proposed a new physical layer technique that can enhance the security of cooperative relay communications. The proposed approach modifies the decoded message at the relay according to the unique channel state between the relay and the destination such that the destination can utilize the modified message to its advantage while the eavesdropper cannot. We present a practical method for securely sharing the modification rule between the legitimate partners and present the secrecy outage probability in a quasi-static fading channel. It is demonstrated that the proposed scheme can provide a significant improvement over other schemes when the relay can successfully decode the source message.
Pivot Sampling in Dual-Pivot Quicksort
Venue: arXiv cs.DS 2014
Year: 2014

The new dual-pivot Quicksort by Vladimir Yaroslavskiy - used in Oracle's Java runtime library since version 7 - features intriguing asymmetries in its behavior. They were shown to cause a basic variant of this algorithm to use less comparisons than classic single-pivot Quicksort implementations. In this paper, we extend the analysis to the case where the two pivots are chosen as fixed order statistics of a random sample and give the precise leading term of the average number of comparisons, swaps and executed Java Bytecode instructions. It turns out that - unlike for classic Quicksort, where it is optimal to choose the pivot as median of the sample - the asymmetries in Yaroslavskiy's algorithm render pivots with a systematic skew more efficient than the symmetric choice. Moreover, the optimal skew heavily depends on the employed cost measure; most strikingly, abstract costs like the number of swaps and comparisons yield a very different result than counting Java Bytecode instructions, which can be assumed most closely related to actual running time.
QCMC: Quasi-conformal Parameterizations for Multiply-connected domains
Venue: arXiv cs.CG 2014
Year: 2014

This paper presents a method to compute the {\it quasi-conformal parameterization} (QCMC) for a multiply-connected 2D domain or surface. QCMC computes a quasi-conformal map from a multiply-connected domain $S$ onto a punctured disk $D_S$ associated with a given Beltrami differential. The Beltrami differential, which measures the conformality distortion, is a complex-valued function $μ:S\to\mathbb{C}$ with supremum norm strictly less than 1. Every Beltrami differential gives a conformal structure of $S$. Hence, the conformal module of $D_S$, which are the radii and centers of the inner circles, can be fully determined by $μ$, up to a Möbius transformation. In this paper, we propose an iterative algorithm to simultaneously search for the conformal module and the optimal quasi-conformal parameterization. The key idea is to minimize the Beltrami energy subject to the boundary constraints. The optimal solution is our desired quasi-conformal parameterization onto a punctured disk. The parameterization of the multiply-connected domain simplifies numerical computations and has important applications in various fields, such as in computer graphics and vision. Experiments have been carried out on synthetic data together with real multiply-connected Riemann surfaces. Results show that our proposed method can efficiently compute quasi-conformal parameterizations of multiply-connected domains and outperforms other state-of-the-art algorithms. Applications of the proposed parameterization technique have also been explored.
Time Of Arrival Based Localization in Wireless Sensor Networks : A Linear Approach
Venue: arXiv cs.NI 2014
Year: 2014

In this paper, we aim to determine the location information of a node deployed in Wireless Sensor Networks (WSN). We estimate the position of an unknown source node using localization based on linear approach on a single simulation platform. The Cramer Rao Lower Bound (CRLB) for position estimate is derived first and the four linear approaches namely Linear Least Squares (LLS), Subspace Approach (SA), Weighted Linear Least Squares (WLLS) and Two-step WLS have been derived and presented. Based on the simulation study the results have been compared. The simulation results show that the Two- step WLS approach is having higher localization accuracy. Keywords: Source Localization, Time of Arrival,Linear Least Squares, Subspace Approach, Weighted Linear Least Squares, Two-step WLS and CRLB.
Compensating Demand Response Participants Via Their Shapley Values
Venue: arXiv cs.GT 2014
Year: 2014

Designing fair compensation mechanisms for demand response (DR) is challenging. This paper models the problem in a game theoretic setting and designs a payment distribution mechanism based on the Shapley Value. As exact computation of the Shapley Value is in general intractable, we propose estimating it using a reinforcement learning algorithm that approximates optimal stratified sampling. We apply this algorithm to two DR programs that utilize the Shapley Value for payments and quantify the accuracy of the resulting estimates.
A New Approach to User Scheduling in Massive Multi-User MIMO Broadcast Channels
Venue: arXiv cs.IT 2014
Year: 2014

In this paper, a new user-scheduling-and-beamforming method is proposed for multi-user massive multiple-input multiple-output (massive MIMO) broadcast channels in the context of two-stage beamforming. The key ideas of the proposed scheduling method are 1) to use a set of orthogonal reference beams and construct a double cone around each reference beam to select `nearly-optimal' semi-orthogonal users based only on channel quality indicator (CQI) feedback and 2) to apply post-user-selection beam refinement with zero-forcing beamforming (ZFBF) based on channel state information (CSI) feedback only from the selected users. It is proved that the proposed scheduling-and-beamforming method is asymptotically optimal as the number of users increases. Furthermore, the proposed scheduling-and-beamforming method almost achieves the performance of the existing semi-orthogonal user selection with ZFBF (SUS-ZFBF) that requires full CSI feedback from all users, with significantly reduced feedback overhead which is even less than that required by random beamforming.
Tree-depth and Vertex-minors
Venue: arXiv cs.DM 2014
Year: 2014

In a recent paper, Kwon and Oum claim that every graph of bounded rank-width is a pivot-minor of a graph of bounded tree-width (while the converse has been known true already before). We study the analogous questions for "depth" parameters of graphs, namely for the tree-depth and related new shrub-depth. We show that shrub-depth is monotone under taking vertex-minors, and that every graph class of bounded shrub-depth can be obtained via vertex-minors of graphs of bounded tree-depth. We also consider the same questions for bipartite graphs and pivot-minors.
Defining and computing persistent Z-homology in the general case
Venue: arXiv cs.CG 2014
Year: 2014

By general case we mean methods able to process simplicial sets and chain complexes not of finite type. A filtration of the object to be studied is the heart of both subjects persistent homology and spectral sequences. In this paper we present the complete relation between them, both from theoretical and computational points of view. One of the main contributions of this paper is the observation that a slight modification of our previous programs computing spectral sequences is enough to compute also persistent homology. By inheritance from our spectral sequence programs, we obtain for free persistent homology programs applicable to spaces not of finite type (provided they are spaces with effective homology) and with Z-coefficients (significantly generalizing the usual presentation of persistent homology over a field). As an illustration, we compute some persistent homology groups (and the corresponding integer barcodes) in the case of a Postnikov tower.
Conclusions from a NAIVE Bayes Operator Predicting the Medicare 2011 Transaction Data Set
Venue: arXiv cs.LG 2014
Year: 2014

Introduction: The United States Federal Government operates one of the worlds largest medical insurance programs, Medicare, to ensure payment for clinical services for the elderly, illegal aliens and those without the ability to pay for their care directly. This paper evaluates the Medicare 2011 Transaction Data Set which details the transfer of funds from Medicare to private and public clinical care facilities for specific clinical services for the operational year 2011. Methods: Data mining was conducted to establish the relationships between reported and computed transaction values in the data set to better understand the drivers of Medicare transactions at a programmatic level. Results: The models averaged 88 for average model accuracy and 38 for average Kappa during training. Some reported classes are highly independent from the available data as their predictability remains stable regardless of redaction of supporting and contradictory evidence. DRG or procedure type appears to be unpredictable from the available financial transaction values. Conclusions: Overlay hypotheses such as charges being driven by the volume served or DRG being related to charges or payments is readily false in this analysis despite 28 million Americans being billed through Medicare in 2011 and the program distributing over 70 billion in this transaction set alone. It may be impossible to predict the dependencies and data structures the payer of last resort without data from payers of first and second resort. Political concerns about Medicare would be better served focusing on these first and second order payer systems as what Medicare costs is not dependent on Medicare itself.
A study on cost behaviors of binary classification measures in class-imbalanced problems
Venue: arXiv cs.LG 2014
Year: 2014

This work investigates into cost behaviors of binary classification measures in a background of class-imbalanced problems. Twelve performance measures are studied, such as F measure, G-means in terms of accuracy rates, and of recall and precision, balance error rate (BER), Matthews correlation coefficient (MCC), Kappa coefficient, etc. A new perspective is presented for those measures by revealing their cost functions with respect to the class imbalance ratio. Basically, they are described by four types of cost functions. The functions provides a theoretical understanding why some measures are suitable for dealing with class-imbalanced problems. Based on their cost functions, we are able to conclude that G-means of accuracy rates and BER are suitable measures because they show "proper" cost behaviors in terms of "a misclassification from a small class will cause a greater cost than that from a large class". On the contrary, F1 measure, G-means of recall and precision, MCC and Kappa coefficient measures do not produce such behaviors so that they are unsuitable to serve our goal in dealing with the problems properly.