OpenRaiser/Intern-Atlas huggingface dataset:
A Comparative study of Transportation Problem under Probabilistic and Fuzzy Uncertainties
Venue: arXiv cs.AI 2013
Year: 2013

Transportation Problem is an important aspect which has been widely studied in Operations Research domain. It has been studied to simulate different real life problems. In particular, application of this Problem in NP- Hard Problems has a remarkable significance. In this Paper, we present a comparative study of Transportation Problem through Probabilistic and Fuzzy Uncertainties. Fuzzy Logic is a computational paradigm that generalizes classical two-valued logic for reasoning under uncertainty. In order to achieve this, the notation of membership in a set needs to become a matter of degree. By doing this we accomplish two things viz., (i) ease of describing human knowledge involving vague concepts and (ii) enhanced ability to develop cost-effective solution to real-world problem. The multi-valued nature of Fuzzy Sets allows handling uncertain and vague information. It is a model-less approach and a clever disguise of Probability Theory. We give comparative simulation results of both approaches and discuss the Computational Complexity. To the best of our knowledge, this is the first work on comparative study of Transportation Problem using Probabilistic and Fuzzy Uncertainties.
Proof in Context -- Web Editing with Rich, Modeless Contextual Feedback
Venue: arXiv cs.HC 2013
Year: 2013

The Agora system is a prototypical Wiki for formal mathematics: a web-based system for collaborating on formal mathematics, intended to support informal documentation of formal developments. This system requires a reusable proof editor component, both for collaborative editing of documents, and for embedding in the resulting documents. This paper describes the design of Agora's asynchronous editor, that is generic enough to support different tools working on editor content and providing contextual information, with interactive theorem proverss being a special, but important, case described in detail for the Coq theorem prover.
Theorema 2.0: A Graphical User Interface for a Mathematical Assistant System
Venue: arXiv cs.MS 2013
Year: 2013

Theorema 2.0 stands for a re-design including a complete re-implementation of the Theorema system, which was originally designed, developed, and implemented by Bruno Buchberger and his Theorema group at RISC. In this paper, we present the first prototype of a graphical user interface (GUI) for the new system. It heavily relies on powerful interactive capabilities introduced in recent releases of the underlying Mathematica system, most importantly the possibility of having dynamic objects connected to interface elements like sliders, menus, check-boxes, radio-buttons and the like. All these features are fully integrated into the Mathematica programming environment and allow the implementation of a modern user interface.
Revisiting Co-Processing for Hash Joins on the Coupled CPU-GPU Architecture
Venue: arXiv cs.DC 2013
Year: 2013

Query co-processing on graphics processors (GPUs) has become an effective means to improve the performance of main memory databases. However, the relatively low bandwidth and high latency of the PCI-e bus are usually bottleneck issues for co-processing. Recently, coupled CPU-GPU architectures have received a lot of attention, e.g. AMD APUs with the CPU and the GPU integrated into a single chip. That opens up new opportunities for optimizing query co-processing. In this paper, we experimentally revisit hash joins, one of the most important join algorithms for main memory databases, on a coupled CPU-GPU architecture. Particularly, we study the fine-grained co-processing mechanisms on hash joins with and without partitioning. The co-processing outlines an interesting design space. We extend existing cost models to automatically guide decisions on the design space. Our experimental results on a recent AMD APU show that (1) the coupled architecture enables fine-grained co-processing and cache reuses, which are inefficient on discrete CPU-GPU architectures; (2) the cost model can automatically guide the design and tuning knobs in the design space; (3) fine-grained co-processing achieves up to 53%, 35% and 28% performance improvement over CPU-only, GPU-only and conventional CPU-GPU co-processing, respectively. We believe that the insights and implications from this study are initial yet important for further research on query co-processing on coupled CPU-GPU architectures.
Modal Analysis with Compressive Measurements
Venue: arXiv cs.IT 2013
Year: 2013

