OpenRaiser/Intern-Atlas huggingface dataset:
Approximation Algorithms for the Incremental Knapsack Problem via Disjunctive Programming
Venue: arXiv cs.DS 2013
Year: 2013

In the incremental knapsack problem ($\IK$), we are given a knapsack whose capacity grows weakly as a function of time. There is a time horizon of $T$ periods and the capacity of the knapsack is $B_t$ in period $t$ for $t = 1, \ldots, T$. We are also given a set $S$ of $N$ items to be placed in the knapsack. Item $i$ has a value of $v_i$ and a weight of $w_i$ that is independent of the time period. At any time period $t$, the sum of the weights of the items in the knapsack cannot exceed the knapsack capacity $B_t$. Moreover, once an item is placed in the knapsack, it cannot be removed from the knapsack at a later time period. We seek to maximize the sum of (discounted) knapsack values over time subject to the capacity constraints. We first give a constant factor approximation algorithm for $\IK$, under mild restrictions on the growth rate of $B_t$ (the constant factor depends on the growth rate). We then give a PTAS for $\IIK$, the special case of $\IK$ with no discounting, when $T = O(\sqrt{\log N})$.
A Trust Model Based Analysis of Social Networks
Venue: arXiv cs.SI 2013
Year: 2013

In this paper, we analyse the sustainability of social networks using STrust, our social trust model. The novelty of the model is that it introduces the concept of engagement trust and combines it with the popularity trust to derive the social trust of the community as well as of individual members in the community. This enables the recommender system to use these different types of trust to recommend different things to the community, and identify (and recommend) different roles. For example, it recommends mentors using the engagement trust and leaders using the popularity trust. We then show the utility of the model by analysing data from two types of social networks. We also study the sustainability of a community through our social trust model. We observe that a 5% drop in highly trusted members causes more than a 50% drop in social capital that, in turn, raises the question of sustainability of the community. We report our analysis and its results.
Every-user delay guarantee for wireless multiple access systems
Venue: arXiv cs.IT 2013
Year: 2013

The quality of service (QoS) requirements are usually different from user to user in a multiaccess system, and it is necessary to take the different requirements into account when allocating the shared resources of the system. In this paper, we consider one QoS criterion--delay in a multiaccess system, and we combine information theory and queueing theory in an attempt to analyze whether a multiaccess system can meet the different delay requirements of users. For users with the same transmission power, we prove that only $N$ inequalities are necessary for the checking, and for users with different transmission powers, we provide a polynomial-time algorithm for such a decision. In cases where the system cannot satisfy the delay requirements of all users, we prove that as long as the sum power is larger than a threshold, there is always an approach to adjust the transmission power of each user to make the system delay feasible if power reallocation is available.
Zero-Delay and Causal Secure Source Coding
Venue: arXiv cs.IT 2013
Year: 2013

We investigate the combination between causal/zero-delay source coding and information-theoretic secrecy. Two source coding models with secrecy constraints are considered. We start by considering zero-delay perfectly secret lossless transmission of a memoryless source. We derive bounds on the key rate and coding rate needed for perfect zero-delay secrecy. In this setting, we consider two models which differ by the ability of the eavesdropper to parse the bit-stream passing from the encoder to the legitimate decoder into separate messages. We also consider causal source coding with a fidelity criterion and side information at the decoder and the eavesdropper. Unlike the zero-delay setting where variable-length coding is traditionally used but might leak information on the source through the length of the codewords, in this setting, since delay is allowed, block coding is possible. We show that in this setting, separation of encryption and causal source coding is optimal.
Senescent Ground Tree Rewrite Systems
Venue: arXiv cs.FL 2013
Year: 2013

Ground Tree Rewrite Systems with State are known to have an undecidable control state reachability problem. Taking inspiration from the recent introduction of scope-bounded multi-stack pushdown systems, we define Senescent Ground Tree Rewrite Systems. These are a restriction of ground tree rewrite systems with state such that nodes of the tree may no longer be rewritten after having witnessed an a priori fixed number of control state changes. As well as generalising scope-bounded multi-stack pushdown systems, we show --- via reductions to and from reset Petri-nets --- that these systems have an Ackermann-complete control state reachability problem. However, reachability of a regular set of trees remains undecidable.
Simultaneous Greedy Analysis Pursuit for Compressive Sensing of Multi-Channel ECG Signals
Venue: arXiv cs.IT 2013
Year: 2013

