OpenRaiser/Intern-Atlas huggingface dataset:
Ride Sharing with a Vehicle of Unlimited Capacity
Venue: arXiv cs.DM 2016
Year: 2016

A ride sharing problem is considered where we are given a graph, whose edges are equipped with a travel cost, plus a set of objects, each associated with a transportation request given by a pair of origin and destination nodes. A vehicle travels through the graph, carrying each object from its origin to its destination without any bound on the number of objects that can be simultaneously transported. The vehicle starts and terminates its ride at given nodes, and the goal is to compute a minimum-cost ride satisfying all requests. This ride sharing problem is shown to be tractable on paths by designing a $O(h \log h+n)$ algorithm, with $h$ being the number of distinct requests and with $n$ being the number of nodes in the path. The algorithm is then used as a subroutine to efficiently solve instances defined over cycles, hence covering all graphs with maximum degree $2$. This traces the frontier of tractability, since $\bf NP$-hard instances are exhibited over trees whose maximum degree is $3$.
Micro-Clustering: Finding Small Clusters in Large Diversity
Venue: arXiv cs.DS 2016
Year: 2016

We address the problem of un-supervised soft-clustering called micro-clustering. The aim of the problem is to enumerate all groups composed of records strongly related to each other, while standard clustering methods separate records at sparse parts. The problem formulation of micro-clustering is non-trivial. Clique mining in a similarity graph is a typical approach, but it results in a huge number of cliques that are of many similar cliques. We propose a new concept data polishing. The cause of huge solutions can be considered that the groups are not clear in the data, that is, the boundaries of the groups are not clear, because of noise, uncertainty, lie, lack, etc. Data polishing clarifies the groups by perturbating the data. Specifically, dense subgraphs that would correspond to clusters are replaced by cliques. The clusters are clarified as maximal cliques, thus the number of maximal cliques will be drastically reduced. We also propose an efficient algorithm applicable even for large scale data. Computational experiments showed the efficiency of our algorithm, i.e., the number of solutions is small, (e.g., 1,000), the members of each group are deeply related, and the computation time is short.
The Complexity of Computing the Optimal Composition of Differential Privacy
Venue: arXiv cs.CC 2016
Year: 2016