Structural Health Monitoring (SHM) systems are critical for monitoring aging infrastructure (such as buildings or bridges) in a cost-effective manner. Such systems typically involve collections of battery-operated wireless sensors that sample vibration data over time. After the data is transmitted to a central node, modal analysis can be used to detect damage in the structure. In this paper, we propose and study three frameworks for Compressive Sensing (CS) in SHM systems; these methods are intended to minimize power consumption by allowing the data to be sampled and/or transmitted more efficiently. At the central node, all of these frameworks involve a very simple technique for estimating the structure's mode shapes without requiring a traditional CS reconstruction of the vibration signals; all that is needed is to compute a simple Singular Value Decomposition. We provide theoretical justification (including measurement bounds) for each of these techniques based on the equations of motion describing a simplified Multiple-Degree-Of-Freedom (MDOF) system, and we support our proposed techniques using simulations based on synthetic and real data.
Using Clustering to extract Personality Information from socio economic data
Venue: arXiv cs.LG 2013
Year: 2013

It has become apparent that models that have been applied widely in economics, including Machine Learning techniques and Data Mining methods, should take into consideration principles that derive from the theories of Personality Psychology in order to discover more comprehensive knowledge regarding complicated economic behaviours. In this work, we present a method to extract Behavioural Groups by using simple clustering techniques that can potentially reveal aspects of the Personalities for their members. We believe that this is very important because the psychological information regarding the Personalities of individuals is limited in real world applications and because it can become a useful tool in improving the traditional models of Knowledge Economy.
Variance in System Dynamics and Agent Based Modelling Using the SIR Model of Infectious Disease
Venue: arXiv cs.CE 2013
Year: 2013

Classical deterministic simulations of epidemiological processes, such as those based on System Dynamics, produce a single result based on a fixed set of input parameters with no variance between simulations. Input parameters are subsequently modified on these simulations using Monte-Carlo methods, to understand how changes in the input parameters affect the spread of results for the simulation. Agent Based simulations are able to produce different output results on each run based on knowledge of the local interactions of the underlying agents and without making any changes to the input parameters. In this paper we compare the influence and effect of variation within these two distinct simulation paradigms and show that the Agent Based simulation of the epidemiological SIR (Susceptible, Infectious, and Recovered) model is more effective at capturing the natural variation within SIR compared to an equivalent model using System Dynamics with Monte-Carlo simulation. To demonstrate this effect, the SIR model is implemented using both System Dynamics (with Monte-Carlo simulation) and Agent Based Modelling based on previously published empirical data.
A Web-based modeling tool for the SEMAT Essence theory of Software Engineering
Venue: arXiv cs.SE 2013
Year: 2013

As opposed to more mature subjects, software engineering lacks general theories to establish its foundations as a discipline. The Essence Theory of software engineering (Essence) has been proposed by the Software Engineering Methods and Theory (SEMAT) initiative. Essence goal is to develop a theoretically sound basis for software engineering practice and its wide adoption. Essence is yet far from reaching academic and industry adoption. Reasons include a struggle to foresee its utilization potential and the lack of tools implementing it. SEMAT Accelerator (SematAcc) is a Web-positioning tool for a software engineering endeavor, which implements the SEMAT's Essence kernel. SematAcc allows using Essence, thus helping to understand it. The tool enables teaching, adopting, and researching Essence in controlled experiments and case studies.
A PAC-Bayesian Tutorial with A Dropout Bound
Venue: arXiv cs.LG 2013
Year: 2013

