OpenRaiser/Intern-Atlas huggingface dataset:
On computing tree and path decompositions with metric constraints on the bags
Venue: arXiv cs.CC 2016
Year: 2016

We here investigate on the complexity of computing the \emph{tree-length} and the \emph{tree-breadth} of any graph $G$, that are respectively the best possible upper-bounds on the diameter and the radius of the bags in a tree decomposition of $G$. \emph{Path-length} and \emph{path-breadth} are similarly defined and studied for path decompositions. So far, it was already known that tree-length is NP-hard to compute. We here prove it is also the case for tree-breadth, path-length and path-breadth. Furthermore, we provide a more detailed analysis on the complexity of computing the tree-breadth. In particular, we show that graphs with tree-breadth one are in some sense the hardest instances for the problem of computing the tree-breadth. We give new properties of graphs with tree-breadth one. Then we use these properties in order to recognize in polynomial-time all graphs with tree-breadth one that are planar or bipartite graphs. On the way, we relate tree-breadth with the notion of \emph{$k$-good} tree decompositions (for $k=1$), that have been introduced in former work for routing. As a byproduct of the above relation, we prove that deciding on the existence of a $k$-good tree decomposition is NP-complete (even if $k=1$). All this answers open questions from the literature.
RRH based Massive MIMO with "on the Fly" Pilot Contamination Control
Venue: arXiv cs.IT 2016
Year: 2016

Dense large-scale antenna deployments are one of the most promising technologies for delivering very large throughputs per unit area in the downlink (DL) of cellular networks. We consider such a dense deployment involving a distributed system formed by multi-antenna remote radio head (RRH) units connected to the same fronthaul serving a geographical area. Knowledge of the DL channel between each active user and its nearby RRH antennas is most efficiently obtained at the RRHs via reciprocity based training, that is, by estimating a user's channel using uplink (UL) pilots transmitted by the user, and exploiting the UL/DL channel reciprocity. We consider aggressive pilot reuse across an RRH system, whereby a single pilot dimension is simultaneously assigned to multiple active users. We introduce a novel coded pilot approach, which allows each RRH unit to detect pilot collisions, i.e., when more than a single user in its proximity uses the same pilot dimensions. Thanks to the proposed coded pilot approach, pilot contamination can be substantially avoided. As shown, such strategy can yield densification benefits in the form of increased multiplexing gain per UL pilot dimension with respect to conventional reuse schemes and some recent approaches assigning pseudorandom pilot vectors to the active users.
It's just a matter of perspective(s): Crowd-Powered Consensus Organization of Corpora
Venue: arXiv cs.DB 2016
Year: 2016

We study the problem of organizing a collection of objects - images, videos - into clusters, using crowdsourcing. This problem is notoriously hard for computers to do automatically, and even with crowd workers, is challenging to orchestrate: (a) workers may cluster based on different latent hierarchies or perspectives; (b) workers may cluster at different granularities even when clustering using the same perspective; and (c) workers may only see a small portion of the objects when deciding how to cluster them (and therefore have limited understanding of the "big picture"). We develop cost-efficient, accurate algorithms for identifying the consensus organization (i.e., the organizing perspective most workers prefer to employ), and incorporate these algorithms into a cost-effective workflow for organizing a collection of objects, termed ORCHESTRA. We compare our algorithms with other algorithms for clustering, on a variety of real-world datasets, and demonstrate that ORCHESTRA organizes items better and at significantly lower costs.
Dynamic Transposition of Melodic Sequences on Digital Devices
Venue: arXiv cs.SD 2016
Year: 2016

A method is proposed which enables one to produce musical compositions by using transposition in place of harmonic progression. A transposition scale is introduced to provide a set of intervals commensurate with the musical scale, such as chromatic or just intonation scales. A sequence of intervals selected from the transposition scale is used to shift instrument frequency at predefined times during the composition which serves as a harmonic sequence of a composition. A transposition sequence constructed in such a way can be extended to a hierarchy of sequences. The fundamental sound frequency of an instrument is obtained as a product of the base frequency, instrument key factor, and a cumulative product of respective factors from all the harmonic sequences. The multiplication factors are selected from subsets of rational numbers, which form instrument scales and transposition scales of different levels. Each harmonic sequence can be related to its own transposition scale, or a single scale can be used for all levels. When composing for an orchestra of instruments, harmonic sequences and instrument scales can be assigned independently to each musical instrument. The method solves the problem of using just intonation scale across multiple octaves as well as simplifies writing of instrument scores.
SENDIM for Incremental Development of Cloud Networks
Venue: arXiv cs.NI 2016
Year: 2016

