OpenRaiser/Intern-Atlas huggingface dataset:
Generalized multiple depot traveling salesmen problem - polyhedral study and exact algorithm
Venue: arXiv cs.DS 2015
Year: 2015

The generalized multiple depot traveling salesmen problem (GMDTSP) is a variant of the multiple depot traveling salesmen problem (MDTSP), where each salesman starts at a distinct depot, the targets are partitioned into clusters and at least one target in each cluster is visited by some salesman. The GMDTSP is an NP-hard problem as it generalizes the MDTSP and has practical applications in design of ring networks, vehicle routing, flexible manufacturing scheduling and postal routing. We present an integer programming formulation for the GMDTSP and valid inequalities to strengthen the linear programming relaxation. Furthermore, we present a polyhedral analysis of the convex hull of feasible solutions to the GMDTSP and derive facet-defining inequalities that strengthen the linear programming relaxation of the GMDTSP. All these results are then used to develop a branch-and-cut algorithm to obtain optimal solutions to the problem. The performance of the algorithm is evaluated through extensive computational experiments on several benchmark instances.
Decomposition and Identification of Linear Structural Equation Models
Venue: arXiv cs.AI 2015
Year: 2015

In this paper, we address the problem of identifying linear structural equation models. We first extend the edge set half-trek criterion to cover a broader class of models. We then show that any semi-Markovian linear model can be recursively decomposed into simpler sub-models, resulting in improved identification power. Finally, we show that, unlike the existing methods developed for linear models, the resulting method subsumes the identification algorithm of non-parametric models.
Crowd Access Path Optimization: Diversity Matters
Venue: arXiv cs.LG 2015
Year: 2015

Quality assurance is one the most important challenges in crowdsourcing. Assigning tasks to several workers to increase quality through redundant answers can be expensive if asking homogeneous sources. This limitation has been overlooked by current crowdsourcing platforms resulting therefore in costly solutions. In order to achieve desirable cost-quality tradeoffs it is essential to apply efficient crowd access optimization techniques. Our work argues that optimization needs to be aware of diversity and correlation of information within groups of individuals so that crowdsourcing redundancy can be adequately planned beforehand. Based on this intuitive idea, we introduce the Access Path Model (APM), a novel crowd model that leverages the notion of access paths as an alternative way of retrieving information. APM aggregates answers ensuring high quality and meaningful confidence. Moreover, we devise a greedy optimization algorithm for this model that finds a provably good approximate plan to access the crowd. We evaluate our approach on three crowdsourced datasets that illustrate various aspects of the problem. Our results show that the Access Path Model combined with greedy optimization is cost-efficient and practical to overcome common difficulties in large-scale crowdsourcing like data sparsity and anonymity.
Ordering Interrogative Questions for Effective Requirements Engineering: The W6H Pattern
Venue: arXiv cs.SE 2015
Year: 2015

Requirements elicitation and requirements analysis are important practices of Requirements Engineering. Elicitation techniques, such as interviews and questionnaires, rely on formulating interrogative questions and asking these in a proper order to maximize the accuracy of the information being gathered. Information gathered during requirements elicitation then has to be interpreted, analyzed, and validated. Requirements analysis involves analyzing the problem and solutions spaces. In this paper, we describe a method to formulate interrogative questions for effective requirements elicitation based on the lexical and semantic principles of the English language interrogatives, and propose a pattern to organize stakeholder viewpoint concerns for better requirements analysis. This helps requirements engineer thoroughly describe problem and solutions spaces. Most of the previous requirements elicitation studies included six out of the seven English language interrogatives 'what', 'where', 'when', 'who', 'why', and 'how' (denoted by W5H) and did not propose any order in the interrogatives. We show that extending the set of six interrogatives with 'which' (denoted by W6H) improves the generation and formulation of questions for requirements elicitation and facilitates better requirements analysis via arranging stakeholder views. We discuss the interdependencies among interrogatives (for requirements engineer to consider while eliciting the requirements) and suggest an order for the set of W6H interrogatives. The proposed W6H-based reusable pattern also aids requirements engineer in organizing viewpoint concerns of stakeholders, making this pattern an effective tool for requirements analysis.
Bidirectional LSTM-CRF Models for Sequence Tagging
Venue: arXiv cs.CL 2015
Year: 2015

In this paper, we propose a variety of Long Short-Term Memory (LSTM) based models for sequence tagging. These models include LSTM networks, bidirectional LSTM (BI-LSTM) networks, LSTM with a Conditional Random Field (CRF) layer (LSTM-CRF) and bidirectional LSTM with a CRF layer (BI-LSTM-CRF). Our work is the first to apply a bidirectional LSTM CRF (denoted as BI-LSTM-CRF) model to NLP benchmark sequence tagging data sets. We show that the BI-LSTM-CRF model can efficiently use both past and future input features thanks to a bidirectional LSTM component. It can also use sentence level tag information thanks to a CRF layer. The BI-LSTM-CRF model can produce state of the art (or close to) accuracy on POS, chunking and NER data sets. In addition, it is robust and has less dependence on word embedding as compared to previous observations.
The graph spectrum of barycentric refinements
Venue: arXiv cs.DM 2015
Year: 2015

