OpenRaiser/Intern-Atlas huggingface dataset:
Self-organization of Nodes using Bio-Inspired Techniques for Achieving Small World Properties
Venue: arXiv cs.NI 2011
Year: 2011

In an autonomous wireless sensor network, self-organization of the nodes is essential to achieve network wide characteristics. We believe that connectivity in wireless autonomous networks can be increased and overall average path length can be reduced by using beamforming and bio-inspired algorithms. Recent works on the use of beamforming in wireless networks mostly assume the knowledge of the network in aggregation to either heterogeneous or hybrid deployment. We propose that without the global knowledge or the introduction of any special feature, the average path length can be reduced with the help of inspirations from the nature and simple interactions between neighboring nodes. Our algorithm also reduces the number of disconnected components within the network. Our results show that reduction in the average path length and the number of disconnected components can be achieved using very simple local rules and without the full network knowledge.
The Control Theory of Motion-Based Communication: Problems in Teaching Robots to Dance
Venue: arXiv cs.SY 2011
Year: 2011

The paper describes results on two components of a research program focused on motion-based communication mediated by the dynamics of a control system. Specifically we are interested in how mobile agents engaged in a shared activity such as dance can use motion as a medium for transmitting certain types of messages. The first part of the paper adopts the terminology of motion description languages and deconstructs an elementary form of the well-known popular dance, Salsa, in terms of four motion primitives (dance steps). Several notions of dance complexity are introduced. We describe an experiment in which ten performances by an actual pair of dancers are evaluated by judges and then compared in terms of proposed complexity metrics. An energy metric is also defined. Values of this metric are obtained by summing the lengths of motion segments executed by wheeled robots replicating the movements of the human dancers in each of the ten dance performances. Of all the metrics that are considered in this experiment, energy is the most closely correlated with the human judges' assessments of performance quality. The second part of the paper poses a general class of dual objective motion control problems in which a primary objective (artistic execution of a dance step or efficient movement toward a specified terminal state) is combined with a communication objective. Solutions of varying degrees of explicitness can be given in several classes of problems of communicating through the dynamics of finite dimensional linear control systems. In this setting it is shown that the cost of adding a communication component to motions that steer a system between prescribed pairs of states is independent of those states. At the same time, the optimal encoding problem itself is shown to be a problem of packing geometric objects, and it remains open.
Greedy Algorithms for Multi-Queue Buffer Management with Class Segregation
Venue: arXiv cs.DM 2011
Year: 2011

In this paper, we focus on a multi-queue buffer management in which packets of different values are segregated in different queues. Our model consists of m packets values and m queues. Recently, Al-Bawani and Souza (arXiv:1103.6049v2 [cs.DS] 30 Mar 2011) presented an online multi-queue buffer management algorithm Greedy and showed that it is 2-competitive for the general m-valued case, i.e., m packet values are 0 < v_{1} < v_{2} < ... < v_{m}, and (1+v_{1}/v_{2})-competitive for the two-valued case, i.e., two packet values are 0 < v_{1} < v_{2}. For the general m-valued case, let c_i = (v_{i} + \sum_{j=1}^{i-1} 2^{j-1} v_{i-j})/(v_{i+1} + \sum_{j=1}^{i-1}2^{j-1}v_{i-j}) for 1 \leq i \leq m-1, and let c_{m}^{*} = \max_{i} c_{i}. In this paper, we precisely analyze the competitive ratio of Greedy for the general m-valued case, and show that the algorithm Greedy is (1+c_{m}^{*})-competitive.
A Visual Entity-Relationship Model for Constraint-Based University Timetabling
Venue: arXiv cs.AI 2011
Year: 2011