Due to the limited and varying availability of cheap infrastructure and resources, cloud network systems and applications are tested in simulation and emulation environments prior to physical deployments, at different stages of development. Configuration management tools manage deployments and migrations across different cloud platforms, mitigating tedious system administration efforts. However, currently a cloud networking simulation cannot be migrated as an emulation, or vice versa, without rewriting and manually re-deploying the simulated application. This paper presents SENDIM (Sendim is a northeastern Portuguese town close to the Spanish border, where the rare Mirandese language is spoken), a Simulation, Emulation, aNd Deployment Integration Middleware for cloud networks. As an orchestration platform for incrementally building Software-Defined Cloud Networks (SDCN), SENDIM manages the development and deployment of algorithms and architectures the entire length from visualization, simulation, emulation, to physical deployments. Hence, SENDIM optimizes the evaluation of cloud networks.
Empirical Gaussian priors for cross-lingual transfer learning
Venue: arXiv cs.CL 2016
Year: 2016

Sequence model learning algorithms typically maximize log-likelihood minus the norm of the model (or minimize Hamming loss + norm). In cross-lingual part-of-speech (POS) tagging, our target language training data consists of sequences of sentences with word-by-word labels projected from translations in $k$ languages for which we have labeled data, via word alignments. Our training data is therefore very noisy, and if Rademacher complexity is high, learning algorithms are prone to overfit. Norm-based regularization assumes a constant width and zero mean prior. We instead propose to use the $k$ source language models to estimate the parameters of a Gaussian prior for learning new POS taggers. This leads to significantly better performance in multi-source transfer set-ups. We also present a drop-out version that injects (empirical) Gaussian noise during online learning. Finally, we note that using empirical Gaussian priors leads to much lower Rademacher complexity, and is superior to optimally weighted model interpolation.
Decentralized Control Problems with Substitutable Actions
Venue: arXiv cs.SY 2016
Year: 2016

We consider a decentralized system with multiple controllers and define substitutability of one controller by another in open-loop strategies. We explore the implications of this property on the optimization of closed-loop strategies. In particular, we focus on the decentralized LQG problem with substitutable actions. Even though the problem we formulate does not belong to the known classes of "simpler" decentralized problems such as partially nested or quadratically invariant problems, our results show that, under the substitutability assumption, linear strategies are optimal and we provide a complete state space characterization of optimal strategies. We also identify a family of information structures that all give the same optimal cost as the centralized information structure under the substitutability assumption. Our results suggest that open-loop substitutability can work as a counterpart of the information structure requirements that enable simplification of decentralized control problems.
Optimal Power Flow with Inelastic Demands for Demand Response in Radial Distribution Networks
Venue: arXiv cs.DS 2016
Year: 2016

The classical optimal power flow problem optimizes the power flow in a power network considering the associated flow and operating constraints. In this paper, we investigate optimal power flow in the context of utility-maximizing demand response management in distribution networks, in which customers' demands are satisfied subject to the operating constraints of voltage and transmission power capacity. The prior results concern only elastic demands that can be partially satisfied, whereas power demands in practice can be inelastic with binary control decisions, which gives rise to a mixed integer programming problem. We shed light on the hardness and approximability by polynomial-time algorithms for optimal power flow problem with inelastic demands. We show that this problem is inapproximable for general power network topology with upper and lower bounds of nodal voltage. Then, we propose an efficient algorithm for a relaxed problem in radial networks with bounded transmission power loss and upper bound of nodal voltage. We derive an approximation ratio between the proposed algorithm and the exact optimal solution. Simulations show that the proposed algorithm can produce close-to-optimal solutions in practice.
Energy-efficient Routing of Hybrid Vehicles
Venue: arXiv cs.DM 2016
Year: 2016

We consider a constrained shortest path problem with two resources. These two resources can be converted into each other in a particular manner. Our practical application is the energy optimal routing of hybrid vehicles. Due to the possibility of converting fuel into electric energy this setting adds new characteristics and new combinatorial possibilities to the common constrained shortest path problem (CSP). We formulate the resulting problem as a generalization of CSP. We show that optimal paths in this model may contain cycles and we state conditions to prevent them. The main contribution is a polynomial-time approximation scheme and a simpler approximation algorithm for computing energy-optimal paths in graphs.
Modeling Non-Functional Application Domain Constraints for Component-Based Robotics Software Systems
Venue: arXiv cs.RO 2016
Year: 2016