This tutorial gives a concise overview of existing PAC-Bayesian theory focusing on three generalization bounds. The first is an Occam bound which handles rules with finite precision parameters and which states that generalization loss is near training loss when the number of bits needed to write the rule is small compared to the sample size. The second is a PAC-Bayesian bound providing a generalization guarantee for posterior distributions rather than for individual rules. The PAC-Bayesian bound naturally handles infinite precision rule parameters, $L_2$ regularization, {\em provides a bound for dropout training}, and defines a natural notion of a single distinguished PAC-Bayesian posterior distribution. The third bound is a training-variance bound --- a kind of bias-variance analysis but with bias replaced by expected training loss. The training-variance bound dominates the other bounds but is more difficult to interpret. It seems to suggest variance reduction methods such as bagging and may ultimately provide a more meaningful analysis of dropouts.
Inconsistency and Accuracy of Heuristics with A* Search
Venue: arXiv cs.AI 2013
Year: 2013

Many studies in heuristic search suggest that the accuracy of the heuristic used has a positive impact on improving the performance of the search. In another direction, historical research perceives that the performance of heuristic search algorithms, such as A* and IDA*, can be improved by requiring the heuristics to be consistent -- a property satisfied by any perfect heuristic. However, a few recent studies show that inconsistent heuristics can also be used to achieve a large improvement in these heuristic search algorithms. These results leave us a natural question: which property of heuristics, accuracy or consistency/inconsistency, should we focus on when building heuristics? While there are studies on the heuristic accuracy with the assumption of consistency, no studies on both the inconsistency and the accuracy of heuristics are known to our knowledge. In this study, we investigate the relationship between the inconsistency and the accuracy of heuristics with A* search. Our analytical result reveals a correlation between these two properties. We then run experiments on the domain for the Knapsack problem with a family of practical heuristics. Our empirical results show that in many cases, the more accurate heuristics also have higher level of inconsistency and result in fewer node expansions by A*.
Duality Codes and the Integrality Gap Bound for Index Coding
Venue: arXiv cs.IT 2013
Year: 2013

This paper considers a base station that delivers packets to multiple receivers through a sequence of coded transmissions. All receivers overhear the same transmissions. Each receiver may already have some of the packets as side information, and requests another subset of the packets. This problem is known as the index coding problem and can be represented by a bipartite digraph. An integer linear program is developed that provides a lower bound on the minimum number of transmissions required for any coding algorithm. Conversely, its linear programming relaxation is shown to provide an upper bound that is achievable by a simple form of vector linear coding. Thus, the information theoretic optimum is bounded by the integrality gap between the integer program and its linear relaxation. In the special case when the digraph has a planar structure, the integrality gap is shown to be zero, so that exact optimality is achieved. Finally, for non-planar problems, an enhanced integer program is constructed that provides a smaller integrality gap. The dual of this problem corresponds to a more sophisticated partial clique coding strategy that time-shares between Reed-Solomon erasure codes. This work illuminates the relationship between index coding, duality, and integrality gaps between integer programs and their linear relaxations.
A Haskell Library for Term Rewriting
Venue: arXiv cs.PL 2013
Year: 2013

We present a Haskell library for first-order term rewriting covering basic operations on positions, terms, contexts, substitutions and rewrite rules. This effort is motivated by the increasing number of term rewriting tools that are written in Haskell.
Stability Analysis of Continuous-Time Switched Systems with a Random Switching Signal
Venue: arXiv cs.SY 2013
Year: 2013

This paper is concerned with the stability analysis of continuous-time switched systems with a random switching signal. The switching signal manifests its characteristics with that the dwell time in each subsystem consists of a fixed part and a random part. The stochastic stability of such switched systems is studied using a Lyapunov approach. A necessary and sufficient condition is established in terms of linear matrix inequalities. The effect of the random switching signal on system stability is illustrated by a numerical example and the results coincide with our intuition.
Polar Codes with Dynamic Frozen Symbols and Their Decoding by Directed Search
Venue: arXiv cs.IT 2013
Year: 2013

A novel construction of polar codes with dynamic frozen symbols is proposed. The proposed codes are subcodes of extended BCH codes, which ensure sufficiently high minimum distance. Furthermore, a decoding algorithm is proposed, which employs estimates of the not-yet-processed bit channel error probabilities to perform directed search in code tree, reducing thus the total number of iterations.
Energy Efficient Coordinated Beamforming for Multi-cell MISO Systems
Venue: arXiv cs.IT 2013
Year: 2013

