OpenRaiser/Intern-Atlas huggingface dataset:
Threshold Policy for Route Discovery Initiation in Mobile Ad hoc Networks
Venue: arXiv cs.NI 2010
Year: 2010

Achieving optimal transmission throughput in data networks in a multi-hop wireless networks is fundamental but hard problem. The situation is aggravated when nodes are mobile. Further, multi-rate system make the analysis of throughput more complicated. In mobile scenario, link may break or be created as nodes are moving within communication range. `Route Discovery' which is to find the optimal route and transmission schedule is an important issue. Route discovery entails some cost; so one would not like to initiate discovery too often. On the other hand, not discovering reasonably often entails the risk of being stuck with a suboptimal route and/or schedule, which hurts end-to-end throughput. The implementation of the routing decision problem in one dimensional mobile ad hoc network as Markov decision process problem is already is discussed in the paper [1]. A heuristic based on threshold policy is discussed in the same paper without giving a way to find the threshold. In this paper, we suggested a rule for setting the threshold, given the parameters of the system. We also point out that our results remain valid in a slightly different mobility model; this model is a first step towards an `open' network in which existing relay nodes can leave and/or new relay nodes can join the network.
Improving the Quality of Non-Holonomic Motion by Hybridizing C-PRM Paths
Venue: arXiv cs.RO 2010
Year: 2010

Sampling-based motion planners are an effective means for generating collision-free motion paths. However, the quality of these motion paths, with respect to different quality measures such as path length, clearance, smoothness or energy, is often notoriously low. This problem is accentuated in the case of non-holonomic sampling-based motion planning, in which the space of feasible motion trajectories is restricted. In this study, we combine the C-PRM algorithm by Song and Amato with our recently introduced path-hybridization approach, for creating high quality non-holonomic motion paths, with combinations of several different quality measures such as path length, smoothness or clearance, as well as the number of reverse car motions. Our implementation includes a variety of code optimizations that result in nearly real-time performance, and which we believe can be extended with further optimizations to a real-time tool for the planning of high-quality car-like motion.
An Efficient Implementation of the Robust Tabu Search Heuristic for Sparse Quadratic Assignment Problems
Venue: arXiv cs.DS 2010
Year: 2010

We propose and develop an efficient implementation of the robust tabu search heuristic for sparse quadratic assignment problems. The traditional implementation of the heuristic applicable to all quadratic assignment problems is of O(N^2) complexity per iteration for problems of size N. Using multiple priority queues to determine the next best move instead of scanning all possible moves, and using adjacency lists to minimize the operations needed to determine the cost of moves, we reduce the asymptotic complexity per iteration to O(N log N ). For practical sized problems, the complexity is O(N).
Text Classification using Artificial Intelligence
Venue: arXiv cs.IR 2010
Year: 2010

Text classification is the process of classifying documents into predefined categories based on their content. It is the automated assignment of natural language texts to predefined categories. Text classification is the primary requirement of text retrieval systems, which retrieve texts in response to a user query, and text understanding systems, which transform text in some way such as producing summaries, answering questions or extracting data. Existing supervised learning algorithms for classifying text need sufficient documents to learn accurately. This paper presents a new algorithm for text classification using artificial intelligence technique that requires fewer documents for training. Instead of using words, word relation i.e. association rules from these words is used to derive feature set from pre-classified text documents. The concept of naïve Bayes classifier is then used on derived features and finally only a single concept of genetic algorithm has been added for final classification. A system based on the proposed algorithm has been implemented and tested. The experimental results show that the proposed system works as a successful text classifier.
Fastest Distributed Consensus on Petal Networks
Venue: arXiv cs.IT 2010
Year: 2010

Providing an analytical solution for the problem of finding Fastest Distributed Consensus (FDC) is one of the challenging problems in the field of sensor networks. Here in this work we present analytical solution for the problem of fastest distributed consensus averaging algorithm by means of stratification and semi-definite programming, for two particular types of Petal networks, namely symmetric and Complete Cored Symmetric (CCS) Petal networks. Our method in this paper is based on convexity of fastest distributed consensus averaging problem, and inductive comparing of the characteristic polynomials initiated by slackness conditions in order to find the optimal weights. Also certain types of leaves are introduced along with their optimal weights which are not achievable by the method used in this work if these leaves are considered individually.
Bulk File Download Throughput in a Single Station WLAN with Nonzero Propagation Delay
Venue: arXiv cs.NI 2010
Year: 2010

We analyze TCP-controlled bulk file transfers in a single station (STA) WLAN with nonzero propagation delay between the file server and the WLAN. Our approach is to model the flow of packets as a closed queueing network (BCMP network) with 3 service centres, one each for the Access Point (AP) and the STA, and the third for the propagation delay. The service rates of the first two are obtained by analyzing the WLAN MAC. Simulations show a very close match with the theory.
Approximability of the Multiple Stack TSP
Venue: arXiv cs.CC 2010
Year: 2010