Service robots are complex, heterogeneous, software intensive systems built from components. Recent robotics research trends mainly address isolated capabilities on functional level. Non-functional properties, such as responsiveness or deterministic behavior, are addressed only in isolation (if at all). We argue that handling such non-functional properties on system level is a crucial next step. We claim that precise control over application-specific, dynamic execution and interaction behavior of functional components -- i.e. clear computation and communication semantics on model level without hidden code-defined parts -- is a key ingredient thereto. In this paper, we propose modeling concepts for these semantics, and present a meta-model which (i) enables component developers to implement component functionalities without presuming application-specific, system-level attributes, and (ii) enables system integrators to reason about causal dependencies between components as well as system-level data-flow characteristics. This allows to control data-propagation semantics and system properties such as end-to-end latencies during system integration without breaking component encapsulation.
Joint Power Allocation and User Association Optimization for Massive MIMO Systems
Venue: arXiv cs.IT 2016
Year: 2016

This paper investigates the joint power allocation and user association problem in multi-cell Massive MIMO (multiple-input multiple-output) downlink (DL) systems. The target is to minimize the total transmit power consumption when each user is served by an optimized subset of the base stations (BSs), using non-coherent joint transmission. We first derive a lower bound on the ergodic spectral efficiency (SE), which is applicable for any channel distribution and precoding scheme. Closed-form expressions are obtained for Rayleigh fading channels with either maximum ratio transmission (MRT) or zero forcing (ZF) precoding. From these bounds, we further formulate the DL power minimization problems with fixed SE constraints for the users. These problems are proved to be solvable as linear programs, giving the optimal power allocation and BS-user association with low complexity. Furthermore, we formulate a max-min fairness problem which maximizes the worst SE among the users, and we show that it can be solved as a quasi-linear program. Simulations manifest that the proposed methods provide good SE for the users using less transmit power than in small-scale systems and the optimal user association can effectively balance the load between BSs when needed. Even though our framework allows the joint transmission from multiple BSs, there is an overwhelming probability that only one BS is associated with each user at the optimal solution.
Reflections on Monadic Lenses
Venue: arXiv cs.PL 2016
Year: 2016

Bidirectional transformations (bx) have primarily been modeled as pure functions, and do not account for the possibility of the side-effects that are available in most programming languages. Recently several formulations of bx that use monads to account for effects have been proposed, both among practitioners and in academic research. The combination of bx with effects turns out to be surprisingly subtle, leading to problems with some of these proposals and increasing the complexity of others. This paper reviews the proposals for monadic lenses to date, and offers some improved definitions, paying particular attention to the obstacles to naively adding monadic effects to existing definitions of pure bx such as lenses and symmetric lenses, and the subtleties of equivalence of symmetric bidirectional transformations in the presence of effects.
Facial Expression Recognition in the Wild using Rich Deep Features
Venue: arXiv cs.CV 2016
Year: 2016

Facial Expression Recognition is an active area of research in computer vision with a wide range of applications. Several approaches have been developed to solve this problem for different benchmark datasets. However, Facial Expression Recognition in the wild remains an area where much work is still needed to serve real-world applications. To this end, in this paper we present a novel approach towards facial expression recognition. We fuse rich deep features with domain knowledge through encoding discriminant facial patches. We conduct experiments on two of the most popular benchmark datasets; CK and TFE. Moreover, we present a novel dataset that, unlike its precedents, consists of natural - not acted - expression images. Experimental results show that our approach achieves state-of-the-art results over standard benchmarks and our own dataset
Modeling the Dynamics of Discussions in Social Networks
Venue: arXiv cs.SI 2016
Year: 2016

In this paper, a method of modeling the dynamics of electronic discussions is proposed based on the so called FOPDT model (First Order Plus Dead Time) known from the process control. Knowledge of the model points to possibility of estimating dynamic movements in discussions as well as understanding and designing their maintaining and guidance. Real discussions are processed.
Environmental Noise Embeddings for Robust Speech Recognition
Venue: arXiv cs.CL 2016
Year: 2016

We propose a novel deep neural network architecture for speech recognition that explicitly employs knowledge of the background environmental noise within a deep neural network acoustic model. A deep neural network is used to predict the acoustic environment in which the system in being used. The discriminative embedding generated at the bottleneck layer of this network is then concatenated with traditional acoustic features as input to a deep neural network acoustic model. Through a series of experiments on Resource Management, CHiME-3 task, and Aurora4, we show that the proposed approach significantly improves speech recognition accuracy in noisy and highly reverberant environments, outperforming multi-condition training, noise-aware training, i-vector framework, and multi-task learning on both in-domain noise and unseen noise.
Compressing molecular dynamics trajectories: breaking the one-bit-per-sample barrier
Venue: arXiv cs.DC 2016
Year: 2016