This paper addresses compressive sensing for multi-channel ECG. Compared to the traditional sparse signal recovery approach which decomposes the signal into the product of a dictionary and a sparse vector, the recently developed cosparse approach exploits sparsity of the product of an analysis matrix and the original signal. We apply the cosparse Greedy Analysis Pursuit (GAP) algorithm for compressive sensing of ECG signals. Moreover, to reduce processing time, classical signal-channel GAP is generalized to the multi-channel GAP algorithm, which simultaneously reconstructs multiple signals with similar support. Numerical experiments show that the proposed method outperforms the classical sparse multi-channel greedy algorithms in terms of accuracy and the single-channel cosparse approach in terms of processing speed.
Visual Representation of 3D Language Constructs Specified by Generic Depictions
Venue: arXiv cs.PL 2013
Year: 2013

Several modeling domains make use of three-dimensional representations, e.g., the "ball-and-stick" models of molecules. Our generator framework DEViL3D supports the design and implementation of visual 3D languages for such modeling purposes. The front-end of a language implementation generated by DEViL3D is a dedicated 3D graphical structure editor, which is used to construct programs in that domain. DEViL3D supports the language designer to describe the visual appearance of the constructs of the particular language in terms of generic 3D depictions. Their parameters specify where substructures are embedded, and how the graphic adapts to space requirements of nested constructs. The 3D editor used for such specifications is generated by DEViL3D, too. In this paper, we briefly introduce the research field of 3D visual languages and report about our generator framework and the role that generic depictions play in the specification process for 3D languages. Our results show that our approach is suitable for a wide range of 3D languages. We emphasize this suitability by presenting requirements on the visual appearance for different languages.
Resilient Control under Denial-of-Service
Venue: arXiv cs.SY 2013
Year: 2013

We investigate resilient control strategies for linear systems under Denial-of-Service (DoS) attacks. By DoS attacks we mean interruptions of communication on measurement (sensor-to-controller) and/or control (controller-to-actuator) channels carried out by an intelligent adversary. We characterize the duration of these interruptions under which stability of the closed-loop system is preserved. The resilient nature of the control descends from its ability to adapt the sampling rate to the occurrence of the DoS.
Dealing with the Fuzziness of Human Reasoning
Venue: arXiv cs.AI 2013
Year: 2013

Reasoning, the most important human brain operation, is charactrized by a degree fuzziness. In the present paper we construct a fuzzy model for the reasoning process giving through the calculation of the possibilities of all possible individuals' profiles a quantitative/qualitative view of their behaviour during the above process and we use the centroid defuzzification technique for measuring the reasoning skills. We also present a number of classroom experiments illustrating our results in practice.
Coverage by Pairwise Base Station Cooperation under Adaptive Geometric Policies
Venue: arXiv cs.IT 2013
Year: 2013

We study a cooperation model where the positions of base stations follow a Poisson point process distribution and where Voronoi cells define the planar areas associated with them. For the service of each user, either one or two base stations are involved. If two, these cooperate by exchange of user data and reduced channel information (channel phase, second neighbour interference) with conferencing over some backhaul link. The total user transmission power is split between them and a common message is encoded, which is coherently transmitted by the stations. The decision for a user to choose service with or without cooperation is directed by a family of geometric policies. The suggested policies further control the shape of coverage contours in favor of cell-edge areas. Analytic expressions based on stochastic geometry are derived for the coverage probability in the network. Their numerical evaluation shows benefits from cooperation, which are enhanced when Dirty Paper Coding is applied to eliminate the second neighbour interference.
Analysis of Wireless Power Transmission
Venue: arXiv cs.NI 2013
Year: 2013

The advent of various wireless technologies have revolutionized the communication infrastructure and consequently changed the entire world into a global village. Use of wireless technology has also been made for transmission of electric power wirelessly. It increases the portability of power systems and integrates the communication technologies and electric power to the same platform. This paper presents a comprehensive review and detailed analysis of various techniques used for wireless power transmission. Feasibility, implementations, operations, results and comparison among different methods have also been covered in order to identify the favorable and economical method for low power and small distance applications.
Learning Non-Linear Feature Maps
Venue: arXiv cs.LG 2013
Year: 2013

Feature selection plays a pivotal role in learning, particularly in areas were parsimonious features can provide insight into the underlying process, such as biology. Recent approaches for non-linear feature selection employing greedy optimisation of Centred Kernel Target Alignment(KTA), while exhibiting strong results in terms of generalisation accuracy and sparsity, can become computationally prohibitive for high-dimensional datasets. We propose randSel, a randomised feature selection algorithm, with attractive scaling properties. Our theoretical analysis of randSel provides strong probabilistic guarantees for the correct identification of relevant features. Experimental results on real and artificial data, show that the method successfully identifies effective features, performing better than a number of competitive approaches.
High Performance Risk Aggregation: Addressing the Data Processing Challenge the Hadoop MapReduce Way
Venue: arXiv cs.DC 2013
Year: 2013