STSP seeks a pair of pickup and delivery tours in two distinct networks, where the two tours are related by LIFO contraints. We address here the problem approximability. We notably establish that asymmetric MaxSTSP and MinSTSP12 are APX, and propose a heuristic that yields to a 1/2, 3/4 and 3/2 standard approximation for respectively Max2STSP, Max2STSP12 and Min2STSP12.
Buyback Problem - Approximate matroid intersection with cancellation costs
Venue: arXiv cs.GT 2010
Year: 2010

In the buyback problem, an algorithm observes a sequence of bids and must decide whether to accept each bid at the moment it arrives, subject to some constraints on the set of accepted bids. Decisions to reject bids are irrevocable, whereas decisions to accept bids may be canceled at a cost that is a fixed fraction of the bid value. Previous to our work, deterministic and randomized algorithms were known when the constraint is a matroid constraint. We extend this and give a deterministic algorithm for the case when the constraint is an intersection of $k$ matroid constraints. We further prove a matching lower bound on the competitive ratio for this problem and extend our results to arbitrary downward closed set systems. This problem has applications to banner advertisement, semi-streaming, routing, load balancing and other problems where preemption or cancellation of previous allocations is allowed.
The Most Advantageous Bangla Keyboard Layout Using Data Mining Technique
Venue: arXiv cs.AI 2010
Year: 2010

Bangla alphabet has a large number of letters, for this it is complicated to type faster using Bangla keyboard. The proposed keyboard will maximize the speed of operator as they can type with both hands parallel. Association rule of data mining to distribute the Bangla characters in the keyboard is used here. The frequencies of data consisting of monograph, digraph and trigraph are analyzed, which are derived from data wire-house, and then used association rule of data mining to distribute the Bangla characters in the layout. Experimental results on several data show the effectiveness of the proposed approach with better performance. This paper presents an optimal Bangla Keyboard Layout, which distributes the load equally on both hands so that maximizing the ease and minimizing the effort.
A Simple Abstraction for Data Modeling
Venue: arXiv cs.DB 2010
Year: 2010

The problems that scientists face in creating well designed databases intersect with the concerns of data curation. Entity-relationship modeling and its variants have been the basis of most relational data modeling for decades. However, these abstractions and the relational model itself are intricate and have proved not to be very accessible among scientists with limited resources for data management. This paper explores one aspect of relational data models, the meaning of foreign key relationships. We observe that a foreign key produces a table relationship that generally references either an entity or repeating attributes. This paper proposes constructing foreign keys based on these two cases, and suggests that the method promotes intuitive data modeling and normalization.
Establishing a Multi-Thesauri-Scenario based on SKOS and Cross-Concordances
Venue: arXiv cs.DL 2010
Year: 2010

This case study proposes a scenario with three topic-related thesauri, which have been connected with bilateral cross-concordances as part of a major terminology mapping initiative in the project KoMoHe (Mayr & Petras, 2008). The thesauri have already been or will be converted to SKOS and in order to not omit the relevant crosswalks, the mapping properties of SKOS will be used for modeling them adequately.
A Scenario-Based Mobile Application for Robot-Assisted Smart Digital Homes
Venue: arXiv cs.RO 2010
Year: 2010

Smart homes are becoming more popular, as every day a new home appliance can be digitally controlled. Smart Digital Homes are using a server to make interaction with all the possible devices in one place, on a computer or webpage. In this paper we designed and implemented a mobile application using Windows Mobile platform that can connect to the controlling server of a Smart Home and grants the access to the Smart Home devices and robots everywhere possible. UML diagrams are presented to illustrate the application design process. Robots are also considered as devices that are able to interact to other object and devices. Scenarios are defined as a set of sequential actions to help manage different tasks all in one place. The mobile application can connect to the server using GPRS mobile internet and Short Message System (SMS). Interactive home map is also designed for easier status-checking and interacting with the devices using the mobile phones.
Social Attention and the Provider's Dilemma
Venue: arXiv cs.CY 2010
Year: 2010

While attracting attention is one of the prime goals of content providers, the conversion of that attention into revenue is by no means obvious. Given that most users expect to consume web content for free, a provider with an established audience faces a dilemma. Since the introduction of advertisements or subscription fees will be construed by users as an inconvenience which may lead them to stop using the site, what should the provider do in order to maximize revenues? We address this question through the lens of adaptation theory, which states that even though a change affects a person's utility initially, as time goes on people tend to adapt and become less aware of past changes. We establish that if the likelihood of continuing to attend to the provider after an increase in inconvenience is log-concave in the magnitude of the increase, then the provider faces a tradeoff between achieving a higher revenue per user sooner and maximizing the number of users in the long term. On the other hand, if the likelihood of continuing to attend to the provider after an increase in inconvenience is log-convex, then it is always optimal for the provider to perform the increase in one step.
The thermodynamic temperature of a rhythmic spiking network
Venue: arXiv cs.NE 2010
Year: 2010

