OpenRaiser/Intern-Atlas huggingface dataset:
On Two Graph-Theoretic Characterizations of Tree Compatibility
Venue: arXiv cs.DM 2012
Year: 2012

Deciding whether a collection of unrooted trees is compatible is a fundamental problem in phylogenetics. Two different graph-theoretic characterizations of tree compatibility have recently been proposed. In one of these, tree compatibility is characterized in terms of the existence of a specific kind of triangulation in a structure known as the display graph. An alternative characterization expresses the tree compatibility problem as a chordal graph sandwich problem in a structure known as the edge label intersection graph. In this paper we show that the characterization using edge label intersection graphs transforms to a characterization in terms of minimal cuts of the display graph. We show how these two characterizations are related to compatibility of splits. We also show how the characterization in terms of minimal cuts of display graph is related to the characterization in terms of triangulation of the display graph.
Improved upper and lower bounds for the point placement problem
Venue: arXiv cs.DS 2012
Year: 2012

The point placement problem is to determine the positions of a set of $n$ distinct points, P = {p1, p2, p3, ..., pn}, on a line uniquely, up to translation and reflection, from the fewest possible distance queries between pairs of points. Each distance query corresponds to an edge in a graph, called point placement graph ppg, whose vertex set is P. The uniqueness requirement of the placement translates to line rigidity of the ppg. In this paper we show how to construct in 2 rounds a line rigid point placement graph of size 9n/7 + O(1). This improves the existing best result of 4n/3 + O(1). We also improve the lower bound on 2-round algorithms from 17n/16 to 9n/8.
Application of classical compilation techniques for syntactic and semantic analysis of specification written in Object Z
Venue: arXiv cs.SE 2012
Year: 2012

Building a parser for a formal specification language such as Object Z is not an easy task. Indeed, it requires a double competence both in the compilation field than in the field of formal specification. In this paper, we first present some tools for analyzing specifications written in Z and Object Z by showing the characteristics of each. Then, we identify some common semantic constraints in Object Z. Finally, we propose an approach for building a parser for Object Z based on the conventional techniques of compilation.
Inapproximability of the Smallest Superpolyomino Problem
Venue: arXiv cs.CG 2012
Year: 2012

We consider the \emph{smallest superpolyomino problem}: given a set of colored polyominoes, find the smallest polyomino containing each input polyomino as a subshape. This problem is shown to be NP-hard, even when restricted to a set of polyominoes using a single common color. Moreover, for sets of polyominoes using two or more colors, the problem is shown to be NP-hard to approximate within a $O(n^{1/3-\varepsilon})$-factor for any $\varepsilon > 0$.
Tourism destinations as digital business ecosystems
Venue: arXiv cs.CY 2012
Year: 2012

Tourism has been experiencing very relevant changes since when Information and Communication Technologies (ICTs), in all their forms, have started to pervade the industry and the market. In the last decade, a new concept gained the attention of both researchers and practitioners, that of Digital Business Ecosystem (DBE). It can be considered as a technological infrastructure aimed at creating a digital environment to support and enhance networking between enterprises and stakeholders operating within a sector. Aim of this paper is to assess the extent to which the technological connection has affected the structural configuration of the tourism system and, specifically, of tourism destinations. The present study argues that two components can be considered when assessing the relationships among stakeholders within a tourism destination: a real and a virtual one. Further it shows how these two components are structurally strongly coupled and co-evolve forming a single system.
Local Optima Networks, Landscape Autocorrelation and Heuristic Search Performance
Venue: arXiv cs.AI 2012
Year: 2012

Recent developments in fitness landscape analysis include the study of Local Optima Networks (LON) and applications of the Elementary Landscapes theory. This paper represents a first step at combining these two tools to explore their ability to forecast the performance of search algorithms. We base our analysis on the Quadratic Assignment Problem (QAP) and conduct a large statistical study over 600 generated instances of different types. Our results reveal interesting links between the network measures, the autocorrelation measures and the performance of heuristic search algorithms.
The Kernel Pitman-Yor Process
Venue: arXiv cs.LG 2012
Year: 2012

In this work, we propose the kernel Pitman-Yor process (KPYP) for nonparametric clustering of data with general spatial or temporal interdependencies. The KPYP is constructed by first introducing an infinite sequence of random locations. Then, based on the stick-breaking construction of the Pitman-Yor process, we define a predictor-dependent random probability measure by considering that the discount hyperparameters of the Beta-distributed random weights (stick variables) of the process are not uniform among the weights, but controlled by a kernel function expressing the proximity between the location assigned to each weight and the given predictors.
A Latent Parameter Node-Centric Model for Spatial Networks
Venue: arXiv cs.SI 2012
Year: 2012