Monte Carlo simulations employed for the analysis of portfolios of catastrophic risk process large volumes of data. Often times these simulations are not performed in real-time scenarios as they are slow and consume large data. Such simulations can benefit from a framework that exploits parallelism for addressing the computational challenge and facilitates a distributed file system for addressing the data challenge. To this end, the Apache Hadoop framework is chosen for the simulation reported in this paper so that the computational challenge can be tackled using the MapReduce model and the data challenge can be addressed using the Hadoop Distributed File System. A parallel algorithm for the analysis of aggregate risk is proposed and implemented using the MapReduce model in this paper. An evaluation of the performance of the algorithm indicates that the Hadoop MapReduce model offers a framework for processing large data in aggregate risk analysis. A simulation of aggregate risk employing 100,000 trials with 1000 catastrophic events per trial on a typical exposure set and contract structure is performed on multiple worker nodes in less than 6 minutes. The result indicates the scope and feasibility of MapReduce for tackling the computational and data challenge in the analysis of aggregate risk for real-time use.
Unscented Orientation Estimation Based on the Bingham Distribution
Venue: arXiv cs.SY 2013
Year: 2013

Orientation estimation for 3D objects is a common problem that is usually tackled with traditional nonlinear filtering techniques such as the extended Kalman filter (EKF) or the unscented Kalman filter (UKF). Most of these techniques assume Gaussian distributions to account for system noise and uncertain measurements. This distributional assumption does not consider the periodic nature of pose and orientation uncertainty. We propose a filter that considers the periodicity of the orientation estimation problem in its distributional assumption. This is achieved by making use of the Bingham distribution, which is defined on the hypersphere and thus inherently more suitable to periodic problems. Furthermore, handling of non-trivial system functions is done using deterministic sampling in an efficient way. A deterministic sampling scheme reminiscent of the UKF is proposed for the nonlinear manifold of orientations. It is the first deterministic sampling scheme that truly reflects the nonlinear manifold of the orientation.
Automatic Ranking of MT Outputs using Approximations
Venue: arXiv cs.CL 2013
Year: 2013

Since long, research on machine translation has been ongoing. Still, we do not get good translations from MT engines so developed. Manual ranking of these outputs tends to be very time consuming and expensive. Identifying which one is better or worse than the others is a very taxing task. In this paper, we show an approach which can provide automatic ranks to MT outputs (translations) taken from different MT Engines and which is based on N-gram approximations. We provide a solution where no human intervention is required for ranking systems. Further we also show the evaluations of our results which show equivalent results as that of human ranking.
Fast Training of Effective Multi-class Boosting Using Coordinate Descent Optimization
Venue: arXiv cs.CV 2013
Year: 2013

Wepresentanovelcolumngenerationbasedboostingmethod for multi-class classification. Our multi-class boosting is formulated in a single optimization problem as in Shen and Hao (2011). Different from most existing multi-class boosting methods, which use the same set of weak learners for all the classes, we train class specified weak learners (i.e., each class has a different set of weak learners). We show that using separate weak learner sets for each class leads to fast convergence, without introducing additional computational overhead in the training procedure. To further make the training more efficient and scalable, we also propose a fast co- ordinate descent method for solving the optimization problem at each boosting iteration. The proposed coordinate descent method is conceptually simple and easy to implement in that it is a closed-form solution for each coordinate update. Experimental results on a variety of datasets show that, compared to a range of existing multi-class boosting meth- ods, the proposed method has much faster convergence rate and better generalization performance in most cases. We also empirically show that the proposed fast coordinate descent algorithm needs less training time than the MultiBoost algorithm in Shen and Hao (2011).
Comparison analysis in Multicast Authentication based on Batch Signature (MABS) in Network Security
Venue: arXiv cs.CR 2013
Year: 2013

Conventional block-based multicast authentication schemes overlook the heterogeneity of receivers by letting the sender choose the block size, divide a multicast stream into blocks, associate each block with a signature, and spread the effect of the signature across all the packets in the block through hash graphs or coding algorithms. The correlation among packets makes them vulnerable to packet loss, which is inherent in the Internet and wireless networks. Moreover, the lack of Denial of Service (DoS) resilience renders most of them vulnerable to packet injection in hostile environments. In this paper, we propose a novel multicast authentication protocol, namely MABS, including two schemes. The basic scheme (MABS-B) eliminates the correlation among packets and thus provides the perfect resilience to packet loss, and it is also efficient in terms of latency, computation, and communication overhead due to an efficient cryptographic primitive called batch signature, which supports the authentication of any number of packets simultaneously.so we discuss their comparisons and performance evaluation of Packet Loss, Comparisons over Lossy Channels, Comparisons of Signature Schemes, computationational overheads etc.
Modeling and Simulation of the EV Charging in a Residential Distribution Power Grid
Venue: arXiv cs.SY 2013
Year: 2013