Given a finite simple graph G, let G' be its barycentric refinement: it is the graph in which the vertices are the complete subgraphs of G and in which two such subgraphs are connected, if one is contained into the other. If L(0)=0<L(1) <= L(2) ... <= L(n) are the eigenvalues of the Laplacian of G, define the spectral function F(x) as the function F(x) = L([n x]) on the interval [0,1], where [r] is the floor function giving the largest integer smaller or equal than r. The graph G' is known to be homotopic to G with Euler characteristic chi(G')=chi(G) and dim(G') >= dim(G). Let G(m) be the sequence of barycentric refinements of G=G(0). We prove that for any finite simple graph G, the spectral functions F(G(m)) of successive refinements converge for m to infinity uniformly on compact subsets of (0,1) and exponentially fast to a universal limiting eigenvalue distribution function F which only depends on the clique number respectively the dimension d of the largest complete subgraph of G and not on the starting graph G. In the case d=1, where we deal with graphs without triangles, the limiting distribution is the smooth function F(x) = 4 sin^2(pi x/2). This is related to the Julia set of the quadratic map T(z) = 4z-z^2 which has the one dimensional Julia set [0,4] and F satisfies T(F(k/n))=F(2k/n) as the Laplacians satisfy such a renormalization recursion. The spectral density in the d=1 case is then the arc-sin distribution which is the equilibrium measure on the Julia set. In higher dimensions, where the limiting function F still remains unidentified, F' appears to have a discrete or singular component.
Classification of Heart Disease Using K- Nearest Neighbor and Genetic Algorithm
Venue: arXiv cs.CY 2015
Year: 2015

Data mining techniques have been widely used to mine knowledgeable information from medical data bases. In data mining classification is a supervised learning that can be used to design models describing important data classes, where class attribute is involved in the construction of the classifier. Nearest neighbor (KNN) is very simple, most popular, highly efficient and effective algorithm for pattern recognition.KNN is a straight forward classifier, where samples are classified based on the class of their nearest neighbor. Medical data bases are high volume in nature. If the data set contains redundant and irrelevant attributes, classification may produce less accurate result. Heart disease is the leading cause of death in INDIA. In Andhra Pradesh heart disease was the leading cause of mortality accounting for 32%of all deaths, a rate as high as Canada (35%) and USA.Hence there is a need to define a decision support system that helps clinicians decide to take precautionary steps. In this paper we propose a new algorithm which combines KNN with genetic algorithm for effective classification. Genetic algorithms perform global search in complex large and multimodal landscapes and provide optimal solution. Experimental results shows that our algorithm enhance the accuracy in diagnosis of heart disease.
On Percolation and $NP$-Hardness
Venue: arXiv cs.CC 2015
Year: 2015

We consider the robustness of computational hardness of problems whose input is obtained by applying independent random deletions to worst-case instances. For some classical $NP$-hard problems on graphs, such as Coloring, Vertex-Cover, and Hamiltonicity, we examine the complexity of these problems when edges (or vertices) of an arbitrary graph are deleted independently with probability $1-p > 0$. We prove that for $n$-vertex graphs, these problems remain as hard as in the worst-case, as long as $p > \frac{1}{n^{1-ε}}$ for arbitrary $ε\in (0,1)$, unless $NP \subseteq BPP$. We also prove hardness results for Constraint Satisfaction Problems, where random deletions are applied to clauses or variables, as well as the Subset-Sum problem, where items of a given instance are deleted at random.
On the Number of Synchronizing Colorings of Digraphs
Venue: arXiv cs.FL 2015
Year: 2015

We deal with $k$-out-regular directed multigraphs with loops (called simply \emph{digraphs}). The edges of such a digraph can be colored by elements of some fixed $k$-element set in such a way that outgoing edges of every vertex have different colors. Such a coloring corresponds naturally to an automaton. The road coloring theorem states that every primitive digraph has a synchronizing coloring. In the present paper we study how many synchronizing colorings can exist for a digraph with $n$ vertices. We performed an extensive experimental investigation of digraphs with small number of vertices. This was done by using our dedicated algorithm exhaustively enumerating all small digraphs. We also present a series of digraphs whose fraction of synchronizing colorings is equal to $1-1/k^d$, for every $d \ge 1$ and the number of vertices large enough. On the basis of our results we state several conjectures and open problems. In particular, we conjecture that $1-1/k$ is the smallest possible fraction of synchronizing colorings, except for a single exceptional example on 6 vertices for $k=2$.
Local community extraction in directed networks
Venue: arXiv cs.SI 2015
Year: 2015