In this paper, we investigate the optimal energy efficient coordinated beamforming in multi-cell multiple-input single-output (MISO) systems with $K$ multiple-antenna base stations (BS) and $K$ single-antenna mobile stations (MS), where each BS sends information to its own intended MS with cooperatively designed transmit beamforming. We assume single user detection at the MS by treating the interference as noise. By taking into account a realistic power model at the BS, we characterize the Pareto boundary of the achievable energy efficiency (EE) region of the $K$ links, where the EE of each link is defined as the achievable data rate at the MS divided by the total power consumption at the BS. Since the EE of each link is non-cancave (which is a non-concave function over an affine function), characterizing this boundary is difficult. To meet this challenge, we relate this multi-cell MISO system to cognitive radio (CR) MISO channels by applying the concept of interference temperature (IT), and accordingly transform the EE boundary characterization problem into a set of fractional concave programming problems. Then, we apply the fractional concave programming technique to solve these fractional concave problems, and correspondingly give a parametrization for the EE boundary in terms of IT levels. Based on this characterization, we further present a decentralized algorithm to implement the multi-cell coordinated beamforming, which is shown by simulations to achieve the EE Pareto boundary.
On The Fast Fading Multiple-Antenna Gaussian Broadcast Channel with Confidential Messages and Partial CSIT
Venue: arXiv cs.IT 2013
Year: 2013

In wiretap channels the eavesdropper's channel state information (CSI) is commonly assumed to be known at transmitter, fully or partially. However, under perfect secrecy constraint the eavesdropper may not be motivated to feedback any correct CSI. In this paper we consider a more feasible problem for the transmitter to have eavesdropper's CSI. That is, the fast fading multiple-antenna Gaussian broadcast channels (FMGBC-CM) with confidential messages, where both receivers are legitimate users such that they both are willing to feedback accurate CSI to maintain their secure transmission, and not to be eavesdropped by the other. We assume that only the statistics of the channel state information are known by the transmitter. We first show the necessary condition for the FMGBC-CM not to be degraded to the common wiretap channels. Then we derive the achievable rate region for the FMGBC-CM where the channel input covariance matrices and the inflation factor are left unknown and to be solved. After that we provide an analytical solution to the channel input covariance matrices. We also propose an iterative algorithm to solve the channel input covariance matrices and the inflation factor. Due to the complicated rate region formulae in normal SNR, we resort to low SNR analysis to investigate the characteristics of the channel. Finally, numerical examples show that under perfect secrecy constraint both users can achieve positive rates simultaneously, which verifies our derived necessary condition. Numerical results also elucidate the effectiveness of the analytic solution and proposed algorithm of solving the channel input covariance matrices and the inflation factor under different conditions.
Image Fusion Technologies In Commercial Remote Sensing Packages
Venue: arXiv cs.CV 2013
Year: 2013

Several remote sensing software packages are used to the explicit purpose of analyzing and visualizing remotely sensed data, with the developing of remote sensing sensor technologies from last ten years. Accord-ing to literature, the remote sensing is still the lack of software tools for effective information extraction from remote sensing data. So, this paper provides a state-of-art of multi-sensor image fusion technologies as well as review on the quality evaluation of the single image or fused images in the commercial remote sensing pack-ages. It also introduces program (ALwassaiProcess) developed for image fusion and classification.
Detection of Outer Rotations on 3D-Vector Fields with Iterative Geometric Correlation and its Efficiency
Venue: arXiv cs.CV 2013
Year: 2013