There are numerous advantages of using Electric Vehicles (EVs) as an alternative method of transportation. However, an increase in EV usage in the existing residential distribution grid poses problems such as overloading the existing infrastructure. In this paper, we have modeled and simulated a residential distribution grid in GridLAB-D (an open-source software tool used to model, simulate, and analyze power distribution systems) to illustrate the problems associated with a higher EV market penetration rates in the residential domain. Power grid upgrades or control algorithms at the transformer level are required to overcome issues such as transformer overloading. We demonstrate the method of coordinating EV charging in a residential distribution grid so as to overcome the overloading problem without any upgrades in the distribution grid.
Q-learning optimization in a multi-agents system for image segmentation
Venue: arXiv cs.AI 2013
Year: 2013

To know which operators to apply and in which order, as well as attributing good values to their parameters is a challenge for users of computer vision. This paper proposes a solution to this problem as a multi-agent system modeled according to the Vowel approach and using the Q-learning algorithm to optimize its choice. An implementation is given to test and validate this method.
Rethinking State-Machine Replication for Parallelism
Venue: arXiv cs.DC 2013
Year: 2013

State-machine replication, a fundamental approach to designing fault-tolerant services, requires commands to be executed in the same order by all replicas. Moreover, command execution must be deterministic: each replica must produce the same output upon executing the same sequence of commands. These requirements usually result in single-threaded replicas, which hinders service performance. This paper introduces Parallel State-Machine Replication (P-SMR), a new approach to parallelism in state-machine replication. P-SMR scales better than previous proposals since no component plays a centralizing role in the execution of independent commands---those that can be executed concurrently, as defined by the service. The paper introduces P-SMR, describes a "commodified architecture" to implement it, and compares its performance to other proposals using a key-value store and a networked file system.
A Model Approach to Build Basic Ontology
Venue: arXiv cs.IR 2013
Year: 2013

As todays world grows with the technology on the other hand it seems to be small with the World Wide Web. With the use of Internet more and more information can be search from the web. When Users fires a query they want relevancy in obtained results. In general, search engines perform the ranking of web pages in an offline mode, which is after the web pages have been retrieved and stored in the database. But most of the time this method does not provide relevant results as most of the search engines were using some ranking algorithms like page Rank, HITS, SALSA and Hilltop. Where these algorithms does not always provides the results based on the semantic web. So a concept of Ontology is been introduced in search engines to get more meaningful and relevant results with respect to the users query.Ontologies are used to capture knowledge about some domain of interest. Ontology describes the concepts in the domain and also the relationships that hold between those concepts. Different ontology languages provide different facilities. The most recent development in standard ontology languages is OWL (Ontology Web Language) from the World Wide Web Consortium. OWL makes it possible to describe concept to its full extent and enables the search engines to provide accurate results to the user.
Toward bio-inspired information processing with networks of nano-scale switching elements
Venue: arXiv cs.ET 2013
Year: 2013

Unconventional computing explores multi-scale platforms connecting molecular-scale devices into networks for the development of scalable neuromorphic architectures, often based on new materials and components with new functionalities. We review some work investigating the functionalities of locally connected networks of different types of switching elements as computational substrates. In particular, we discuss reservoir computing with networks of nonlinear nanoscale components. In usual neuromorphic paradigms, the network synaptic weights are adjusted as a result of a training/learning process. In reservoir computing, the non-linear network acts as a dynamical system mixing and spreading the input signals over a large state space, and only a readout layer is trained. We illustrate the most important concepts with a few examples, featuring memristor networks with time-dependent and history dependent resistances.
Service based hight-speed railway base station arrangement
Venue: arXiv cs.IT 2013
Year: 2013

To provide stable and high data rate wireless access for passengers in the train, it is necessary to properly deploy base stations along the railway. We consider this issue from the perspective of service, which is defined as the integral of the time-varying instantaneous channel capacity. With large-scale fading assumption, it will be shown that the total service of each base station is inversely proportional to the velocity of the train. Besides, we find that if the ratio of the service provided by a base station in its service region to its total service is given, the base station interval (i.e. the distance between two adjacent base stations) is a constant regardless of the velocity of the train. On the other hand, if a certain amount of service is required, the interval will increase with the velocity of the train. The above results apply not only to simple curve rails, like line rail and arc rail, but also to any irregular curve rail, provided that the train is travelling at a constant velocity. Furthermore, the new developed results are applied to analyze the on-off transmission strategy of base stations.