Artificial neural networks built from two-state neurons are powerful computational substrates, whose computational ability is well understood by analogy with statistical mechanics. In this work, we introduce similar analogies in the context of spiking neurons in a fixed time window, where excitatory and inhibitory inputs drawn from a Poisson distribution play the role of temperature. For single neurons with a "bandgap" between their inputs and the spike threshold, this temperature allows for stochastic spiking. By imposing a global inhibitory rhythm over the fixed time windows, we connect neurons into a network that exhibits synchronous, clock-like updating akin to neural networks. We implement a single-layer Boltzmann machine without learning to demonstrate our model.
Diversity and Polarization of Research Performance: Evidence from Hungary
Venue: arXiv cs.SI 2010
Year: 2010

Measuring the intellectual diversity encoded in publication records as a proxy to the degree of interdisciplinarity has recently received considerable attention in the science mapping community. The present paper draws upon the use of the Stirling index as a diversity measure applied to a network model (customized science map) of research profiles, proposed by several authors. A modified version of the index is used and compared with the previous versions on a sample data set in order to rank top Hungarian research organizations (HROs) according to their research performance diversity. Results, unexpected in several respects, show that the modified index is a candidate for measuring the degree of polarization of a research profile. The study also points towards a possible typology of publication portfolios that instantiate different types of diversity.
Clandestine Simulations in Cellular Automata
Venue: arXiv cs.DM 2010
Year: 2010

This paper studies two kinds of simulation between cellular automata: simulations based on factor and simulations based on sub-automaton. We show that these two kinds of simulation behave in two opposite ways with respect to the complexity of attractors and factor subshifts. On the one hand, the factor simulation preserves the complexity of limits sets or column factors (the simulator CA must have a higher complexity than the simulated CA). On the other hand, we show that any CA is the sub-automaton of some CA with a simple limit set (NL-recognizable) and the sub-automaton of some CA with a simple column factor (finite type). As a corollary, we get intrinsically universal CA with simple limit sets or simple column factors. Hence we are able to 'hide' the simulation power of any CA under simple dynamical indicators.
Changing User Attitudes to Reduce Spreadsheet Risk
Venue: arXiv cs.HC 2010
Year: 2010

A business case study on how three simple guidelines: 1. Make it easy to check (and maintain) 2. Make it safe to use 3. Keep business logic out of code changed user attitudes and improved spreadsheet quality in a financial services organisation.
Secret Key Agreement from Vector Gaussian Sources by Rate Limited Public Communication
Venue: arXiv cs.IT 2010
Year: 2010

We investigate the secret key agreement from correlated vector Gaussian sources in which the legitimate parties can use the public communication with limited rate. For the class of protocols with the one-way public communication, we show that the optimal trade-off between the rate of key generation and the rate of the public communication is characterized as an optimization problem of a Gaussian random variable. The characterization is derived by using the enhancement technique introduced by Weingarten et.al. for MIMO Gaussian broadcast channel.
List Factoring and Relative Worst Order Analysis
Venue: arXiv cs.DS 2010
Year: 2010

Relative worst order analysis is a supplement or alternative to competitive analysis which has been shown to give results more in accordance with observed behavior of online algorithms for a range of different online problems. The contribution of this paper is twofold. First, it adds the static list accessing problem to the collection of online problems where relative worst order analysis gives better results. Second, and maybe more interesting, it adds the non-trivial supplementary proof technique of list factoring to the theoretical toolbox for relative worst order analysis.
A Low Overhead Reachability Guaranteed Dynamic Route Discovery Mechanism for Dense MANETs
Venue: arXiv cs.NI 2010
Year: 2010

A crucial issue for a mobile ad hoc network is the handling of a large number of nodes. As more nodes join the mobile ad hoc network, contention and congestion are more likely. The on demand routing protocols which broadcasts control packets to discover routes to the destination nodes, generate a high number of broadcast packets in a larger networks causing contention and collision. We propose an efficient route discovery protocol, which reduces the number of broadcast packet, using controlled flooding technique. The simulation results show that the proposed probabilistic flooding decreases the number of control packets floating in the network during route discovery phase, without lowering the success ratio of path discoveries. Furthermore, the proposed method adapts to the normal network conditions. The results show that up to 70% of control packet traffic is saved in route discovery phase when the network is denser.
A Fair and Efficient Packet Scheduling Scheme for IEEE 802.16 Broadband Wireless Access Systems
Venue: arXiv cs.NI 2010
Year: 2010