Molecular dynamics simulations yield large amounts of trajectory data. For their durable storage and accessibility an efficient compression algorithm is paramount. State of the art domain-specific algorithms combine quantization, Huffman encoding and occasionally domain knowledge. We propose the high resolution trajectory compression scheme (HRTC) that relies on piecewise linear functions to approximate quantized trajectories. By splitting the error budget between quantization and approximation, our approach beats the current state of the art by several orders of magnitude given the same error tolerance. It allows storing samples at far less than one bit per sample. It is simple and fast enough to be integrated into the inner simulation loop, store every time step, and become the primary representation of trajectory data.
Fog Computing: Principles, Architectures, and Applications
Venue: arXiv cs.DC 2016
Year: 2016

The Internet of Everything (IoE) solutions gradually bring every object online, and processing data in centralized cloud does not scale to requirements of such environment. This is because, there are applications such as health monitoring and emergency response that require low latency and delay caused by transferring data to the cloud and then back to the application can seriously impact the performance. To this end, Fog computing has emerged, where cloud computing is extended to the edge of the network to decrease the latency and network congestion. Fog computing is a paradigm for managing a highly distributed and possibly virtualized environment that provides compute and network services between sensors and cloud data centers. This chapter provides background and motivations on emergence of Fog computing and defines its key characteristics. In addition, a reference architecture for Fog computing is presented and recent related development and applications are discussed.
A Sidetrack-Based Algorithm for Finding the k Shortest Simple Paths in a Directed Graph
Venue: arXiv cs.DS 2016
Year: 2016

We present an algorithm for the k shortest simple path problem on weighted directed graphs (kSSP) that is based on Eppstein's algorithm for a similar problem in which paths are allowed to contain cycles. In contrast to most other algorithms for kSSP, ours is not based on Yen's algorithm and does not solve replacement path problems. Its worst-case running time is on par with state-of-the-art algorithms for kSSP. Using our algorithm, one may find O(m) simple paths with a single shortest path tree computation and O(n + m) additional time per path in well-behaved cases, where n is the number of nodes and m is the number of edges. Our computational results show that on random graphs and large road networks, these well-behaved cases are quite common and our algorithm is faster than existing algorithms by an order of magnitude. Further, the running time is far better predictable due to very small dispersion.
Infomax strategies for an optimal balance between exploration and exploitation
Venue: arXiv cs.LG 2016
Year: 2016

Proper balance between exploitation and exploration is what makes good decisions, which achieve high rewards like payoff or evolutionary fitness. The Infomax principle postulates that maximization of information directs the function of diverse systems, from living systems to artificial neural networks. While specific applications are successful, the validity of information as a proxy for reward remains unclear. Here, we consider the multi-armed bandit decision problem, which features arms (slot-machines) of unknown probabilities of success and a player trying to maximize cumulative payoff by choosing the sequence of arms to play. We show that an Infomax strategy (Info-p) which optimally gathers information on the highest mean reward among the arms saturates known optimal bounds and compares favorably to existing policies. The highest mean reward considered by Info-p is not the quantity actually needed for the choice of the arm to play, yet it allows for optimal tradeoffs between exploration and exploitation.
Existence Problem of Telescopers: Beyond the Bivariate Case
Venue: arXiv cs.SC 2016
Year: 2016

In this paper, we solve the existence problem of telescopers for rational functions in three discrete variables. We reduce the problem to that of deciding the summability of bivariate rational functions, which has been solved recently. The existence criteria we present is needed for detecting the termination of Zeilberger's algorithm to the function classes studied in this paper.
Cooperative Joint Localization and Clock Synchronization Based on Gaussian Message Passing in Asynchronous Wireless Networks
Venue: arXiv cs.IT 2016
Year: 2016

Localization and synchronization are very important in many wireless applications such as monitoring and vehicle tracking. Utilizing the same time of arrival (TOA) measurements for simultaneous localization and synchronization is challenging. In this paper, we present a factor graph (FG) representation of the joint localization and time synchronization problem based on TOA measurements, in which the non-line-of-sight measurements are also taken into consideration. On this FG, belief propagation (BP) message passing and variational message passing (VMP) are applied to derive two fully distributed cooperative algorithms with low computational requirements. Due to the nonlinearity in the observation function, it is intractable to compute the messages in closed form and most existing solutions rely on Monte Carlo methods, e.g., particle filtering. We linearize a specific nonlinear term in the expressions of messages, which enables us to use a Gaussian representation for all messages. Accordingly, only the mean and variance have to be updated and transmitted between neighboring nodes, which significantly reduces the communication overhead and computational complexity. A message passing schedule scheme is proposed to trade off between estimation performance and communication overhead. Simulation results show that the proposed algorithms perform very close to particle-based methods with much lower complexity especially in densely connected networks.