In the study of differential privacy, composition theorems (starting with the original paper of Dwork, McSherry, Nissim, and Smith (TCC'06)) bound the degradation of privacy when composing several differentially private algorithms. Kairouz, Oh, and Viswanath (ICML'15) showed how to compute the optimal bound for composing $k$ arbitrary $(ε,δ)$-differentially private algorithms. We characterize the optimal composition for the more general case of $k$ arbitrary $(ε_{1},δ_{1}),\ldots,(ε_{k},δ_{k})$-differentially private algorithms where the privacy parameters may differ for each algorithm in the composition. We show that computing the optimal composition in general is $\#$P-complete. Since computing optimal composition exactly is infeasible (unless FP=$\#$P), we give an approximation algorithm that computes the composition to arbitrary accuracy in polynomial time. The algorithm is a modification of Dyer's dynamic programming approach to approximately counting solutions to knapsack problems (STOC'03).
Pushdown Control-Flow Analysis for Free
Venue: arXiv cs.PL 2016
Year: 2016

Traditional control-flow analysis (CFA) for higher-order languages, whether implemented by constraint-solving or abstract interpretation, introduces spurious connections between callers and callees. Two distinct invocations of a function will necessarily pollute one another's return-flow. Recently, three distinct approaches have been published which provide perfect call-stack precision in a computable manner: CFA2, PDCFA, and AAC. Unfortunately, CFA2 and PDCFA are difficult to implement and require significant engineering effort. Furthermore, all three are computationally expensive; for a monovariant analysis, CFA2 is in $O(2^n)$, PDCFA is in $O(n^6)$, and AAC is in $O(n^9 log n)$. In this paper, we describe a new technique that builds on these but is both straightforward to implement and computationally inexpensive. The crucial insight is an unusual state-dependent allocation strategy for the addresses of continuation. Our technique imposes only a constant-factor overhead on the underlying analysis and, with monovariance, costs only O(n3) in the worst case. This paper presents the intuitions behind this development, a proof of the precision of this analysis, and benchmarks demonstrating its efficacy.
Visibility-Aware Optimal Contagion of Malware Epidemics
Venue: arXiv cs.CR 2016
Year: 2016

Recent innovations in the design of computer viruses have led to new trade-offs for the attacker. Multiple variants of a malware may spread at different rates and have different levels of visibility to the network. In this work we examine the optimal strategies for the attacker so as to trade off the extent of spread of the malware against the need for stealth. We show that in the mean-field deterministic regime, this spread-stealth trade-off is optimized by computationally simple single-threshold policies. Specifically, we show that only one variant of the malware is spread by the attacker at each time, as there exists a time up to which the attacker prioritizes maximizing the spread of the malware, and after which she prioritizes stealth.
On Recurrent Reachability for Continuous Linear Dynamical Systems
Venue: arXiv cs.SY 2016
Year: 2016

The continuous evolution of a wide variety of systems, including continuous-time Markov chains and linear hybrid automata, can be described in terms of linear differential equations. In this paper we study the decision problem of whether the solution $\boldsymbol{x}(t)$ of a system of linear differential equations $d\boldsymbol{x}/dt=A\boldsymbol{x}$ reaches a target halfspace infinitely often. This recurrent reachability problem can equivalently be formulated as the following Infinite Zeros Problem: does a real-valued function $f:\mathbb{R}_{\geq 0}\rightarrow\mathbb{R}$ satisfying a given linear differential equation have infinitely many zeros? Our main decidability result is that if the differential equation has order at most $7$, then the Infinite Zeros Problem is decidable. On the other hand, we show that a decision procedure for the Infinite Zeros Problem at order $9$ (and above) would entail a major breakthrough in Diophantine Approximation, specifically an algorithm for computing the Lagrange constants of arbitrary real algebraic numbers to arbitrary precision.
Untangling AdaBoost-based Cost-Sensitive Classification. Part I: Theoretical Perspective
Venue: arXiv cs.CV 2016
Year: 2016

Boosting algorithms have been widely used to tackle a plethora of problems. In the last few years, a lot of approaches have been proposed to provide standard AdaBoost with cost-sensitive capabilities, each with a different focus. However, for the researcher, these algorithms shape a tangled set with diffuse differences and properties, lacking a unifying analysis to jointly compare, classify, evaluate and discuss those approaches on a common basis. In this series of two papers we aim to revisit the various proposals, both from theoretical (Part I) and practical (Part II) perspectives, in order to analyze their specific properties and behavior, with the final goal of identifying the algorithm providing the best and soundest results.
Application of Permutation Group Theory in Reversible Logic Synthesis
Venue: arXiv cs.ET 2016
Year: 2016

The paper discusses various applications of permutation group theory in the synthesis of reversible logic circuits consisting of Toffoli gates with negative control lines. An asymptotically optimal synthesis algorithm for circuits consisting of gates from the NCT library is described. An algorithm for gate complexity reduction, based on equivalent replacements of gates compositions, is introduced. A new approach for combining a group-theory-based synthesis algorithm with a Reed-Muller-spectra-based synthesis algorithm is described. Experimental results are presented to show that the proposed synthesis techniques allow a reduction in input lines count, gate complexity or quantum cost of reversible circuits for various benchmark functions.
Joint Transmission and Energy Transfer Policies for Energy Harvesting Devices with Finite Batteries
Venue: arXiv cs.IT 2016
Year: 2016

One of the main concerns in traditional Wireless Sensor Networks (WSNs) is energy efficiency. In this work, we analyze two techniques that can extend network lifetime. The first is Ambient \emph{Energy Harvesting} (EH), i.e., the capability of the devices to gather energy from the environment, whereas the second is Wireless \emph{Energy Transfer} (ET), that can be used to exchange energy among devices. We study the combination of these techniques, showing that they can be used jointly to improve the system performance. We consider a transmitter-receiver pair, showing how the ET improvement depends upon the statistics of the energy arrivals and the energy consumption of the devices. With the aim of maximizing a reward function, e.g., the average transmission rate, we find performance upper bounds with and without ET, define both online and offline optimization problems, and present results based on realistic energy arrivals in indoor and outdoor environments. We show that ET can significantly improve the system performance even when a sizable fraction of the transmitted energy is wasted and that, in some scenarios, the online approach can obtain close to optimal performance.
Lessons Learned from Applying Social Network Analysis on an Industrial Free/Libre/Open Source Software Ecosystem
Venue: arXiv cs.SI 2016
Year: 2016

Many software projects are no longer done in-house by a single organization. Instead, we are in a new age where software is developed by a networked community of individuals and organizations, which base their relations to each other on mutual interest. Paradoxically, recent research suggests that software development can actually be jointly-developed by rival firms. For instance, it is known that the mobile-device makers Apple and Samsung kept collaborating in open source projects while running expensive patent wars in the court. Taking a case study approach, we explore how rival firms collaborate in the open source arena by employing a multi-method approach that combines qualitative analysis of archival data (QA) with mining software repositories (MSR) and Social Network Analysis (SNA). While exploring collaborative processes within the OpenStack ecosystem, our research contributes to Software Engineering research by exploring the role of groups, sub-communities and business models within a high-networked open source ecosystem. Surprising results point out that competition for the same revenue model (i.e., operating conflicting business models) does not necessary affect collaboration within the ecosystem. Moreover, while detecting the different sub-communities of the OpenStack community, we found out that the expected social tendency of developers to work with developers from same firm (i.e., homophily) did not hold within the OpenStack ecosystem. Furthermore, while addressing a novel, complex and unexplored open source case, this research also contributes to the management literature in coopetition strategy and high-tech entrepreneurship with a rich description on how heterogeneous actors within a high-networked ecosystem (involving individuals, startups, established firms and public organizations) joint-develop a complex infrastructure for big-data in the open source arena.
A Parameter-free Affinity Based Clustering
Venue: arXiv cs.CV 2016
Year: 2016

Several methods have been proposed to estimate the number of clusters in a dataset; the basic ideal behind all of them has been to study an index that measures inter-cluster separation and intra-cluster cohesion over a range of cluster numbers and report the number which gives an optimum value of the index. In this paper we propose a simple, parameter free approach that is like human cognition to form clusters, where closely lying points are easily identified to form a cluster and total number of clusters are revealed. To identify closely lying points, affinity of two points is defined as a function of distance and a threshold affinity is identified, above which two points in a dataset are likely to be in the same cluster. Well separated clusters are identified even in the presence of outliers, whereas for not so well separated dataset, final number of clusters are estimated and the detected clusters are merged to produce the final clusters. Experiments performed with several large dimensional synthetic and real datasets show good results with robustness to noise and density variation within dataset.
Towards Storytelling from Visual Lifelogging: An Overview
Venue: arXiv cs.CV 2016
Year: 2016

Visual lifelogging consists of acquiring images that capture the daily experiences of the user by wearing a camera over a long period of time. The pictures taken offer considerable potential for knowledge mining concerning how people live their lives, hence, they open up new opportunities for many potential applications in fields including healthcare, security, leisure and the quantified self. However, automatically building a story from a huge collection of unstructured egocentric data presents major challenges. This paper provides a thorough review of advances made so far in egocentric data analysis, and in view of the current state of the art, indicates new lines of research to move us towards storytelling from visual lifelogging.
Particle detection and tracking in fluorescence time-lapse imaging: a contrario approach
Venue: arXiv cs.CV 2016
Year: 2016

This paper proposes a probabilistic approach for the detection and the tracking of particles in fluorescent time-lapse imaging. In the presence of a very noised and poor-quality data, particles and trajectories can be characterized by an a contrario model, that estimates the probability of observing the structures of interest in random data. This approach, first introduced in the modeling of human visual perception and then successfully applied in many image processing tasks, leads to algorithms that neither require a previous learning stage, nor a tedious parameter tuning and are very robust to noise. Comparative evaluations against a well-established baseline show that the proposed approach outperforms the state of the art.
Exact ZF Analysis and Computer-Algebra-Aided Evaluation in Rank-1 LoS Rician Fading
Venue: arXiv cs.IT 2016
Year: 2016

We study zero-forcing detection (ZF) for multiple-input/multiple-output (MIMO) spatial multiplexing under transmit-correlated Rician fading for an N_R X N_T channel matrix with rank-1 line-of-sight (LoS) component. By using matrix transformations and multivariate statistics, our exact analysis yields the signal-to-noise ratio moment generating function (m.g.f.) as an infinite series of gamma distribution m.g.f.'s and analogous series for ZF performance measures, e.g., outage probability and ergodic capacity. However, their numerical convergence is inherently problematic with increasing Rician K-factor, N_R , and N_T. We circumvent this limitation as follows. First, we derive differential equations satisfied by the performance measures with a novel automated approach employing a computer-algebra tool which implements Groebner basis computation and creative telescoping. These differential equations are then solved with the holonomic gradient method (HGM) from initial conditions computed with the infinite series. We demonstrate that HGM yields more reliable performance evaluation than by infinite series alone and more expeditious than by simulation, for realistic values of K , and even for N_R and N_T relevant to large MIMO systems. We envision extending the proposed approaches for exact analysis and reliable evaluation to more general Rician fading and other transceiver methods.
Improved Approximations for Cubic and Cubic Bipartite TSP
Venue: arXiv cs.DS 2016
Year: 2016

We show improved approximation guarantees for the traveling salesman problem on cubic graphs, and cubic bipartite graphs. For cubic bipartite graphs with n nodes, we improve on recent results of Karp and Ravi (2014) by giving a simple "local improvement" algorithm that finds a tour of length at most 5/4 n - 2. For 2-connected cubic graphs, we show that the techniques of Moemke and Svensson (2011) can be combined with the techniques of Correa, Larre and Soto (2012), to obtain a tour of length at most (4/3-1/8754)n.
Sensor placement for fault location identification in water networks: A minimum test cover approach
Venue: arXiv cs.SY 2016
Year: 2016

This paper focuses on the optimal sensor placement problem for the identification of pipe failure locations in large-scale urban water systems. The problem involves selecting the minimum number of sensors such that every pipe failure can be uniquely localized. This problem can be viewed as a minimum test cover (MTC) problem, which is NP-hard. We consider two approaches to obtain approximate solutions to this problem. In the first approach, we transform the MTC problem to a minimum set cover (MSC) problem and use the greedy algorithm that exploits the submodularity property of the MSC problem to compute the solution to the MTC problem. In the second approach, we develop a new \textit{augmented greedy} algorithm for solving the MTC problem. This approach does not require the transformation of the MTC to MSC. Our augmented greedy algorithm provides in a significant computational improvement while guaranteeing the same approximation ratio as the first approach. We propose several metrics to evaluate the performance of the sensor placement designs. Finally, we present detailed computational experiments for a number of real water distribution networks.
Belief and Truth in Hypothesised Behaviours
Venue: arXiv cs.AI 2016
Year: 2016

There is a long history in game theory on the topic of Bayesian or "rational" learning, in which each player maintains beliefs over a set of alternative behaviours, or types, for the other players. This idea has gained increasing interest in the artificial intelligence (AI) community, where it is used as a method to control a single agent in a system composed of multiple agents with unknown behaviours. The idea is to hypothesise a set of types, each specifying a possible behaviour for the other agents, and to plan our own actions with respect to those types which we believe are most likely, given the observed actions of the agents. The game theory literature studies this idea primarily in the context of equilibrium attainment. In contrast, many AI applications have a focus on task completion and payoff maximisation. With this perspective in mind, we identify and address a spectrum of questions pertaining to belief and truth in hypothesised types. We formulate three basic ways to incorporate evidence into posterior beliefs and show when the resulting beliefs are correct, and when they may fail to be correct. Moreover, we demonstrate that prior beliefs can have a significant impact on our ability to maximise payoffs in the long-term, and that they can be computed automatically with consistent performance effects. Furthermore, we analyse the conditions under which we are able complete our task optimally, despite inaccuracies in the hypothesised types. Finally, we show how the correctness of hypothesised types can be ascertained during the interaction via an automated statistical analysis.
Unsupervised Sentence Simplification Using Deep Semantics
Venue: arXiv cs.CL 2016
Year: 2016

We present a novel approach to sentence simplification which departs from previous work in two main ways. First, it requires neither hand written rules nor a training corpus of aligned standard and simplified sentences. Second, sentence splitting operates on deep semantic structure. We show (i) that the unsupervised framework we propose is competitive with four state-of-the-art supervised systems and (ii) that our semantic based approach allows for a principled and effective handling of sentence splitting.
Multicast Traffic Engineering for Software-Defined Networks
Venue: arXiv cs.NI 2016
Year: 2016

Although Software-Defined Networking (SDN) enables flexible network resource allocations for traffic engineering, current literature mostly focuses on unicast communications. Compared to traffic engineering for multiple unicast flows, multicast traffic engineering for multiple trees is very challenging not only because minimizing the bandwidth consumption of a single multicast tree by solving the Steiner tree problem is already NP-Hard, but the Steiner tree problem does not consider the link capacity constraint for multicast flows and node capacity constraint to store the forwarding entries in Group Table of OpenFlow. In this paper, therefore, we first study the hardness results of scalable multicast traffic engineering in SDN. We prove that scalable multicast traffic engineering with only the node capacity constraint is NP-Hard and not approximable within, which is the number of destinations in the largest multicast group. We then prove that scalable multicast traffic engineering with both the node and link capacity constraints is NP-Hard and not approximable within any ratio. To solve the problem, we design an approximation algorithm, named Multi-Tree Routing and State Assignment Algorithm (MTRSA), for the first case and extend it to the general multicast traffic engineering problem. The simulation and implementation results demonstrate that the solutions obtained by the proposed algorithm outperform the shortest-path trees and Steiner trees. Most importantly, MTRSA is computation-efficient and can be deployed in SDN since it can generate the solution with numerous trees in a short time.
A Visual Embedding for the Unsupervised Extraction of Abstract Semantics
Venue: arXiv cs.CV 2016
Year: 2016

Vector-space word representations obtained from neural network models have been shown to enable semantic operations based on vector arithmetic. In this paper, we explore the existence of similar information on vector representations of images. For that purpose we define a methodology to obtain large, sparse vector representations of image classes, and generate vectors through the state-of-the-art deep learning architecture GoogLeNet for 20K images obtained from ImageNet. We first evaluate the resultant vector-space semantics through its correlation with WordNet distances, and find vector distances to be strongly correlated with linguistic semantics. We then explore the location of images within the vector space, finding elements close in WordNet to be clustered together, regardless of significant visual variances (e.g. 118 dog types). More surprisingly, we find that the space unsupervisedly separates complex classes without prior knowledge (e.g. living things). Afterwards, we consider vector arithmetics. Although we are unable to obtain meaningful results on this regard, we discuss the various problem we encountered, and how we consider to solve them. Finally, we discuss the impact of our research for cognitive systems, focusing on the role of the architecture being used.