This paper proposes a fair and efficient QoS scheduling scheme for IEEE 802.16 BWA systems that satisfies both throughput and delay guarantee to various real and non-real time applications. The proposed QoS scheduling scheme is compared with an existing QoS scheduling scheme proposed in literature in recent past. Simulation results show that the proposed scheduling scheme can provide a tight QoS guarantee in terms of delay, delay violation rate and throughput for all types of traffic as defined in the WiMAX standard, thereby maintaining the fairness and helps to eliminate starvation of lower priority class services. Bandwidth utilization of the system and fairness index of the resources are also encountered to validate the QoS provided by our proposed scheduling scheme.
The Baire partial quasi-metric space: A mathematical tool for asymptotic complexity analysis in Computer Science
Venue: arXiv cs.CC 2010
Year: 2010

In 1994, S.G. Matthews introduced the notion of partial metric space in order to obtain a suitable mathematical tool for program verification [Ann. New York Acad. Sci. 728 (1994), 183-197]. He gave an application of this new structure to parallel computing by means of a partial metric version of the celebrated Banach fixed point theorem [Theoret. Comput. Sci. 151 (1995), 195-205]. Later on, M.P. Schellekens introduced the theory of complexity (quasi-metric) spaces as a part of the development of a topological foundation for the asymptotic complexity analysis of programs and algorithms [Elec- tronic Notes in Theoret. Comput. Sci. 1 (1995), 211-232]. The applicability of this theory to the asymptotic complexity analysis of Divide and Conquer algorithms was also illustrated by Schellekens. In particular, he gave a new proof, based on the use of the aforenamed Banach fixed point theorem, of the well-known fact that Mergesort al- gorithm has optimal asymptotic average running time of computing. In this paper, motivated by the utility of partial metrics in Computer Science, we discuss whether the Matthews fixed point theorem is a suitable tool to analyze the asymptotic complexity of algorithms in the spirit of Schellekens. Specifically, we show that a slight modification of the well-known Baire partial metric on the set of all words over an alphabet constitutes an appropriate tool to carry out the asymptotic complexity analysis of algorithms via fixed point methods without the need for assuming the convergence condition inherent to the defini- tion of the complexity space in the Shellekens framework. Finally, in order to illustrate and to validate the developed theory we apply our results to analyze the asymptotic complexity of Quicksort, Mergesort and Largesort algorithms.
Cut Elimination for a Logic with Induction and Co-induction
Venue: arXiv cs.LO 2010
Year: 2010

Proof search has been used to specify a wide range of computation systems. In order to build a framework for reasoning about such specifications, we make use of a sequent calculus involving induction and co-induction. These proof principles are based on a proof theoretic (rather than set-theoretic) notion of definition. Definitions are akin to logic programs, where the left and right rules for defined atoms allow one to view theories as "closed" or defining fixed points. The use of definitions and free equality makes it possible to reason intentionally about syntax. We add in a consistent way rules for pre and post fixed points, thus allowing the user to reason inductively and co-inductively about properties of computational system making full use of higher-order abstract syntax. Consistency is guaranteed via cut-elimination, where we give the first, to our knowledge, cut-elimination procedure in the presence of general inductive and co-inductive definitions.
Secure Relay Beamforming over Cognitive Radio Channels
Venue: arXiv cs.IT 2010
Year: 2010

In this paper, a cognitive relay channel is considered, and amplify-and-forward (AF) relay beamforming designs in the presence of an eavesdropper and a primary user are studied. Our objective is to optimize the performance of the cognitive relay beamforming system while limiting the interference in the direction of the primary receiver and keeping the transmitted signal secret from the eavesdropper. We show that under both total and individual power constraints, the problem becomes a quasiconvex optimization problem which can be solved by interior point methods. We also propose two sub-optimal null space beamforming schemes which are obtained in a more computationally efficient way.
An Embarrassingly Simple Speed-Up of Belief Propagation with Robust Potentials
Venue: arXiv cs.CV 2010
Year: 2010

We present an exact method of greatly speeding up belief propagation (BP) for a wide variety of potential functions in pairwise MRFs and other graphical models. Specifically, our technique applies whenever the pairwise potentials have been {\em truncated} to a constant value for most pairs of states, as is commonly done in MRF models with robust potentials (such as stereo) that impose an upper bound on the penalty assigned to discontinuities; for each of the $M$ possible states in one node, only a smaller number $m$ of compatible states in a neighboring node are assigned milder penalties. The computational complexity of our method is $O(mM)$, compared with $O(M^2)$ for standard BP, and we emphasize that the method is {\em exact}, in contrast with related techniques such as pruning; moreover, the method is very simple and easy to implement. Unlike some previous work on speeding up BP, our method applies both to sum-product and max-product BP, which makes it useful in any applications where marginal probabilities are required, such as maximum likelihood estimation. We demonstrate the technique on a stereo MRF example, confirming that the technique speeds up BP without altering the solution.