Correlation is a common technique for the detection of shifts. Its generalization to the multidimensional geometric correlation in Clifford algebras has been proven a useful tool for color image processing, because it additionally contains information about a rotational misalignment. But so far the exact correction of a three-dimensional outer rotation could only be achieved in certain special cases. In this paper we prove that applying the geometric correlation iteratively has the potential to detect the outer rotational misalignment for arbitrary three-dimensional vector fields. We further present the explicit iterative algorithm, analyze its efficiency detecting the rotational misalignment in the color space of a color image. The experiments suggest a method for the acceleration of the algorithm, which is practically tested with great success.
Strong Price of Anarchy and Coalitional Dynamics
Venue: arXiv cs.GT 2013
Year: 2013

We introduce a framework for studying the effect of cooperation on the quality of outcomes in utility games. Our framework is a coalitional analog of the smoothness framework of non-cooperative games. Coalitional smoothness implies bounds on the strong price of anarchy, the loss of quality of coalitionally stable outcomes, as well as bounds on coalitional versions of coarse correlated equilibria and sink equilibria, which we define as out-of-equilibrium myopic behavior as determined by a natural coalitional version of best-response dynamics. Our coalitional smoothness framework captures existing results bounding the strong price of anarchy of network design games. We show that in any monotone utility-maximization game, if each player's utility is at least his marginal contribution to the welfare, then the strong price of anarchy is at most 2. This captures a broad class of games, including games with a very high price of anarchy. Additionally, we show that in potential games the strong price of anarchy is close to the price of stability, the quality of the best Nash equilibrium.
Compactly Supported Tensor Product Complex Tight Framelets with Directionality
Venue: arXiv cs.IT 2013
Year: 2013

Although tensor product real-valued wavelets have been successfully applied to many high-dimensional problems, they can only capture well edge singularities along the coordinate axis directions. As an alternative and improvement of tensor product real-valued wavelets and dual tree complex wavelet transform, recently tensor product complex tight framelets with increasing directionality have been introduced in [8] and applied to image denoising in [13]. Despite several desirable properties, the directional tensor product complex tight framelets constructed in [8,13] are bandlimited and do not have compact support in the space/time domain. Since compactly supported wavelets and framelets are of great interest and importance in both theory and application, it remains as an unsolved problem whether there exist compactly supported tensor product complex tight framelets with directionality. In this paper, we shall satisfactorily answer this question by proving a theoretical result on directionality of tight framelets and by introducing an algorithm to construct compactly supported complex tight framelets with directionality. Our examples show that compactly supported complex tight framelets with directionality can be easily derived from any given eligible low-pass filters and refinable functions. Several examples of compactly supported tensor product complex tight framelets with directionality have been presented.
Index Coding Problem with Side Information Repositories
Venue: arXiv cs.IT 2013
Year: 2013

To tackle the expected enormous increase in mobile video traffic in cellular networks, an architecture involving a base station along with caching femto stations (referred to as helpers), storing popular files near users, has been proposed [1]. The primary benefit of caching is the enormous increase in downloading rate when a popular file is available at helpers near a user requesting that file. In this work, we explore a secondary benefit of caching in this architecture through the lens of index coding. We assume a system with n users and constant number of caching helpers. Only helpers store files, i.e. have side information. We investigate the following scenario: Each user requests a distinct file that is not found in the set of helpers nearby. Users are served coded packets (through an index code) by an omniscient base station. Every user decodes its desired packet from the coded packets and the side information packets from helpers nearby. We assume that users can obtain any file stored in their neighboring helpers without incurring transmission costs. With respect to the index code employed, we investigate two achievable schemes: 1) XOR coloring based on coloring of the side information graph associated with the problem and 2)Vector XOR coloring based on fractional coloring of the side information graph. We show that the general problem reduces to a canonical problem where every user is connected to exactly one helper under some topological constraints. For the canonical problem, with constant number of helpers (k), we show that the complexity of computing the best XOR/vector XOR coloring schemes are polynomial in the number of users n. The result exploits a special complete bi-partite structure that the side information graphs exhibit for any finite k.