University timetabling (UTT) is a complex problem due to its combinatorial nature but also the type of constraints involved. The holy grail of (constraint) programming: "the user states the problem the program solves it" remains a challenge since solution quality is tightly coupled with deriving "effective models", best handled by technology experts. In this paper, focusing on the field of university timetabling, we introduce a visual graphic communication tool that lets the user specify her problem in an abstract manner, using a visual entity-relationship model. The entities are nodes of mainly two types: resource nodes (lecturers, assistants, student groups) and events nodes (lectures, lab sessions, tutorials). The links between the nodes signify a desired relationship between them. The visual modeling abstraction focuses on the nature of the entities and their relationships and abstracts from an actual constraint model.
Optimal accessing and non-accessing structures for graph protocols
Venue: arXiv cs.CC 2011
Year: 2011

An accessing set in a graph is a subset B of vertices such that there exists D subset of B, such that each vertex of V\B has an even number of neighbors in D. In this paper, we introduce new bounds on the minimal size kappa'(G) of an accessing set, and on the maximal size kappa(G) of a non-accessing set of a graph G. We show strong connections with perfect codes and give explicitly kappa(G) and kappa'(G) for several families of graphs. Finally, we show that the corresponding decision problems are NP-Complete.
The Complexity of Nash Equilibria in Limit-Average Games
Venue: arXiv cs.GT 2011
Year: 2011

We study the computational complexity of Nash equilibria in concurrent games with limit-average objectives. In particular, we prove that the existence of a Nash equilibrium in randomised strategies is undecidable, while the existence of a Nash equilibrium in pure strategies is decidable, even if we put a constraint on the payoff of the equilibrium. Our undecidability result holds even for a restricted class of concurrent games, where nonzero rewards occur only on terminal states. Moreover, we show that the constrained existence problem is undecidable not only for concurrent games but for turn-based games with the same restriction on rewards. Finally, we prove that the constrained existence problem for Nash equilibria in (pure or randomised) stationary strategies is decidable and analyse its complexity.
A Reduced Multiple Gabor Frame for Local Time Adaptation of the Spectrogram
Venue: arXiv cs.SD 2011
Year: 2011

In this paper we propose a method for automatic local time adap- tation of the spectrogram of an audio signal, based on its decomposition within a Gabor multi-frame. The sparsity of the analyses within each individual frame is evaluated through the Rényi entropies measures. According to the sparsity of the decompositions, an optimal resolution and a reduced multi-frame are determined, defining an adapted spectrogram with variable resolution and hop size. The composition of such a reduced multi-frame allows an immediate definition of a dual frame: re-synthesis techniques for this adapted analysis are easily derived by the traditional phase vocoder scheme.
On Graphical Modeling of Preference and Importance
Venue: arXiv cs.AI 2011
Year: 2011

In recent years, CP-nets have emerged as a useful tool for supporting preference elicitation, reasoning, and representation. CP-nets capture and support reasoning with qualitative conditional preference statements, statements that are relatively natural for users to express. In this paper, we extend the CP-nets formalism to handle another class of very natural qualitative statements one often uses in expressing preferences in daily life - statements of relative importance of attributes. The resulting formalism, TCP-nets, maintains the spirit of CP-nets, in that it remains focused on using only simple and natural preference statements, uses the ceteris paribus semantics, and utilizes a graphical representation of this information to reason about its consistency and to perform, possibly constrained, optimization using it. The extra expressiveness it provides allows us to better model tradeoffs users would like to make, more faithfully representing their preferences.
How to prolong network life-span in wireless networks
Venue: arXiv cs.NI 2011
Year: 2011

One of the most important problems in wireless sensor network is to develop a routing protocol that has energy efficiency. Since the power of the sensor Nodes are limited, conserving energy and network life is a critical issue in wireless sensor network. Clustering is one of the known methods widely used to face these challenges. In this paper, a cluster based communication protocol with considering the low energy consumption in wireless sensor networks, is introduced which balances the energy load among sensor nodes. The nodes close to each other have more overlap; they sense the same data from environment and cause a waste of energy by generating repetitive data. In this paper, a cluster based routing protocol is introduced, in the proposed protocol, in each round a certain number of nodes are specified; the nodes which have at least one neighboring node at a distance less than the threshold. Then, among them the nodes with less energy and greater overlap with their neighbors have been chosen to go to sleep mode, Also, the energy imbalance among sensor nodes is reduced by integrating the distance of the nodes from the base station into clustering policies.
Multi-User MIMO with outdated CSI: Training, Feedback and Scheduling
Venue: arXiv cs.IT 2011
Year: 2011