Spatial networks, in which nodes and edges are embedded in space, play a vital role in the study of complex systems. For example, many social networks attach geo-location information to each user, allowing the study of not only topological interactions between users, but spatial interactions as well. The defining property of spatial networks is that edge distances are associated with a cost, which may subtly influence the topology of the network. However, the cost function over distance is rarely known, thus developing a model of connections in spatial networks is a difficult task. In this paper, we introduce a novel model for capturing the interaction between spatial effects and network structure. Our approach represents a unique combination of ideas from latent variable statistical models and spatial network modeling. In contrast to previous work, we view the ability to form long/short-distance connections to be dependent on the individual nodes involved. For example, a node's specific surroundings (e.g. network structure and node density) may make it more likely to form a long distance link than other nodes with the same degree. To capture this information, we attach a latent variable to each node which represents a node's spatial reach. These variables are inferred from the network structure using a Markov Chain Monte Carlo algorithm. We experimentally evaluate our proposed model on 4 different types of real-world spatial networks (e.g. transportation, biological, infrastructure, and social). We apply our model to the task of link prediction and achieve up to a 35% improvement over previous approaches in terms of the area under the ROC curve. Additionally, we show that our model is particularly helpful for predicting links between nodes with low degrees. In these cases, we see much larger improvements over previous models.
Performance Analysis Cluster and GPU Computing Environment on Molecular Dynamic Simulation of BRV-1 and REM2 with GROMACS
Venue: arXiv cs.DC 2012
Year: 2012

One of application that needs high performance computing resources is molecular d ynamic. There is some software available that perform molecular dynamic, one of these is a well known GROMACS. Our previous experiment simulating molecular dynamics of Indonesian grown herbal compounds show sufficient speed up on 32 n odes Cluster computing environment. In order to obtain a reliable simulation, one usually needs to run the experiment on the scale of hundred nodes. But this is expensive to develop and maintain. Since the invention of Graphical Processing Units that is also useful for general programming, many applications have been developed to run on this. This paper reports our experiments that evaluate the performance of GROMACS that runs on two different environment, Cluster computing resources and GPU based PCs. We run the experiment on BRV-1 and REM2 compounds. Four different GPUs are installed on the same type of PCs of quad cores; they are Gefore GTS 250, GTX 465, GTX 470 and Quadro 4000. We build a cluster of 16 nodes based on these four quad cores PCs. The preliminary experiment shows that those run on GTX 470 is the best among the other type of GPUs and as well as the cluster computing resource. A speed up around 11 and 12 is gained, while the cost of computer with GPU is only about 25 percent that of Cluster we built.
Impact of Scheduling in the Return-Link of Multi-Beam Satellite MIMO Systems
Venue: arXiv cs.IT 2012
Year: 2012

The utilization of universal frequency reuse in multi-beam satellite systems introduces a non-negligible level of co-channel interference (CCI), which in turn penalizes the quality of service experienced by users. Taking this as starting point, the paper focuses on resource management performed by the gateway (hub) on the return-link, with particular emphasis on a scheduling algorithm based on bipartite graph approach. The study gives important insights into the achievable per-user rate and the role played by the number of users and spot beams considered for scheduling. More interestingly, it is shown that a free-slot assignment strategy helps to exploit the available satellite resources, thus guaranteeing a max-min rate requirement to users. Remarks about the trade-off between efficiency-loss and performance increase are finally drawn at the end of the paper.
On efficient constructions of short lists containing mostly Ramsey graphs
Venue: arXiv cs.CC 2012
Year: 2012

One of the earliest and best-known application of the probabilistic method is the proof of existence of a 2 log n$-Ramsey graph, i.e., a graph with n nodes that contains no clique or independent set of size 2 log n. The explicit construction of such a graph is a major open problem. We show that a reasonable hardness assumption implies that in polynomial time one can construct a list containing polylog(n) graphs such that most of them are 2 log n-Ramsey.
Submodularity and Optimality of Fusion Rules in Balanced Binary Relay Trees
Venue: arXiv cs.IT 2012
Year: 2012

We study the distributed detection problem in a balanced binary relay tree, where the leaves of the tree are sensors generating binary messages. The root of the tree is a fusion center that makes the overall decision. Every other node in the tree is a fusion node that fuses two binary messages from its child nodes into a new binary message and sends it to the parent node at the next level. We assume that the fusion nodes at the same level use the same fusion rule. We call a string of fusion rules used at different levels a fusion strategy. We consider the problem of finding a fusion strategy that maximizes the reduction in the total error probability between the sensors and the fusion center. We formulate this problem as a deterministic dynamic program and express the solution in terms of Bellman's equations. We introduce the notion of stringsubmodularity and show that the reduction in the total error probability is a stringsubmodular function. Consequentially, we show that the greedy strategy, which only maximizes the level-wise reduction in the total error probability, is within a factor of the optimal strategy in terms of reduction in the total error probability.
Black-Box Verification for GUI Applications
Venue: arXiv cs.SE 2012
Year: 2012