Network is a simple but powerful representation of real-world complex systems. Network community analysis has become an invaluable tool to explore and reveal the internal organization of nodes. However, only a few methods were directly designed for community-detection in directed networks. In this article, we introduce the concept of local community structure in directed networks and provide a generic criterion to describe a local community with two properties. We further propose a stochastic optimization algorithm to rapidly detect a local community, which allows for uncovering the directional modular characteristics in directed networks. Numerical results show that the proposed method can resolve detailed local communities with directional information and provide more structural characteristics of directed networks than previous methods.
Threshold Saturation for Spatially Coupled Turbo-like Codes over the Binary Erasure Channel
Venue: arXiv cs.IT 2015
Year: 2015

In this paper we prove threshold saturation for spatially coupled turbo codes (SC-TCs) and braided convolutional codes (BCCs) over the binary erasure channel. We introduce a compact graph representation for the ensembles of SC-TC and BCC codes which simplifies their description and the analysis of the message passing decoding. We demonstrate that by few assumptions in the ensembles of these codes, it is possible to rewrite their vector recursions in a form which places these ensembles under the category of scalar admissible systems. This allows us to define potential functions and prove threshold saturation using the proof technique introduced by Yedla et al..
Self-Interference Suppression for the Full-Duplex Wireless Communication with Large-Scale Antenna
Venue: arXiv cs.IT 2015
Year: 2015

In this letter, we proposed a shared-antenna full-duplex massive MIMO model for the multiuser MIMO system. This model exploits a single antenna array at the base station (BS) to transmit and receive the signals simultaneously. It has the merits of both the full-duplex system and the time-division duplex (TDD) massive MIMO system, i.e., the high spectral efficiency and the channel reciprocity. We focus on the zero-forcing (ZF) and the maximal-ratio transmission/maximal-ratio combining (MRT/MRC) linear processing methods, which are commonly used in the massive MIMO system. As the main finding, we prove that the self-interference (SI) in a shared-antenna full-duplex massive MU-MIMO system can be suppressed in the completely dependent uplink and downlink channels when the number of antennas becomes large enough.
Feature Learning for Interaction Activity Recognition in RGBD Videos
Venue: arXiv cs.CV 2015
Year: 2015

This paper proposes a human activity recognition method which is based on features learned from 3D video data without incorporating domain knowledge. The experiments on data collected by RGBD cameras produce results outperforming other techniques. Our feature encoding method follows the bag-of-visual-word model, then we use a SVM classifier to recognise the activities. We do not use skeleton or tracking information and the same technique is applied on color and depth data.
Easy steps towards a sane IT policy in hospitals
Venue: arXiv cs.CY 2015
Year: 2015

We witnessed the low quality of IT solutions in Paris hospitals. The price paid to private companies for these solutions and the cost incurred from their inefficiency constitute a gross and appalling waste of public resources. We propose to bootstrap a change in IT policy by having heads of department hire IT workers ; we give advice to the central decision making body on how to incentivize them. Easily measurable efficiency gains as well as hard-to-quantify positive externalities will follow.
Archiving Deferred Representations Using a Two-Tiered Crawling Approach
Venue: arXiv cs.DL 2015
Year: 2015

Web resources are increasingly interactive, resulting in resources that are increasingly difficult to archive. The archival difficulty is based on the use of client-side technologies (e.g., JavaScript) to change the client-side state of a representation after it has initially loaded. We refer to these representations as deferred representations. We can better archive deferred representations using tools like headless browsing clients. We use 10,000 seed Universal Resource Identifiers (URIs) to explore the impact of including PhantomJS -- a headless browsing tool -- into the crawling process by comparing the performance of wget (the baseline), PhantomJS, and Heritrix. Heritrix crawled 2.065 URIs per second, 12.15 times faster than PhantomJS and 2.4 times faster than wget. However, PhantomJS discovered 531,484 URIs, 1.75 times more than Heritrix and 4.11 times more than wget. To take advantage of the performance benefits of Heritrix and the URI discovery of PhantomJS, we recommend a tiered crawling strategy in which a classifier predicts whether a representation will be deferred or not, and only resources with deferred representations are crawled with PhantomJS while resources without deferred representations are crawled with Heritrix. We show that this approach is 5.2 times faster than using only PhantomJS and creates a frontier (set of URIs to be crawled) 1.8 times larger than using only Heritrix.
Theoretical Analysis of Tuned HVAC Line for Low Loss Long Distance Bulk Power Transmission
Venue: arXiv cs.SY 2015
Year: 2015