Conventional MU-MIMO techniques, e.g. Linear Zero-Forced Beamforming (LZFB), require sufficiently accurate channel state information at the transmitter (CSIT) in order to realize spectral efficient transmission (degree of freedom gains). In practical settings, however, CSIT accuracy can be limited by a number of issues including CSI estimation, CSI feedback delay between user terminals to base stations, and the time/frequency coherence of the channel. The latter aspects of CSIT-feedback delay and channel-dynamics can lead to significant challenges in the deployment of efficient MU-MIMO systems. Recently it has been shown by Maddah-Ali and Tse (MAT) that degree of freedom gains can be realized by MU-MIMO even when the knowledge of CSIT is completely outdated. Specifically, outdated CSIT, albeit perfect CSIT, is known for transmissions only after they have taken place. This aspect of insensitivity to CSIT-feedback delay is of particular interest since it allows one to reconsider MU-MIMO design in dynamic channel conditions. Indeed, as we show, with appropriate scheduling, and even in the context of CSI estimation and feedback errors, the proposed MAT scheme can have performance advantages over conventional MU-MIMO in such scenarios.
Distributed Algorithms for Consensus and Coordination in the Presence of Packet-Dropping Communication Links - Part I: Statistical Moments Analysis Approach
Venue: arXiv cs.SY 2011
Year: 2011

This two-part paper discusses robustification methodologies for linear-iterative distributed algorithms for consensus and coordination problems in multicomponent systems, in which unreliable communication links may drop packets. We consider a setup where communication links between components can be asymmetric (i.e., component j might be able to send information to component i, but not necessarily vice-versa), so that the information exchange between components in the system is in general described by a directed graph that is assumed to be strongly connected. In the absence of communication link failures, each component i maintains two auxiliary variables and updates each of their values to be a linear combination of their corresponding previous values and the corresponding previous values of neighboring components (i.e., components that send information to node i). By appropriately initializing these two (decoupled) iterations, the system components can asymptotically calculate variables of interest in a distributed fashion; in particular, the average of the initial conditions can be calculated as a function that involves the ratio of these two auxiliary variables. The focus of this paper to robustify this double-iteration algorithm against communication link failures. We achieve this by modifying the double-iteration algorithm (by introducing some additional auxiliary variables) and prove that the modified double-iteration converges almost surely to average consensus. In the first part of the paper, we study the first and second moments of the two iterations, and use them to establish convergence, and illustrate the performance of the algorithm with several numerical examples. In the second part, in order to establish the convergence of the algorithm, we use coefficients of ergodicity commonly used in analyzing inhomogeneous Markov chains.
An Interpretation of Belief Functions by means of a Probabilistic Multi-modal Logic
Venue: arXiv cs.LO 2011
Year: 2011

While belief functions may be seen formally as a generalization of probabilistic distributions, the question of the interactions between belief functions and probability is still an issue in practice. This question is difficult, since the contexts of use of these theory are notably different and the semantics behind these theories are not exactly the same. A prominent issue is increasingly regarded by the community, that is the management of the conflicting information. Recent works have introduced new rules for handling the conflict redistribution while combining belief functions. The notion of conflict, or its cancellation by an hypothesis of open world, seems by itself to prevent a direct interpretation of belief function in a probabilistic framework. This paper addresses the question of a probabilistic interpretation of belief functions. It first introduces and implements a theoretically grounded rule, which is in essence an adaptive conjunctive rule. It is shown, how this rule is derived from a logical interpretation of the belief functions by means of a probabilistic multimodal logic; in addition, a concept of source independence is introduced, based on a principle of entropy maximization.
Towards an interoperable information infrastructure providing decision support for genomic medicine
Venue: arXiv cs.OH 2011
Year: 2011

