OpenRaiser/Intern-Atlas huggingface dataset:
A Supermodular Optimization Framework for Leader Selection under Link Noise in Linear Multi-Agent Systems
Venue: arXiv cs.SY 2012
Year: 2012

In many applications of multi-agent systems (MAS), a set of leader agents acts as a control input to the remaining follower agents. In this paper, we introduce an analytical approach to selecting leader agents in order to minimize the total mean-square error of the follower agent states from their desired value in steady-state in the presence of noisy communication links. We show that the problem of choosing leaders in order to minimize this error can be solved using supermodular optimization techniques, leading to efficient algorithms that are within a provable bound of the optimum. We formulate two leader selection problems within our framework, namely the problem of choosing a fixed number of leaders to minimize the error, as well as the problem of choosing the minimum number of leaders to achieve a tolerated level of error. We study both leader selection criteria for different scenarios, including MAS with static topologies, topologies experiencing random link or node failures, switching topologies, and topologies that vary arbitrarily in time due to node mobility. In addition to providing provable bounds for all these cases, simulation results demonstrate that our approach outperforms other leader selection methods, such as node degree-based and random selection methods, and provides comparable performance to current state of the art algorithms.
An Integrated Aerial Telecommunications Network that Supports Emergency Traffic
Venue: arXiv cs.NI 2012
Year: 2012

This paper outlines how an aerial telecommunications network can optimally meet the stringent needs of emergency relief and recovery operations. We propose a novel architecture, made of an integrated and highly dynamic multi-purpose aerial telecommunications infrastructure that can be contextually extended with fast-deploying high or low altitude platforms. In particular, we analyze the interest and challenges of adapting core concepts from substitution networks and controlled mobility mechanisms, so that a base network can be seamlessly augmented, both in terms of capacity and functions. We give an estimation of the emergency traffic supported by the lower altitude platforms in an example scenario and discuss the challenges posed by this architecture, notably in terms of disaster resilience and ability to efficiently provide sustained first responder communications.
Credibility in Web Search Engines
Venue: arXiv cs.IR 2012
Year: 2012

Web search engines apply a variety of ranking signals to achieve user satisfaction, i.e., results pages that provide the best-possible results to the user. While these ranking signals implicitly consider credibility (e.g., by measuring popularity), explicit measures of credibility are not applied. In this chapter, credibility in Web search engines is discussed in a broad context: credibility as a measure for including documents in a search engine's index, credibility as a ranking signal, credibility in the context of universal search results, and the possibility of using credibility as an explicit measure for ranking purposes. It is found that while search engines-at least to a certain extent-show credible results to their users, there is no fully integrated credibility framework for Web search engines.
System identification and modeling for interacting and non-interacting tank systems using intelligent techniques
Venue: arXiv cs.AI 2012
Year: 2012

System identification from the experimental data plays a vital role for model based controller design. Derivation of process model from first principles is often difficult due to its complexity. The first stage in the development of any control and monitoring system is the identification and modeling of the system. Each model is developed within the context of a specific control problem. Thus, the need for a general system identification framework is warranted. The proposed framework should be able to adapt and emphasize different properties based on the control objective and the nature of the behavior of the system. Therefore, system identification has been a valuable tool in identifying the model of the system based on the input and output data for the design of the controller. The present work is concerned with the identification of transfer function models using statistical model identification, process reaction curve method, ARX model, genetic algorithm and modeling using neural network and fuzzy logic for interacting and non interacting tank process. The identification technique and modeling used is prone to parameter change & disturbance. The proposed methods are used for identifying the mathematical model and intelligent model of interacting and non interacting process from the real time experimental data.
A Regularized Saddle-Point Algorithm for Networked Optimization with Resource Allocation Constraints
Venue: arXiv cs.SY 2012
Year: 2012

We propose a regularized saddle-point algorithm for convex networked optimization problems with resource allocation constraints. Standard distributed gradient methods suffer from slow convergence and require excessive communication when applied to problems of this type. Our approach offers an alternative way to address these problems, and ensures that each iterative update step satisfies the resource allocation constraints. We derive step-size conditions under which the distributed algorithm converges geometrically to the regularized optimal value, and show how these conditions are affected by the underlying network topology. We illustrate our method on a robotic network application example where a group of mobile agents strive to maintain a moving target in the barycenter of their positions.
On fixed-parameter algorithms for Split Vertex Deletion
Venue: arXiv cs.DS 2012
Year: 2012