In black-box testing of GUI applications (a form of system testing), a dynamic analysis of the GUI application is used to infer a black-box model; the black-box model is then used to derive test cases for the test of the GUI application. In this paper, we propose to supplement the test with the verification of the black-box model. We present a method that can give a guarantee of the absence of faults, i.e., the correctness of all test cases of the black-box model. The black-model allows us to formulate a parametrized verification problem. As we will show, it also allows us to circumvent the static analysis of the GUI tool kit. We have implemented our approach; preliminary experiments indicate its practical potential.
Full Rank Solutions for the MIMO Gaussian Wiretap Channel with an Average Power Constraint
Venue: arXiv cs.IT 2012
Year: 2012

This paper considers a multiple-input multiple-output (MIMO) Gaussian wiretap channel model, where there exists a transmitter, a legitimate receiver and an eavesdropper, each equipped with multiple antennas. In this paper, we first revisit the rank property of the optimal input covariance matrix that achieves the secrecy capacity of the multiple antenna MIMO Gaussian wiretap channel under the average power constraint. Next, we obtain necessary and sufficient conditions on the MIMO wiretap channel parameters such that the optimal input covariance matrix is full-rank, and we fully characterize the resulting covariance matrix as well. Numerical results are presented to illustrate the proposed theoretical findings.
Single Source - All Sinks Max Flows in Planar Digraphs
Venue: arXiv cs.DM 2012
Year: 2012

Let G = (V,E) be a planar n-vertex digraph. Consider the problem of computing max st-flow values in G from a fixed source s to all sinks t in V\{s}. We show how to solve this problem in near-linear O(n log^3 n) time. Previously, no better solution was known than running a single-source single-sink max flow algorithm n-1 times, giving a total time bound of O(n^2 log n) with the algorithm of Borradaile and Klein. An important implication is that all-pairs max st-flow values in G can be computed in near-quadratic time. This is close to optimal as the output size is Theta(n^2). We give a quadratic lower bound on the number of distinct max flow values and an Omega(n^3) lower bound for the total size of all min cut-sets. This distinguishes the problem from the undirected case where the number of distinct max flow values is O(n). Previous to our result, no algorithm which could solve the all-pairs max flow values problem faster than the time of Theta(n^2) max-flow computations for every planar digraph was known. This result is accompanied with a data structure that reports min cut-sets. For fixed s and all t, after O(n^{3/2} log^{3/2} n) preprocessing time, it can report the set of arcs C crossing a min st-cut in time roughly proportional to the size of C.
Lifted Relax, Compensate and then Recover: From Approximate to Exact Lifted Probabilistic Inference
Venue: arXiv cs.AI 2012
Year: 2012

We propose an approach to lifted approximate inference for first-order probabilistic models, such as Markov logic networks. It is based on performing exact lifted inference in a simplified first-order model, which is found by relaxing first-order constraints, and then compensating for the relaxation. These simplified models can be incrementally improved by carefully recovering constraints that have been relaxed, also at the first-order level. This leads to a spectrum of approximations, with lifted belief propagation on one end, and exact lifted inference on the other. We discuss how relaxation, compensation, and recovery can be performed, all at the firstorder level, and show empirically that our approach substantially improves on the approximations of both propositional solvers and lifted belief propagation.
DBN-Based Combinatorial Resampling for Articulated Object Tracking
Venue: arXiv cs.CV 2012
Year: 2012

Particle Filter is an effective solution to track objects in video sequences in complex situations. Its key idea is to estimate the density over the possible states of the object using a weighted sample whose elements are called particles. One of its crucial step is a resampling step in which particles are resampled to avoid some degeneracy problem. In this paper, we introduce a new resampling method called Combinatorial Resampling that exploits some features of articulated objects to resample over an implicitly created sample of an exponential size better representing the density to estimate. We prove that it is sound and, through experimentations both on challenging synthetic and real video sequences, we show that it outperforms all classical resampling methods both in terms of the quality of its results and in terms of response times.
Learning Mixtures of Submodular Shells with Application to Document Summarization
Venue: arXiv cs.LG 2012
Year: 2012

We introduce a method to learn a mixture of submodular "shells" in a large-margin setting. A submodular shell is an abstract submodular function that can be instantiated with a ground set and a set of parameters to produce a submodular function. A mixture of such shells can then also be so instantiated to produce a more complex submodular function. What our algorithm learns are the mixture weights over such shells. We provide a risk bound guarantee when learning in a large-margin structured-prediction setting using a projected subgradient method when only approximate submodular optimization is possible (such as with submodular function maximization). We apply this method to the problem of multi-document summarization and produce the best results reported so far on the widely used NIST DUC-05 through DUC-07 document summarization corpora.
Computing Optimal Security Strategies for Interdependent Assets
Venue: arXiv cs.GT 2012
Year: 2012