Genetic dispositions play a major role in individual disease risk and treatment response. Genomic medicine, in which medical decisions are refined by genetic information of particular patients, is becoming increasingly important. Here we describe our work and future visions around the creation of a distributed infrastructure for pharmacogenetic data and medical decision support, based on industry standards such as the Web Ontology Language (OWL) and the Arden Syntax.
Improving Recommendation Quality by Merging Collaborative Filtering and Social Relationships
Venue: arXiv cs.SI 2011
Year: 2011

Matrix Factorization techniques have been successfully applied to raise the quality of suggestions generated by Collaborative Filtering Systems (CFSs). Traditional CFSs based on Matrix Factorization operate on the ratings provided by users and have been recently extended to incorporate demographic aspects such as age and gender. In this paper we propose to merge CFS based on Matrix Factorization and information regarding social friendships in order to provide users with more accurate suggestions and rankings on items of their interest. The proposed approach has been evaluated on a real-life online social network; the experimental results show an improvement against existing CFSs. A detailed comparison with related literature is also present.
Properties and Applications of Programs with Monotone and Convex Constraints
Venue: arXiv cs.AI 2011
Year: 2011

We study properties of programs with monotone and convex constraints. We extend to these formalisms concepts and results from normal logic programming. They include the notions of strong and uniform equivalence with their characterizations, tight programs and Fages Lemma, program completion and loop formulas. Our results provide an abstract account of properties of some recent extensions of logic programming with aggregates, especially the formalism of lparse programs. They imply a method to compute stable models of lparse programs by means of off-the-shelf solvers of pseudo-boolean constraints, which is often much faster than the smodels system.
Computationally Feasible VCG Mechanisms
Venue: arXiv cs.GT 2011
Year: 2011

A major achievement of mechanism design theory is a general method for the construction of truthful mechanisms called VCG (Vickrey, Clarke, Groves). When applying this method to complex problems such as combinatorial auctions, a difficulty arises: VCG mechanisms are required to compute optimal outcomes and are, therefore, computationally infeasible. However, if the optimal outcome is replaced by the results of a sub-optimal algorithm, the resulting mechanism (termed VCG-based) is no longer necessarily truthful. The first part of this paper studies this phenomenon in depth and shows that it is near universal. Specifically, we prove that essentially all reasonable approximations or heuristics for combinatorial auctions as well as a wide class of cost minimization problems yield non-truthful VCG-based mechanisms. We generalize these results for affine maximizers. The second part of this paper proposes a general method for circumventing the above problem. We introduce a modification of VCG-based mechanisms in which the agents are given a chance to improve the output of the underlying algorithm. When the agents behave truthfully, the welfare obtained by the mechanism is at least as good as the one obtained by the algorithms output. We provide a strong rationale for truth-telling behavior. Our method satisfies individual rationality as well.
Combination Strategies for Semantic Role Labeling
Venue: arXiv cs.AI 2011
Year: 2011

This paper introduces and analyzes a battery of inference models for the problem of semantic role labeling: one based on constraint satisfaction, and several strategies that model the inference as a meta-learning problem using discriminative classifiers. These classifiers are developed with a rich set of novel features that encode proposition and sentence-level information. To our knowledge, this is the first work that: (a) performs a thorough analysis of learning-based inference models for semantic role labeling, and (b) compares several inference strategies in this context. We evaluate the proposed inference strategies in the framework of the CoNLL-2005 shared task using only automatically-generated syntactic information. The extensive experimental evaluation and analysis indicates that all the proposed inference strategies are successful -they all outperform the current best results reported in the CoNLL-2005 evaluation exercise- but each of the proposed approaches has its advantages and disadvantages. Several important traits of a state-of-the-art SRL combination strategy emerge from this analysis: (i) individual models should be combined at the granularity of candidate arguments rather than at the granularity of complete solutions; (ii) the best combination strategy uses an inference model based in learning; and (iii) the learning-based inference benefits from max-margin classifiers and global feedback.
Properties of Carry Value Transformation
Venue: arXiv cs.DM 2011
Year: 2011

