OpenRaiser/Intern-Atlas huggingface dataset:
Xheal: Localized Self-healing using Expanders
Venue: arXiv cs.DS 2011
Year: 2011

We consider the problem of self-healing in reconfigurable networks (e.g. peer-to-peer and wireless mesh networks) that are under repeated attack by an omniscient adversary and propose a fully distributed algorithm, Xheal that maintains good expansion and spectral properties of the network, also keeping the network connected. Moreover, Xheal does this while allowing only low stretch and degree increase per node. Thus, the algorithm heals global properties while only doing local changes and using only local information. Our work improves over the self-healing algorithms 'Forgiving tree'[PODC 2008] and 'Forgiving graph'[PODC 2009] (using a similar model) in that we are able to give guarantees on degree and stretch, while at the same time preserving the expansion and spectral properties of the network. These repairs preserve the invariants in the following sense. At any point in the algorithm, the expansion of the graph will be either `better' than the expansion of the graph formed by considering only the adversarial insertions (not the adversarial deletions) or the expansion will be, at least, a constant. Also, the stretch i.e. the distance between any pair of nodes in the healed graph is no more than a $O(\log n)$ factor. Similarly, at any point, a node $v$ whose degree would have been $d$ in the graph with adversarial insertions only, will have degree at most $O(κd)$ in the actual graph, for a small parameter $κ$. We also provide bounds on the second smallest eigenvalue of the Laplacian which captures key properties such as mixing time, conductance, congestion in routing etc. Our distributed data structure has low amortized latency and bandwidth requirements.
Settling the feasibility of interference alignment for the MIMO interference channel: the symmetric square case
Venue: arXiv cs.IT 2011
Year: 2011

Determining the feasibility conditions for vector space interference alignment in the K-user MIMO interference channel with constant channel coefficients has attracted much recent attention yet remains unsolved. The main result of this paper is restricted to the symmetric square case where all transmitters and receivers have N antennas, and each user desires d transmit dimensions. We prove that alignment is possible if and only if the number of antennas satisfies N>= d(K+1)/2. We also show a necessary condition for feasibility of alignment with arbitrary system parameters. An algebraic geometry approach is central to the results.
SAR Imaging of Moving Targets via Compressive Sensing
Venue: arXiv cs.IT 2011
Year: 2011

An algorithm based on compressive sensing (CS) is proposed for synthetic aperture radar (SAR) imaging of moving targets. The received SAR echo is decomposed into the sum of basis sub-signals, which are generated by discretizing the target spatial domain and velocity domain and synthesizing the SAR received data for every discretized spatial position and velocity candidate. In this way, the SAR imaging problem is converted into sub-signal selection problem. In the case that moving targets are sparsely distributed in the observed scene, their reflectivities, positions and velocities can be obtained by using the CS technique. It is shown that, compared with traditional algorithms, the target image obtained by the proposed algorithm has higher resolution and lower side-lobe while the required number of measurements can be an order of magnitude less than that by sampling at Nyquist sampling rate. Moreover, multiple targets with different speeds can be imaged simultaneously, so the proposed algorithm has higher efficiency.
Platform for Assessing Strategic Alignment Using Enterprise Architecture: Application to E-Government Process Assessment
Venue: arXiv cs.SE 2011
Year: 2011

This paper presents an overview of S2AEA (v2) (Strategic Alignment Assessment based on Enterprise Architecture (version2)), a platform for modelling enterprise architecture and for assessing strategic alignment based on internal enterprise architecture metrics. The idea of the platform is based on the fact that enterprise architecture provides a structure for business processes and information systems that supports them. This structure can be used to measure the degree of consistency between business strategies and information systems. In that sense, this paper presents a platform illustrating the role of enterprise architecture in the strategic alignment assessment. This assessment can be used in auditing information systems. The platform is applied to assess an e-government process.
Intervention in Power Control Games With Selfish Users
Venue: arXiv cs.IT 2011
Year: 2011

We study the power control problem in wireless ad hoc networks with selfish users. Without incentive schemes, selfish users tend to transmit at their maximum power levels, causing significant interference to each other. In this paper, we study a class of incentive schemes based on intervention to induce selfish users to transmit at desired power levels. An intervention scheme can be implemented by introducing an intervention device that can monitor the power levels of users and then transmit power to cause interference to users. We mainly consider first-order intervention rules based on individual transmit powers. We derive conditions on design parameters and the intervention capability to achieve a desired outcome as a (unique) Nash equilibrium and propose a dynamic adjustment process that the designer can use to guide users and the intervention device to the desired outcome. The effect of using intervention rules based on aggregate receive power is also analyzed. Our results show that with perfect monitoring intervention schemes can be designed to achieve any positive power profile while using interference from the intervention device only as a threat. We also analyze the case of imperfect monitoring and show that a performance loss can occur. Lastly, simulation results are presented to illustrate the performance improvement from using intervention rules and compare the performances of different intervention rules.
The Design of a Novel Prismatic Drive for a Three-DOF Parallel-Kinematics Machine
Venue: arXiv cs.RO 2011
Year: 2011

The design of a novel prismatic drive is reported in this paper. This transmission is based on Slide-o-Cam, a cam mechanism with multiple rollers mounted on a common translating follower. The design of Slide-o-Cam was reported elsewhere. This drive thus provides pure-rolling motion, thereby reducing the friction of rack-and-pinions and linear drives. Such properties can be used to design new transmissions for parallel-kinematics machines. In this paper, this transmission is intended to replace the ball-screws in Orthoglide, a three-dof parallel robot intended for machining applications.
Hide-and-Seek with Directional Sensing
Venue: arXiv cs.GT 2011
Year: 2011

We consider a game played between a hider, who hides a static object in one of several possible positions in a bounded planar region, and a searcher, who wishes to reach the object by querying sensors placed in the plane. The searcher is a mobile agent, and whenever it physically visits a sensor, the sensor returns a random direction, corresponding to a half-plane in which the hidden object is located. We first present a novel search heuristic and characterize bounds on the expected distance covered before reaching the object. Next, we model this game as a large-dimensional zero-sum dynamic game and we apply a recently introduced randomized sampling technique that provides a probabilistic level of security to the hider. We observe that, when the randomized sampling approach is only allowed to select a very small number of samples, the cost of the heuristic is comparable to the security level provided by the randomized procedure. However, as we allow the number of samples to increase, the randomized procedure provides a higher probabilistic security level.
JavaCtx: Seamless Toolchain Integration for Context-Oriented Programming
Venue: arXiv cs.PL 2011
Year: 2011

Context-oriented programming is an emerging paradigm addressing at the language level the issue of dynamic software adaptation and modularization of context-specific concerns. In this paper we propose JavaCtx, a tool which employs coding conventions to generate the context-aware semantics for Java programs and subsequently weave it into the application. The contribution of JavaCtx is twofold: the design of a set of coding conventions which allow to write context-oriented software in plain Java and the concept of context-oriented semantics injection, which allows to introduce the context-aware semantics without a source-to-source compilations process which disrupts the structure of the code. Both these points allow to seamless integrate JavaCtx in the existing industrial-strength appliances and by far ease the development of context-oriented software.
Efficient First Order Methods for Linear Composite Regularizers
Venue: arXiv cs.LG 2011
Year: 2011

A wide class of regularization problems in machine learning and statistics employ a regularization term which is obtained by composing a simple convex function ωwith a linear transformation. This setting includes Group Lasso methods, the Fused Lasso and other total variation methods, multi-task learning methods and many more. In this paper, we present a general approach for computing the proximity operator of this class of regularizers, under the assumption that the proximity operator of the function ωis known in advance. Our approach builds on a recent line of research on optimal first order optimization methods and uses fixed point iterations for numerically computing the proximity operator. It is more general than current approaches and, as we show with numerical simulations, computationally more efficient than available first order methods which do not achieve the optimal rate. In particular, our method outperforms state of the art O(1/T) methods for overlapping Group Lasso and matches optimal O(1/T^2) methods for the Fused Lasso and tree structured Group Lasso.
Logical Varieties in Normative Reasoning
Venue: arXiv cs.LO 2011
Year: 2011

Although conventional logical systems based on logical calculi have been successfully used in mathematics and beyond, they have definite limitations that restrict their application in many cases. For instance, the principal condition for any logical calculus is its consistency. At the same time, knowledge about large object domains (in science or in practice) is essentially inconsistent. Logical prevarieties and varieties were introduced to eliminate these limitations in a logically correct way. In this paper, the Logic of Reasonable Inferences is described. This logic has been applied successfully to model legal reasoning with inconsistent knowledge. It is demonstrated that this logic is a logical variety and properties of logical varieties related to legal reasoning are developed.
Operand Folding Hardware Multipliers
Venue: arXiv cs.MS 2011
Year: 2011

This paper describes a new accumulate-and-add multiplication algorithm. The method partitions one of the operands and re-combines the results of computations done with each of the partitions. The resulting design turns-out to be both compact and fast. When the operands' bit-length $m$ is 1024, the new algorithm requires only $0.194m+56$ additions (on average), this is about half the number of additions required by the classical accumulate-and-add multiplication algorithm ($\frac{m}2$).
Automatic Vehicle Checking Agent (VCA)
Venue: arXiv cs.AI 2011
Year: 2011

A definition of intelligence is given in terms of performance that can be quantitatively measured. In this study, we have presented a conceptual model of Intelligent Agent System for Automatic Vehicle Checking Agent (VCA). To achieve this goal, we have introduced several kinds of agents that exhibit intelligent features. These are the Management agent, internal agent, External Agent, Watcher agent and Report agent. Metrics and measurements are suggested for evaluating the performance of Automatic Vehicle Checking Agent (VCA). Calibrate data and test facilities are suggested to facilitate the development of intelligent systems.
Symbolic computation of weighted Moore-Penrose inverse using partitioning method
Venue: arXiv cs.SC 2011
Year: 2011

We propose a method and algorithm for computing the weighted Moore-Penrose inverse of one-variable rational matrices. Continuing this idea, we develop an algorithm for computing the weighted Moore-Penrose inverse of one-variable polynomial matrix. These methods and algorithms are generalizations of the method for computing the weighted Moore-Penrose inverse for constant matrices, originated in Wang and Chen [G.R. Wang, Y.L. Chen, A recursive algorithm for computing the weighted Moore-Penrose inverse AMN, J. Comput. Math. 4 (1986) 74-85], and the partitioning method for computing the Moore-Penrose inverse of rational and polynomial matrices introduced in Stanimirovic and Tasic [P.S. Stanimirovic, M.B. Tasic, Partitioning method for rational and polynomial matrices, Appl. Math. Comput. 155 (2004) 137-163]. Algorithms are implemented in the symbolic computational package MATHEMATICA.
Dimensionality Decrease Heuristics for NP Complete Problems
Venue: arXiv cs.DS 2011
Year: 2011

The vast majority of scientific community believes that P!=NP, with countless supporting arguments. The number of people who believe otherwise probably amounts to as few as those opposing the 2nd Law of Thermodynamics. But isn't nature elegant enough, not to resource to brute-force search? In this article, a novel concept of dimensionality is presented, which may lead to a more efficient class of heuristic implementations to solve NP complete problems. Thus, broadening the universe of man-machine tractable problems. Dimensionality, as defined here, will be a closer analog of strain energy in nature.
New Hardness Results in Rainbow Connectivity
Venue: arXiv cs.CC 2011
Year: 2011

A path in an edge colored graph is said to be a rainbow path if no two edges on the path have the same color. An edge colored graph is (strongly) rainbow connected if there exists a (geodesic) rainbow path between every pair of vertices. The (strong) rainbow connectivity of a graph $G$, denoted by ($src(G)$, respectively) $rc(G)$ is the smallest number of colors required to edge color the graph such that the graph is (strong) rainbow connected. It is known that for \emph{even} $k$ to decide whether the rainbow connectivity of a graph is at most $k$ or not is NP-hard. It was conjectured that for all $k$, to decide whether $rc(G) \leq k$ is NP-hard. In this paper we prove this conjecture. We also show that it is NP-hard to decide whether $src(G) \leq k$ or not even when $G$ is a bipartite graph.
Preprocessing: A Prerequisite for Discovering Patterns in WUM Process
Venue: arXiv cs.DB 2011
Year: 2011

Web log data is usually diverse and voluminous. This data must be assembled into a consistent, integrated and comprehensive view, in order to be used for pattern discovery. Without properly cleaning, transforming and structuring the data prior to the analysis, one cannot expect to find meaningful patterns. As in most data mining applications, data preprocessing involves removing and filtering redundant and irrelevant data, removing noise, transforming and resolving any inconsistencies. In this paper, a complete preprocessing methodology having merging, data cleaning, user/session identification and data formatting and summarization activities to improve the quality of data by reducing the quantity of data has been proposed. To validate the efficiency of the proposed preprocessing methodology, several experiments are conducted and the results show that the proposed methodology reduces the size of Web access log files down to 73-82% of the initial size and offers richer logs that are structured for further stages of Web Usage Mining (WUM). So preprocessing of raw data in this WUM process is the central theme of this paper.
Comparison of Random Waypoint & Random Walk Mobility Model under DSR, AODV & DSDV MANET Routing Protocols
Venue: arXiv cs.NI 2011
Year: 2011

Mobile Adhoc Network is a kind of wireless ad hoc network where nodes are connected wirelessly and the network is self configuring. MANET may work in a standalone manner or may be a part of another network. In this paper we have compared Random Walk Mobility Model and Random Waypoint Mobility Model over two reactive routing protocols Dynamic Source Routing (DSR) and Adhoc On-Demand Distance Vector Routing (AODV) protocol and one Proactive routing protocol Distance Sequenced Distance Vector Routing (DSDV) Our analysis showed that DSR, AODV & DSDV under Random Walk and Random Way Point Mobility models have similar results for similar inputs however as the pause time increases so does the difference in performance rises. They show that their motion, direction, angle of direction, speed is same under both mobility models. We have made their analysis on packet delivery ratio, throughput and routing overhead. We have tested them with different criteria like different number of nodes, speed and different maximum number of connections.
On the regularity of iterated hairpin completion of a single word
Venue: arXiv cs.FL 2011
Year: 2011

Hairpin completion is an abstract operation modeling a DNA bio-operation which receives as input a DNA strand $w = xαy \calpha$, and outputs $w' = x αy \barα \bar{x}$, where $\bar{x}$ denotes the Watson-Crick complement of $x$. In this paper, we focus on the problem of finding conditions under which the iterated hairpin completion of a given word is regular. According to the numbers of words $α$ and $\calpha$ that initiate hairpin completion and how they are scattered, we classify the set of all words $w$. For some basic classes of words $w$ containing small numbers of occurrences of $α$ and $\calpha$, we prove that the iterated hairpin completion of $w$ is regular. For other classes with higher numbers of occurrences of $α$ and $\calpha$, we prove a necessary and sufficient condition for the iterated hairpin completion of a word in these classes to be regular.
Design, Engineering, and Experimental Analysis of a Simulated Annealing Approach to the Post-Enrolment Course Timetabling Problem
Venue: arXiv cs.DM 2011
Year: 2011

The post-enrolment course timetabling (PE-CTT) is one of the most studied timetabling problems, for which many instances and results are available. In this work we design a metaheuristic approach based on Simulated Annealing to solve the PE-CTT. We consider all the different variants of the problem that have been proposed in the literature and we perform a comprehensive experimental analysis on all the public instances available. The outcome is that our solver, properly engineered and tuned, performs very well on all cases, providing the new best known results on many instances and state-of-the-art values for the others.
An Axis-Based Representation for Recognition
Venue: arXiv cs.CV 2011
Year: 2011

This paper presents a new axis-based shape representation scheme along with a matching framework to address the problem of generic shape recognition. The main idea is to define the relative spatial arrangement of local symmetry axes and their metric properties in a shape centered coordinate frame. The resulting descriptions are invariant to scale, rotation, small changes in viewpoint and articulations. Symmetry points are extracted from a surface whose level curves roughly mimic the motion by curvature. By increasing the amount of smoothing on the evolving curve, only those symmetry axes that correspond to the most prominent parts of a shape are extracted. The representation does not suffer from the common instability problems of the traditional connected skeletons. It captures the perceptual qualities of shapes well. Therefore finding the similarities and the differences among shapes becomes easier. The matching process gives highly successful results on a diverse database of 2D shapes.
Diversity Analysis of Symbol-by-Symbol Linear Equalizers
Venue: arXiv cs.IT 2011
Year: 2011

In frequency-selective channels linear receivers enjoy significantly-reduced complexity compared with maximum likelihood receivers at the cost of performance degradation which can be in the form of a loss of the inherent frequency diversity order or reduced coding gain. This paper demonstrates that the minimum mean-square error symbol-by-symbol linear equalizer incurs no diversity loss compared to the maximum likelihood receivers. In particular, for a channel with memory $ν$, it achieves the full diversity order of ($ν+1$) while the zero-forcing symbol-by-symbol linear equalizer always achieves a diversity order of one.
Pattern discovery for semi-structured web pages using bar-tree representation
Venue: arXiv cs.IR 2011
Year: 2011

Many websites with an underlying database containing structured data provide the richest and most dense source of information relevant for topical data integration. The real data integration requires sustainable and reliable pattern discovery to enable accurate content retrieval and to recognize pattern changes from time to time; yet, extracting the structured data from web documents is still lacking from its accuracy. This paper proposes the bar-tree representation to describe the whole pattern of web pages in an efficient way based on the reverse algorithm. While previous algorithms always trace the pattern and extract the region of interest from \textit{top root}, the reverse algorithm recognizes the pattern from the region of interest to both top and bottom roots simultaneously. The attributes are then extracted and labeled reversely from the region of interest of targeted contents. Since using conventional representations for the algorithm should require more computational power, the bar-tree method is developed to represent the generated patterns using bar graphs characterized by the depths and widths from the document roots. We show that this representation is suitable for extracting the data from the semi-structured web sources, and for detecting the template changes of targeted pages. The experimental results show perfect recognition rate for template changes in several web targets.
Multi-representation d'une ontologie : OWL, bases de donnees, systèmes de types et d'objets
Venue: arXiv cs.IR 2011
Year: 2011

Due to the emergence of the semantic Web and the increasing need to formalize human knowledge, ontologie engineering is now an important activity. But is this activity very different from other ones like software engineering, for example ? In this paper, we investigate analogies between ontologies on one hand, types, objects and data bases on the other one, taking into account the notion of evolution of an ontology. We represent a unique ontology using different paradigms, and observe that the distance between these different concepts is small. We deduce from this constatation that ontologies and more specifically ontology description languages can take advantage of beeing fertilizated with some other computer science domains and inherit important characteristics as modularity, for example.