In the Split Vertex Deletion problem, given a graph G and an integer k, we ask whether one can delete k vertices from the graph G to obtain a split graph (i.e., a graph, whose vertex set can be partitioned into two sets: one inducing a clique and the second one inducing an independent set). In this paper we study fixed-parameter algorithms for Split Vertex Deletion parameterized by k: we show that, up to a factor quasipolynomial in k and polynomial in n, the Split Vertex Deletion problem can be solved in the same time as the well-studied Vertex Cover problem. Plugging the currently best fixed-parameter algorithm for Vertex Cover due to Chen et al. [TCS 2010], we obtain an algorithm that solves Split Vertex Deletion in time O(1.2738^k * k^O(log k) + n^O(1)). To achieve our goal, we prove the following structural result that may be of independent interest: for any graph G we may compute a family P of size n^O(log n) containing partitions of V(G) into two parts, such for any two disjoint subsets X_C, X_I of V(G) where G[X_C] is a clique and G[X_I] is an independent set, there is a partition in P which contains all vertices of X_C on one side and all vertices of X_I on the other.
A Polylogarithimic Approximation Algorithm for Edge-Disjoint Paths with Congestion 2
Venue: arXiv cs.DS 2012
Year: 2012

In the Edge-Disjoint Paths with Congestion problem (EDPwC), we are given an undirected n-vertex graph G, a collection M={(s_1,t_1),...,(s_k,t_k)} of demand pairs and an integer c. The goal is to connect the maximum possible number of the demand pairs by paths, so that the maximum edge congestion - the number of paths sharing any edge - is bounded by c. When the maximum allowed congestion is c=1, this is the classical Edge-Disjoint Paths problem (EDP). The best current approximation algorithm for EDP achieves an $O(\sqrt n)$-approximation, by rounding the standard multi-commodity flow relaxation of the problem. This matches the $Ω(\sqrt n)$ lower bound on the integrality gap of this relaxation. We show an $O(poly log k)$-approximation algorithm for EDPwC with congestion c=2, by rounding the same multi-commodity flow relaxation. This gives the best possible congestion for a sub-polynomial approximation of EDPwC via this relaxation. Our results are also close to optimal in terms of the number of pairs routed, since EDPwC is known to be hard to approximate to within a factor of $\tildeΩ((\log n)^{1/(c+1)})$ for any constant congestion c. Prior to our work, the best approximation factor for EDPwC with congestion 2 was $\tilde O(n^{3/7})$, and the best algorithm achieving a polylogarithmic approximation required congestion 14.
Securing Instrumented Environments over Content-Centric Networking: the Case of Lighting Control
Venue: arXiv cs.CR 2012
Year: 2012

Instrumented environments, such as modern building automation systems (BAS), are becoming commonplace and are increasingly interconnected with (and sometimes by) enterprise networks and the Internet. Regardless of the underlying communication platform, secure control of devices in such environments is a challenging task. The current trend is to move from proprietary communication media and protocols to IP over Ethernet. While the move to IP represents progress, new and different Internet architectures might be better-suited for instrumented environments. In this paper, we consider security of instrumented environments in the context of Content-Centric Networking (CCN). In particular, we focus on building automation over Named-Data Networking (NDN), a prominent instance of CCN. After identifying security requirements in a specific BAS sub-domain (lighting control), we construct a concrete NDN-based security architecture, analyze its properties and report on preliminary implementation and experimental results. We believe in securing a communication paradigm well outside of its claimed forte of content distribution. At the same time, we provide a viable (secure and efficient) communication platform for a class of instrumented environments exemplified by lighting control.
Performance of MIMO Relay DCSK-CD Systems over Nakagami Fading Channels
Venue: arXiv cs.OH 2012
Year: 2012

A multi-access multiple-input multiple-output (MIMO) relay differential chaos shift keying cooperative diversity (DCSK-CD) system is proposed in this paper as a comprehensive cooperation scheme, in which the relay and destination both employ multiple antennas to strengthen the robustness against signal fading in a wireless network. It is shown that, with spatial diversity gains, the bit error rate (BER) performance of the proposed system is remarkably better than the conventional DCSK non-cooperation (DCSK-NC) and DCSK cooperative communication (DCSK-CC) systems. Moreover, the exact BER and close-form expressions of the proposed system are derived over Nakagami fading channels through the moment generating function (MGF), which is shown to be highly consistent with the simulation results. Meanwhile, this paper illustrates a trade-off between the performance and the complexity, and provides a threshold for the number of relay antennas keeping the user consumed energy constant. Due to the above-mentioned advantages, the proposed system stands out as a good candidate or alternative for energy-constrained wireless communications based on chaotic modulation, especially for low-power and low-cost wireless personal area networks (WPANs).
A Locale for Minimal Bad Sequences
Venue: arXiv cs.LO 2012
Year: 2012

