OpenRaiser/Intern-Atlas huggingface dataset:
Approximation Algorithms for Budget Constrained Network Upgradeable Problems
Venue: arXiv cs.DS 2014
Year: 2014

We study budget constrained network upgradeable problems. We are given an undirected edge weighted graph $G=(V,E)$ where the weight an edge $e \in E$ can be upgraded for a cost $c(e)$. Given a budget $B$ for improvement, the goal is to find a subset of edges to be upgraded so that the resulting network is optimum for $B$. The results obtained in this paper include the following. Maximum Weight Constrained Spanning Tree We present a randomized algorithm for the problem of weight upgradeable budget constrained maximum spanning tree on a general graph. This returns a spanning tree $\mathcal{T}^{'}$ which is feasible within the budget $B$, such that $\Pr [ l(\mathcal{T}^{'}) \geq (1-ε)\text{OPT}\text{ , } c(\mathcal{T}^{'} ) \leq B] \ge 1-\frac{1}{n}$ (where $l$ and $c$ denote the length and cost of the tree respectively), for any fixed $ε>0$, in time polynomial in $|V|=n$, $|E|=m$. Our results extend to the minimization version also. Previously Krumke et. al. \cite{krumke} presented a$(1+\frac{1}γ, 1+ γ)$ bicriteria approximation algorithm for any fixed $γ>0$ for this problem in general graphs for a more general cost upgrade function. The result in this paper improves their 0/1 cost upgrade model. Longest Path in a DAG We consider the problem of weight improvable longest path in a $n$ vertex DAG and give a $O(n^3)$ algorithm for the problem when there is a bound on the number of improvements allowed. We also give a $(1-ε)$-approximation which runs in $O(\frac{n^4}ε)$ time for the budget constrained version. Similar results can be achieved also for the problem of shortest paths in a DAG.
Turing Test for the Internet of Things
Venue: arXiv cs.AI 2014
Year: 2014

How smart is your kettle? How smart are things in your kitchen, your house, your neighborhood, on the internet? With the advent of Internet of Things, and the move of making devices `smart' by utilizing AI, a natural question arrises, how can we evaluate the progress. The standard way of evaluating AI is through the Turing Test. While Turing Test was designed for AI; the device that it was tailored to was a computer. Applying the test to variety of devices that constitute Internet of Things poses a number of challenges which could be addressed through a number of adaptations.
Min-max piecewise constant optimal control for multi-model linear systems
Venue: arXiv cs.SY 2014
Year: 2014

The present work addresses a finite-horizon linear-quadratic optimal control problem for uncertain systems driven by piecewise constant controls. The precise values of the system parameters are unknown, but assumed to belong to a finite set (i.e., there exist only finitely many possible models for the plant). Uncertainty is dealt with using a min-max approach (i.e., we seek the best control for the worst possible plant). The optimal control is derived using a multi-model version of Lagrange's multipliers method, which specifies the control in terms of a discrete-time Riccati equation and an optimization problem over a simplex. A numerical algorithm for computing the optimal control is proposed and tested by simulation.
Easy-to-Use On-the-Fly Binary Program Acceleration on Many-Cores
Venue: arXiv cs.DC 2014
Year: 2014

This paper introduces Binary Acceleration At Runtime (BAAR), an easy-to-use on-the-fly binary acceleration mechanism which aims to tackle the problem of enabling existent software to automatically utilize accelerators at runtime. BAAR is based on the LLVM Compiler Infrastructure and has a client-server architecture. The client runs the program to be accelerated in an environment which allows program analysis and profiling. Program parts which are identified as suitable for the available accelerator are exported and sent to the server. The server optimizes these program parts for the accelerator and provides RPC execution for the client. The client transforms its program to utilize accelerated execution on the server for offloaded program parts. We evaluate our work with a proof-of-concept implementation of BAAR that uses an Intel Xeon Phi 5110P as the acceleration target and performs automatic offloading, parallelization and vectorization of suitable program parts. The practicality of BAAR for real-world examples is shown based on a study of stencil codes. Our results show a speedup of up to 4x without any developer-provided hints and 5.77x with hints over the same code compiled with the Intel Compiler at optimization level O2 and running on an Intel Xeon E5-2670 machine. Based on our insights gained during implementation and evaluation we outline future directions of research, e.g., offloading more fine-granular program parts than functions, a more sophisticated communication mechanism or introducing on-stack-replacement.
Belief revision in the propositional closure of a qualitative algebra
Venue: arXiv cs.AI 2014
Year: 2014

Belief revision is an operation that aims at modifying old be-liefs so that they become consistent with new ones. The issue of belief revision has been studied in various formalisms, in particular, in qualitative algebras (QAs) in which the result is a disjunction of belief bases that is not necessarily repre-sentable in a QA. This motivates the study of belief revision in formalisms extending QAs, namely, their propositional clo-sures: in such a closure, the result of belief revision belongs to the formalism. Moreover, this makes it possible to define a contraction operator thanks to the Harper identity. Belief revision in the propositional closure of QAs is studied, an al-gorithm for a family of revision operators is designed, and an open-source implementation is made freely available on the web.
Reconfiguration of Cliques in a Graph
Venue: arXiv cs.DS 2014
Year: 2014

We study reconfiguration problems for cliques in a graph, which determine whether there exists a sequence of cliques that transforms a given clique into another one in a step-by-step fashion. As one step of a transformation, we consider three different types of rules, which are defined and studied in reconfiguration problems for independent sets. We first prove that all the three rules are equivalent in cliques. We then show that the problems are PSPACE-complete for perfect graphs, while we give polynomial-time algorithms for several classes of graphs, such as even-hole-free graphs and cographs. In particular, the shortest variant, which computes the shortest length of a desired sequence, can be solved in polynomial time for chordal graphs, bipartite graphs, planar graphs, and bounded treewidth graphs.
Resolving multi-proxy transitive vote delegation
Venue: arXiv cs.MA 2014
Year: 2014

Solving a delegation graph for transitive votes is already a non-trivial task for many programmers. When extending the current main paradigm, where each voter can only appoint a single transitive delegation, to a system where each vote can be separated over multiple delegations, solving the delegation graph becomes even harder. This article presents a solution of an example graph, and a non-formal proof of why this algorithm works.
Permutation Reconstruction from MinMax-Betweenness Constraints
Venue: arXiv cs.DS 2014
Year: 2014

In this paper, we investigate the reconstruction of permutations on {1, 2, ..., n} from betweenness constraints involving the minimum and the maximum element located between t and t+1, for all t=1, 2, ..., n-1. We propose two variants of the problem (directed and undirected), and focus first on the directed version, for which we draw up general features and design a polynomial algorithm in a particular case. Then, we investigate necessary and sufficient conditions for the uniqueness of the reconstruction in both directed and undirected versions, using a parameter k whose variation controls the stringency of the betweenness constraints. We finally point out open problems.
Kernel Methods on the Riemannian Manifold of Symmetric Positive Definite Matrices
Venue: arXiv cs.CV 2014
Year: 2014

Symmetric Positive Definite (SPD) matrices have become popular to encode image information. Accounting for the geometry of the Riemannian manifold of SPD matrices has proven key to the success of many algorithms. However, most existing methods only approximate the true shape of the manifold locally by its tangent plane. In this paper, inspired by kernel methods, we propose to map SPD matrices to a high dimensional Hilbert space where Euclidean geometry applies. To encode the geometry of the manifold in the mapping, we introduce a family of provably positive definite kernels on the Riemannian manifold of SPD matrices. These kernels are derived from the Gaussian ker- nel, but exploit different metrics on the manifold. This lets us extend kernel-based algorithms developed for Euclidean spaces, such as SVM and kernel PCA, to the Riemannian manifold of SPD matrices. We demonstrate the benefits of our approach on the problems of pedestrian detection, ob- ject categorization, texture analysis, 2D motion segmentation and Diffusion Tensor Imaging (DTI) segmentation.
A Framework for Shape Analysis via Hilbert Space Embedding
Venue: arXiv cs.CV 2014
Year: 2014

We propose a framework for 2D shape analysis using positive definite kernels defined on Kendall's shape manifold. Different representations of 2D shapes are known to generate different nonlinear spaces. Due to the nonlinearity of these spaces, most existing shape classification algorithms resort to nearest neighbor methods and to learning distances on shape spaces. Here, we propose to map shapes on Kendall's shape manifold to a high dimensional Hilbert space where Euclidean geometry applies. To this end, we introduce a kernel on this manifold that permits such a mapping, and prove its positive definiteness. This kernel lets us extend kernel-based algorithms developed for Euclidean spaces, such as SVM, MKL and kernel PCA, to the shape manifold. We demonstrate the benefits of our approach over the state-of-the-art methods on shape classification, clustering and retrieval.
A Study of Sindhi Related and Arabic Script Adapted languages Recognition
Venue: arXiv cs.CV 2014
Year: 2014

A large number of publications are available for the Optical Character Recognition (OCR). Significant researches, as well as articles are present for the Latin, Chinese and Japanese scripts. Arabic script is also one of mature script from OCR perspective. The adaptive languages which share Arabic script or its extended characters; still lacking the OCRs for their language. In this paper we present the efforts of researchers on Arabic and its related and adapted languages. This survey is organized in different sections, in which introduction is followed by properties of Sindhi Language. OCR process techniques and methods used by various researchers are presented. The last section is dedicated for future work and conclusion is also discussed.
Combining the Best of Graphical Models and ConvNets for Semantic Segmentation
Venue: arXiv cs.CV 2014
Year: 2014

We present a two-module approach to semantic segmentation that incorporates Convolutional Networks (CNNs) and Graphical Models. Graphical models are used to generate a small (5-30) set of diverse segmentations proposals, such that this set has high recall. Since the number of required proposals is so low, we can extract fairly complex features to rank them. Our complex feature of choice is a novel CNN called SegNet, which directly outputs a (coarse) semantic segmentation. Importantly, SegNet is specifically trained to optimize the corpus-level PASCAL IOU loss function. To the best of our knowledge, this is the first CNN specifically designed for semantic segmentation. This two-module approach achieves $52.5\%$ on the PASCAL 2012 segmentation challenge.
Adaptive Resource Management for Multimedia Applications in Femtocellular and Macrocellular Networks
Venue: arXiv cs.NI 2014
Year: 2014

The increasing demands of various high data rate wireless applications have been seen in the recent years and it will continue in the future. To fulfill these demands, the limited existing wireless resources should be utilized properly or new wireless technology should be developed. Therefore, we propose some novel idea to manage the wireless resources and deployment of femtocellular network technology. The study was mainly divided into two parts: (a) femtocellular network deployment and resource allocation and (b) resource management for macrocellular networks. The femtocellular network deployment scenarios, integrated femtocell/macrocell network architectures, cost-effective frequency planning, and mobility management schemes are presented in first part. In the second part, we provide a CAC based on adaptive bandwidth allocation for the wireless network in. The proposed CAC relies on adaptive multi-level bandwidth-allocation scheme for non-real-time calls. We propose video service provisioning over wireless networks. We provide a QoS adaptive radio resource allocation as well as popularity based bandwidth allocation schemes for scalable videos over wireless cellular networks. All the proposed schemes are verified through several numerical and simulation results. The research results presented in this dissertation clearly imply the advantages of our proposed schemes.
LH*TH: New fast Scalable Distributed Data Structures (SDDS)
Venue: arXiv cs.DC 2014
Year: 2014

Proposed in 1993 the Scalable Distributed Data Structures (SDDSs) became a profile of basis for the data management on Multi computer. In this paper we propose an organization of a LH* bucket based on the trie hashing in order to improve times of different access request.
A New System For Recording The Radiological Effective Doses For Patients Investigated by Imaging Methods
Venue: arXiv cs.CE 2014
Year: 2014

In this paper the project of an integrated system for radiation safety and security of the patients investigated by radiological imaging methods is presented. The new system is based on smart cards and Public Key Infrastructure. The new system allows radiation effective dose data storage and a more accurate reporting system.
Adaptive Downlink CoMP in Heterogeneous Cellular Networks with Imperfect Overhead Messaging
Venue: arXiv cs.IT 2014
Year: 2014

Coordinated multi-point (CoMP) transmission is an effective means of improving network throughput in heterogeneous cellular networks (HetNets). However, its performance is seriously weakened if imperfect coordination happens between base stations (BSs). Many prior CoMP works do not consider inter-cell overhead message delays such that a seemingly astonishing CoMP throughput gain is attained. In this paper, the quantization error and delay that actually exist in overhead messages was modeled and we developed a much tractable SIR model based on the stochastic geometry framework. We proposed adaptive CoMP that is applied to downlink zero-forcing beamforming (ZFBF) and it can mitigate the interference from the coordinated cells with delayed overhead messages. The bounds on the complementary cumulative distribution function (CCDF) of the SIR of a user are characterized such that the average throughput of a user is able to be analytically evaluated. Numerical results show that the proposed adaptive CoMP scheme can make the throughput gain very robust to the overhead delay and thus significantly increase the throughput even when BSs are not perfectly coordinated.
CCN Forwarding Strategies for Multihomed Mobile Terminals
Venue: arXiv cs.NI 2014
Year: 2014

Current IP-based networks are unable to fully exploit the capabilities of the increasing number of multihomed mobile terminals. We argue that Content-Centric Networking (CCN), a novel networking architecture based on named information objects, can fill the gap. In this paper, we elicit requirements for CCN packet forwarding on multihomed mobile terminals. We categorize CCN forwarding strategies according to their ability to fulfill these requirements and provide a real-world performance evaluation in the current CCNx prototype implementation. Moreover, we describe the initial design of an advanced multipath forwarding strategy.
Fixed Point Algorithm Based on Quasi-Newton Method for Convex Minimization Problem with Application to Image Deblurring
Venue: arXiv cs.CV 2014
Year: 2014

Solving an optimization problem whose objective function is the sum of two convex functions has received considerable interests in the context of image processing recently. In particular, we are interested in the scenario when a non-differentiable convex function such as the total variation (TV) norm is included in the objective function due to many variational models established in image processing have this nature. In this paper, we propose a fast fixed point algorithm based on the quasi-Newton method for solving this class of problem, and apply it in the field of TV-based image deblurring. The novel method is derived from the idea of the quasi-Newton method, and the fixed-point algorithms based on the proximity operator, which were widely investigated very recently. Utilizing the non-expansion property of the proximity operator we further investigate the global convergence of the proposed algorithm. Numerical experiments on image deblurring problem with additive or multiplicative noise are presented to demonstrate that the proposed algorithm is superior to the recently developed fixed-point algorithm in the computational efficiency.
Adaptive Delay-Tolerant DSTBC in Opportunistic Relaying Cooperative MIMO Systems
Venue: arXiv cs.IT 2014
Year: 2014

An adaptive delay-tolerant distributed space-time coding (DSTC) scheme with feedback is proposed for two-hop cooperative multiple-input multiple-output (MIMO) networks using an amplify-and-forward strategy and opportunistic relaying algorithms. Maximum likelihood receivers and adjustable code matrices are considered subject to a power constraint. In the proposed delay-tolerant DSTC scheme, an adjustable code matrix is employed to transform the space-time coded matrices at the relay nodes. Stochastic gradient algorithms are developed with reduced computational complexity to estimate the parameters of the code matrix. Simulation results show that the proposed algorithms obtain significant performance gains and address the delay issue in cooperative MIMO systems as compared to existing DSTC schemes.
Physical-layer Network Coding in Two-Way Heterogeneous Cellular Networks with Power Imbalance
Venue: arXiv cs.NI 2014
Year: 2014

The growing demand for high-speed data, quality of service (QoS) assurance and energy efficiency has triggered the evolution of 4G LTE-A networks to 5G and beyond. Interference is still a major performance bottleneck. This paper studies the application of physical-layer network coding (PNC), a technique that exploits interference, in heterogeneous cellular networks. In particular, we propose a rate-maximising relay selection algorithm for a single cell with multiple relays based on the decode-and-forward strategy. With nodes transmitting at different powers, the proposed algorithm adapts the resource allocation according to the differing link rates and we prove theoretically that the optimisation problem is log-concave. The proposed technique is shown to perform significantly better than the widely studied selection-cooperation technique. We then undertake an experimental study on a software radio platform of the decoding performance of PNC with unbalanced SNRs in the multiple-access transmissions. This problem is inherent in cellular networks and it is shown that with channel coding and decoders based on multiuser detection and successive interference cancellation, the performance is better with power imbalance. This paper paves the way for further research in multi-cell PNC, resource allocation, and the implementation of PNC with higher-order modulations and advanced coding techniques.
Towards Error Handling in a DSL for Robot Assembly Tasks
Venue: arXiv cs.RO 2014
Year: 2014

This work-in-progress paper presents our work with a domain specific language (DSL) for tackling the issue of programming robots for small-sized batch production. We observe that as the complexity of assembly increases so does the likelihood of errors, and these errors need to be addressed. Nevertheless, it is essential that programming and setting up the assembly remains fast, allows quick changeovers, easy adjustments and reconfigurations. In this paper we present an initial design and implementation of extending an existing DSL for assembly operations with error specification, error handling and advanced move commands incorporating error tolerance. The DSL is used as part of a framework that aims at tackling uncertainties through a probabilistic approach.
Baseband and RF Hardware Impairments in Full-Duplex Wireless Systems: Experimental Characterisation and Suppression
Venue: arXiv cs.IT 2014
Year: 2014

Hardware imperfections can significantly reduce the performance of full-duplex wireless systems by introducing non-idealities and random effects that make it challenging to fully suppress self-interference. Previous research has mostly focused on analyzing the impact of hardware imperfections on full-duplex systems, based on simulations and theoretical models. In this paper, we follow a measurement-based approach to experimentally identify and isolate these hardware imperfections leading to residual self-interference in full-duplex nodes. Our measurements show the important role of images arising from in-phase and quadrature (IQ) imbalance in the mixers. We also observe base-band non-linearities in the digital-to-analog converters (DAC), which can introduce strong harmonic components that have not been previously considered. A corresponding general mathematical model to suppress these components of the self-interference signal arising from the hardware non-idealities is developed from the observations and measurements. Results from a 10 MHz bandwidth full-duplex OFDM system, operating at 2.48 GHz, show up to 13 dB additional suppression, relative to state-of-the-art implementations can be achieved by jointly compensating for IQ imbalance and DAC non-linearities.
Generalized Vietoris Bisimulations
Venue: arXiv cs.LO 2014
Year: 2014

We introduce and study bisimulations for coalgebras on Stone spaces [14]. Our notion of bisimulation is sound and complete for behavioural equivalence, and generalizes Vietoris bisimulations [4]. The main result of our paper is that bisimulation for a $\mathbf{Stone}$ coalgebra is the topological closure of bisimulation for the underlying $\mathbf{Set}$ coalgebra.
Distributed Fronthaul Compression and Joint Signal Recovery in Cloud-RAN
Venue: arXiv cs.IT 2014
Year: 2014

The cloud radio access network (C-RAN) is a promising network architecture for future mobile communications, and one practical hurdle for its large scale implementation is the stringent requirement of high capacity and low latency fronthaul connecting the distributed remote radio heads (RRH) to the centralized baseband pools (BBUs) in the C-RAN. To improve the scalability of C-RAN networks, it is very important to take the fronthaul loading into consideration in the signal detection, and it is very desirable to reduce the fronthaul loading in C-RAN systems. In this paper, we consider uplink C-RAN systems and we propose a distributed fronthaul compression scheme at the distributed RRHs and a joint recovery algorithm at the BBUs by deploying the techniques of distributed compressive sensing (CS). Different from conventional distributed CS, the CS problem in C-RAN system needs to incorporate the underlying effect of multi-access fading for the end-to-end recovery of the transmitted signals from the users. We analyze the performance of the proposed end-to-end signal recovery algorithm and we show that the aggregate measurement matrix in C-RAN systems, which contains both the distributed fronthaul compression and multiaccess fading, can still satisfy the restricted isometry property with high probability. Based on these results, we derive tradeoff results between the uplink capacity and the fronthaul loading in C-RAN systems.