One of the main objectives of the smart grid initiative is to enable bulk power transmission over long distance, with reduced transmission losses. Besides the traditional high-voltage alternating current (HVAC) transmission, with the advancement in power electronics, high-voltage direct current (HVDC) transmission is increasingly becoming important. One of the main factors impacting the transmission line parameters and the losses is the length of the transmission line (overhead). In this paper, a concept of tuned high-voltage AC line is presented for long (> 250 km) transmission line. A tuned line is where the receiving-end voltage and current are numerically equal to the corresponding sending-end values. This paper presents the detailed theoretical analysis of the tuned HVAC line, suggesting adaptation of the transmission frequency as per the length of the line. The simulation of a tuned HVAC line is performed using the PSCAD/EMTDC. Simulation results for two different line lengths, substantiate the theoretical analysis of reducing the reactive power absorbed in the line, while increasing the active power transmission.
Mobile Internet from the Heavens
Venue: arXiv cs.NI 2015
Year: 2015

Almost two-thirds of the humankind currently does not have access to the Internet, wired or wireless. We present a Space Internet proposal capable of providing Zetabyte/ month capacity which is equivalent to 200GB/month for 5 Billion users Worldwide. Our proposal is based on deploying thousands of low-cost micro-satellites in Low-Earth Orbit (LEO), each capable of providing Terabit/s data rates with signal latencies better than or equal to ground based systems.
Smooth Boolean functions are easy: efficient algorithms for low-sensitivity functions
Venue: arXiv cs.CC 2015
Year: 2015

A natural measure of smoothness of a Boolean function is its sensitivity (the largest number of Hamming neighbors of a point which differ from it in function value). The structure of smooth or equivalently low-sensitivity functions is still a mystery. A well-known conjecture states that every such Boolean function can be computed by a shallow decision tree. While this conjecture implies that smooth functions are easy to compute in the simplest computational model, to date no non-trivial upper bounds were known for such functions in any computational model, including unrestricted Boolean circuits. Even a bound on the description length of such functions better than the trivial $2^n$ does not seem to have been known. In this work, we establish the first computational upper bounds on smooth Boolean functions: 1) We show that every sensitivity s function is uniquely specified by its values on a Hamming ball of radius 2s. We use this to show that such functions can be computed by circuits of size $n^{O(s)}$. 2) We show that sensitivity s functions satisfy a strong pointwise noise-stability guarantee for random noise of rate O(1/s). We use this to show that these functions have formulas of depth O(s log n). 3) We show that sensitivity s functions can be (locally) self-corrected from worst-case noise of rate $\exp(-O(s))$. All our results are simple, and follow rather directly from (variants of) the basic fact that that the function value at few points in small neighborhoods of a given point determine its function value via a majority vote. Our results confirm various consequences of the conjecture. They may be viewed as providing a new form of evidence towards its validity, as well as new directions towards attacking it.
Determine the User Country of a Tweet
Venue: arXiv cs.SI 2015
Year: 2015

In the widely used message platform Twitter, about 2% of the tweets contains the geographical location through exact GPS coordinates (latitude and longitude). Knowing the location of a tweet is useful for many data analytics questions. This research is looking at the determination of a location for tweets that do not contain GPS coordinates. An accuracy of 82% was achieved using a Naive Bayes model trained on features such as the users' timezone, the user's language, and the parsed user location. The classifier performs well on active Twitter countries such as the Netherlands and United Kingdom. An analysis of errors made by the classifier shows that mistakes were made due to limited information and shared properties between countries such as shared timezone. A feature analysis was performed in order to see the effect of different features. The features timezone and parsed user location were the most informative features.
Analysis of Spatially-Coupled Counter Braids
Venue: arXiv cs.IT 2015
Year: 2015

A counter braid (CB) is a novel counter architecture introduced by Lu et al. in 2007 for per-flow measurements on high-speed links. CBs achieve an asymptotic compression rate (under optimal decoding) that matches the entropy lower bound of the flow size distribution. Spatially-coupled CBs (SC-CBs) have recently been proposed. In this work, we further analyze single-layer CBs and SC-CBs using an equivalent bipartite graph representation of CBs. On this equivalent representation, we show that the potential and area thresholds are equal. We also show that the area under the extended belief propagation (BP) extrinsic information transfer curve (defined for the equivalent graph), computed for the expected residual CB graph when a peeling decoder equivalent to the BP decoder stops, is equal to zero precisely at the area threshold. This, combined with simulations and an asymptotic analysis of the Maxwell decoder, leads to the conjecture that the area threshold is in fact equal to the Maxwell decoding threshold and hence a lower bound on the maximum a posteriori (MAP) decoding threshold. Finally, we present some numerical results and give some insight into the apparent gap of the BP decoding threshold of SC-CBs to the conjectured lower bound on the MAP decoding threshold.