We present a locale that abstracts over the necessary ingredients for constructing a minimal bad sequence, as required in classical proofs of Higman's lemma and Kruskal's tree theorem.
Building Cooperative Networks
Venue: arXiv cs.GT 2012
Year: 2012

We study the cooperation problem in the framework of evolutionary game theory using the prisoner's dilemma as metaphor of the problem. Considering the growing process of the system and individuals with imitation capacity, we show conditions that allow to form highly cooperative networks of any size and topology. Introducing general considerations of real systems, we reduce the required conditions for cooperation to evolve approaching the benefit-cost ratio r to the theoretical minimum r=1, when the mean connectivity of the individuals is increased. Through the paper, we distinguish different mechanisms that allow the system to maintain high levels of cooperation when the system grows by incorporation of defectors. These mechanisms require heterogeneity among individuals for cooperation to evolve. However, the required conditions and heterogeneities are drastically reduced as compared to those required for static networks.
Compressed Sensing based Protocol for Efficient Reconstruction of Sparse Superimposed Data in a Multi-Hop Wireless Sensor Network
Venue: arXiv cs.OH 2012
Year: 2012

We consider a multi-hop wireless sensor network that measures sparse events and propose a simple forwarding protocol based on Compressed Sensing (CS) which does not need any sophisticated Media Access Control (MAC) scheduling, neither a routing protocol, thereby making significant overhead and energy savings. By means of flooding, multiple packets with different superimposed measurements are received simultaneously at any node. Thanks to our protocol, each node is able to recover each measurement and forward it while avoiding cycles. Numerical results show that our protocol achieves close to zero reconstruction errors at the sink, while greatly reducing overhead. This initial research reveals a new and promising approach to protocol design through CS for wireless mesh and sensor networks.
Improved Perfect Space-Time Block Codes
Venue: arXiv cs.IT 2012
Year: 2012

The perfect space-time block codes (STBCs) are based on four design criteria - full-rateness, non-vanishing determinant, cubic shaping and uniform average transmitted energy per antenna per time slot. Cubic shaping and transmission at uniform average energy per antenna per time slot are important from the perspective of energy efficiency of STBCs. The shaping criterion demands that the {\it generator matrix} of the lattice from which each layer of the perfect STBC is carved be unitary. In this paper, it is shown that unitariness is not a necessary requirement for energy efficiency in the context of space-time coding with finite input constellations, and an alternative criterion is provided that enables one to obtain full-rate (rate of $n_t$ complex symbols per channel use for an $n_t$ transmit antenna system) STBCs with larger {\it normalized minimum determinants} than the perfect STBCs. Further, two such STBCs, one each for 4 and 6 transmit antennas, are presented and they are shown to have larger normalized minimum determinants than the comparable perfect STBCs which hitherto had the best known normalized minimum determinants.
Graph Operations on Parity Games and Polynomial-Time Algorithms
Venue: arXiv cs.GT 2012
Year: 2012

Parity games are games that are played on directed graphs whose vertices are labeled by natural numbers, called priorities. The players push a token along the edges of the digraph. The winner is determined by the parity of the greatest priority occurring infinitely often in this infinite play. A motivation for studying parity games comes from the area of formal verification of systems by model checking. Deciding the winner in a parity game is polynomial time equivalent to the model checking problem of the modal mu-calculus. Another strong motivation lies in the fact that the exact complexity of solving parity games is a long-standing open problem, the currently best known algorithm being subexponential. It is known that the problem is in the complexity classes UP and coUP. In this paper we identify restricted classes of digraphs where the problem is solvable in polynomial time, following an approach from structural graph theory. We consider three standard graph operations: the join of two graphs, repeated pasting along vertices, and the addition of a vertex. Given a class C of digraphs on which we can solve parity games in polynomial time, we show that the same holds for the class obtained from C by applying once any of these three operations to its elements. These results provide, in particular, polynomial time algorithms for parity games whose underlying graph is an orientation of a complete graph, a complete bipartite graph, a block graph, or a block-cactus graph. These are classes where the problem was not known to be efficiently solvable. Previous results concerning restricted classes of parity games which are solvable in polynomial time include classes of bounded tree-width, bounded DAG-width, and bounded clique-width. We also prove that recognising the winning regions of a parity game is not easier than computing them from scratch.
Performance Measurement and Method Analysis (PMMA) for Fingerprint Reconstruction
Venue: arXiv cs.CV 2012
Year: 2012