We introduce a novel framework for computing optimal randomized security policies in networked domains which extends previous approaches in several ways. First, we extend previous linear programming techniques for Stackelberg security games to incorporate benefits and costs of arbitrary security configurations on individual assets. Second, we offer a principled model of failure cascades that allows us to capture both the direct and indirect value of assets, and extend this model to capture uncertainty about the structure of the interdependency network. Third, we extend the linear programming formulation to account for exogenous (random) failures in addition to targeted attacks. The goal of our work is two-fold. First, we aim to develop techniques for computing optimal security strategies in realistic settings involving interdependent security. To this end, we evaluate the value of our technical contributions in comparison with previous approaches, and show that our approach yields much better defense policies and scales to realistic graphs. Second, our computational framework enables us to attain theoretical insights about security on networks. As an example, we study how allowing security to be endogenous impacts the relative resilience of different network topologies.
Active Imitation Learning via Reduction to I.I.D. Active Learning
Venue: arXiv cs.LG 2012
Year: 2012

In standard passive imitation learning, the goal is to learn a target policy by passively observing full execution trajectories of it. Unfortunately, generating such trajectories can require substantial expert effort and be impractical in some cases. In this paper, we consider active imitation learning with the goal of reducing this effort by querying the expert about the desired action at individual states, which are selected based on answers to past queries and the learner's interactions with an environment simulator. We introduce a new approach based on reducing active imitation learning to i.i.d. active learning, which can leverage progress in the i.i.d. setting. Our first contribution, is to analyze reductions for both non-stationary and stationary policies, showing that the label complexity (number of queries) of active imitation learning can be substantially less than passive learning. Our second contribution, is to introduce a practical algorithm inspired by the reductions, which is shown to be highly effective in four test domains compared to a number of alternatives.
A Maximum Likelihood Approach For Selecting Sets of Alternatives
Venue: arXiv cs.AI 2012
Year: 2012

We consider the problem of selecting a subset of alternatives given noisy evaluations of the relative strength of different alternatives. We wish to select a k-subset (for a given k) that provides a maximum likelihood estimate for one of several objectives, e.g., containing the strongest alternative. Although this problem is NP-hard, we show that when the noise level is sufficiently high, intuitive methods provide the optimal solution. We thus generalize classical results about singling out one alternative and identifying the hidden ranking of alternatives by strength. Extensive experiments show that our methods perform well in practical settings.
A Model-Based Approach to Rounding in Spectral Clustering
Venue: arXiv cs.LG 2012
Year: 2012

In spectral clustering, one defines a similarity matrix for a collection of data points, transforms the matrix to get the Laplacian matrix, finds the eigenvectors of the Laplacian matrix, and obtains a partition of the data using the leading eigenvectors. The last step is sometimes referred to as rounding, where one needs to decide how many leading eigenvectors to use, to determine the number of clusters, and to partition the data points. In this paper, we propose a novel method for rounding. The method differs from previous methods in three ways. First, we relax the assumption that the number of clusters equals the number of eigenvectors used. Second, when deciding the number of leading eigenvectors to use, we not only rely on information contained in the leading eigenvectors themselves, but also use subsequent eigenvectors. Third, our method is model-based and solves all the three subproblems of rounding using a class of graphical models called latent tree models. We evaluate our method on both synthetic and real-world data. The results show that our method works correctly in the ideal case where between-clusters similarity is 0, and degrades gracefully as one moves away from the ideal case.
Heuristic Ranking in Tightly Coupled Probabilistic Description Logics
Venue: arXiv cs.AI 2012
Year: 2012

The Semantic Web effort has steadily been gaining traction in the recent years. In particular,Web search companies are recently realizing that their products need to evolve towards having richer semantic search capabilities. Description logics (DLs) have been adopted as the formal underpinnings for Semantic Web languages used in describing ontologies. Reasoning under uncertainty has recently taken a leading role in this arena, given the nature of data found on theWeb. In this paper, we present a probabilistic extension of the DL EL++ (which underlies the OWL2 EL profile) using Markov logic networks (MLNs) as probabilistic semantics. This extension is tightly coupled, meaning that probabilistic annotations in formulas can refer to objects in the ontology. We show that, even though the tightly coupled nature of our language means that many basic operations are data-intractable, we can leverage a sublanguage of MLNs that allows to rank the atomic consequences of an ontology relative to their probability values (called ranking queries) even when these values are not fully computed. We present an anytime algorithm to answer ranking queries, and provide an upper bound on the error that it incurs, as well as a criterion to decide when results are guaranteed to be correct.