The notion of Carry Value Transformation (CVT) is a model of Discrete Deterministic Dynamical System. In this paper, we have studied some interesting properties of CVT and proved that (1) the addition of any two non-negative integers is same as the sum of their CVT and XOR values. (2) While performing the repeated addition of CVT and XOR of two non-negative integers "a" and "b" (where a >= b), the number of iterations required to get either CVT=0 or XOR=0 is at most the length of "a" when both are expressed as binary strings. A similar process of addition of Modified Carry Value Transformation (MCVT) and XOR requires a maximum of two iterations for MCVT to be zero. (3) An equivalence relation is defined in the set (Z x Z) which divides the CV table into disjoint equivalence classes.
A note on Prüfer-like coding and counting forests of uniform hypertrees
Venue: arXiv cs.DM 2011
Year: 2011

This note presents an encoding and a decoding algorithms for a forest of (labelled) rooted uniform hypertrees and hypercycles in linear time, by using as few as $n - 2$ integers in the range $[1,n]$. It is a simple extension of the classical Prüfer code for (labelled) rooted trees to an encoding for forests of (labelled) rooted uniform hypertrees and hypercycles, which allows to count them up according to their number of vertices, hyperedges and hypertrees. In passing, we also find Cayley's formula for the number of (labelled) rooted trees as well as its generalisation to the number of hypercycles found by Selivanov in the early 70's.
Completion Time in Broadcast Channel and Interference Channel
Venue: arXiv cs.IT 2011
Year: 2011

In a multi-user channel, completion time refers to the number of channel uses required for users, each with some given fixed bit pool, to complete the transmission of all their data bits. This paper extends the information theoretic formulation of multi-access completion time to broadcast channel and interference channel, enabling us to obtain the so-called completion time region (CTR), which, analogous to capacity region, characterizes all possible trade-offs between users' completion times. Specifically, for Gaussian broadcast channel (GBC) and Gaussian interference channel (GIC) in the strong/very strong regime, the exact CTR is obtained. For GIC in the weak/mixed regime, an achievable CTR based on the Etkin-Tse-Wang scheme and an outer-bound are obtained.
Alan Turing and the Origins of Complexity
Venue: arXiv cs.CC 2011
Year: 2011

The 75th anniversary of Turing's seminal paper and his centennial year anniversary occur in 2011 and 2012, respectively. It is natural to review and assess Turing's contributions in diverse fields in the light of new developments that his thoughts has triggered in many scientific communities. Here, the main idea is to discuss how the work of Turing allows us to change our views on the foundations of Mathematics, much like quantum mechanics changed our conception of the world of Physics. Basic notions like computability and universality are discussed in a broad context, making special emphasis on how the notion of complexity can be given a precise meaning after Turing, i.e., not just qualitative but also quantitative. Turing's work is given some historical perspective with respect to some of his precursors, contemporaries and mathematicians who took up his ideas farther.
The BlueNetwork Concept
Venue: arXiv cs.HC 2011
Year: 2011

Most of energy efficiency and carbon reduction initiatives and concepts attempt to regulate and optimize machines behavior, and therefore, human behavior itself is left neglected. Although most of energy and resource consumption is the result of machines functioning and behavior (including domesticated animals such as cows), these behaviors themselves are actually in answer to humans demands and needs, and therefore, can be considered the indirect results of humans behavior. Resolving the source of problems, i.e., the unhealthy human behavior, not only reduces these footprints including energy and water consumption, and GHG emissions, it also helps increasing the quality of life in society. Here, we propose an approach which focuses on adjusting humans behavior toward eliminating unnecessary demand on the machines that consequently lowers the consumption. This goal is achieved by creating a social environment in which directed and selective interactions help humans to adjust to healthier behavior. The solution consists of human-friendly interfaces and also artificial intelligence software in order to learn and emulate human interactions.