Fingerprint reconstruction is one of the most well-known and publicized biometrics. Because of their uniqueness and consistency over time, fingerprints have been used for identification over a century, more recently becoming automated due to advancements in computed capabilities. Fingerprint reconstruction is popular because of the inherent ease of acquisition, the numerous sources (e.g. ten fingers) available for collection, and their established use and collections by law enforcement and immigration. Fingerprints have always been the most practical and positive means of identification. Offenders, being well aware of this, have been coming up with ways to escape identification by that means. Erasing left over fingerprints, using gloves, fingerprint forgery; are certain examples of methods tried by them, over the years. Failing to prevent themselves, they moved to an extent of mutilating their finger skin pattern, to remain unidentified. This article is based upon obliteration of finger ridge patterns and discusses some known cases in relation to the same, in chronological order; highlighting the reasons why offenders go to an extent of performing such act. The paper gives an overview of different methods and performance measurement of the fingerprint reconstruction.
Don't Be Strict in Local Search!
Venue: arXiv cs.DS 2012
Year: 2012

Local Search is one of the fundamental approaches to combinatorial optimization and it is used throughout AI. Several local search algorithms are based on searching the k-exchange neighborhood. This is the set of solutions that can be obtained from the current solution by exchanging at most k elements. As a rule of thumb, the larger k is, the better are the chances of finding an improved solution. However, for inputs of size n, a naïve brute-force search of the k-exchange neighborhood requires n to the power of O(k) time, which is not practical even for very small values of k. Fellows et al. (IJCAI 2009) studied whether this brute-force search is avoidable and gave positive and negative answers for several combinatorial problems. They used the notion of local search in a strict sense. That is, an improved solution needs to be found in the k-exchange neighborhood even if a global optimum can be found efficiently. In this paper we consider a natural relaxation of local search, called permissive local search (Marx and Schlotter, IWPEC 2009) and investigate whether it enhances the domain of tractable inputs. We exemplify this approach on a fundamental combinatorial problem, Vertex Cover. More precisely, we show that for a class of inputs, finding an optimum is hard, strict local search is hard, but permissive local search is tractable. We carry out this investigation in the framework of parameterized complexity.
RMR-Efficient Randomized Abortable Mutual Exclusion
Venue: arXiv cs.DC 2012
Year: 2012

Recent research on mutual exclusion for shared-memory systems has focused on "local spin" algorithms. Performance is measured using the "remote memory references" (RMRs) metric. As common in recent literature, we consider a standard asynchronous shared memory model with N processes, which allows atomic read, write and compare-and-swap (short: CAS) operations. In such a model, the asymptotically tight upper and lower bound on the number of RMRs per passage through the Critical Section is Theta(log N) for the optimal deterministic algorithms (see Yang and Anderson,1995, and Attiya, Hendler and Woelfel, 2008). Recently, several randomized algorithms have been devised that break the Omega(log N) barrier and need only o(log N) RMRs per passage in expectation (see Hendler and Woelfel, 2010, Hendler and Woelfel, 2011, and Bender and Gilbert, 2011). In this paper we present the first randomized "abortable" mutual exclusion algorithm that achieves a sub-logarithmic expected RMR complexity. More precisely, against a weak adversary (which can make scheduling decisions based on the entire past history, but not the latest coin-flips of each process) every process needs an expected number of O(log N/ log log N) RMRs to enter end exit the critical section. If a process receives an abort-signal, it can abort an attempt to enter the critical section within a finite number of its own steps and by incurring O(log N/ log log N) RMRs.
Semantic Web Techniques for Yellow Page Service Providers
Venue: arXiv cs.IR 2012
Year: 2012

Use of web pages providing unstructured information poses variety of problems to the user, such as use of arbitrary formats, unsuitability for machine processing and likely incompleteness of information. Structured data alleviates these problems but we require more. Very often yellow page systems are implemented using a centralized database. In some cases, human intermediaries accessible over the phone network examine a centralized database and use their reasoning ability to deal with the user's need for information. Scaling up such systems is difficult. This paper explores an alternative - a highly distributed system design meeting a variety of needs - considerably reducing efforts required at a central organization, enabling large numbers of vendors to enter information about their own products and services, enabling end-users to contribute information such as their own ratings, using an ontology to describe each domain of application in a flexible manner for uses foreseen and unforeseen, enabling distributed search and mash-ups, use of vendor independent standards, using reasoning to find the best matches to a given query, geo-spatial reasoning and a simple, interactive, mobile application/interface. We give importance to geo-spatial information and mobile applications because of the very wide-spread use of mobile phones and their inherent ability to provide some information about the current location of the user. We have created a prototype using the Jena Toolkit and geo-spatial extensions to SPARQL. We have tested this prototype by asking a group of typical users to use it and to provide structured feedback. We have summarized this feedback in the paper. We believe that the technology can be applied in many contexts in addition to yellow page systems.