OpenRaiser/Intern-Atlas huggingface dataset:
Algorithms for the Problems of Length-Constrained Heaviest Segments
Venue: arXiv cs.CG 2011
Year: 2011

We present algorithms for length-constrained maximum sum segment and maximum density segment problems, in particular, and the problem of finding length-constrained heaviest segments, in general, for a sequence of real numbers. Given a sequence of n real numbers and two real parameters L and U (L <= U), the maximum sum segment problem is to find a consecutive subsequence, called a segment, of length at least L and at most U such that the sum of the numbers in the subsequence is maximum. The maximum density segment problem is to find a segment of length at least L and at most U such that the density of the numbers in the subsequence is the maximum. For the first problem with non-uniform width there is an algorithm with time and space complexities in O(n). We present an algorithm with time complexity in O(n) and space complexity in O(U). For the second problem with non-uniform width there is a combinatorial solution with time complexity in O(n) and space complexity in O(U). We present a simple geometric algorithm with the same time and space complexities. We extend our algorithms to respectively solve the length-constrained k maximum sum segments problem in O(n+k) time and O(max{U, k}) space, and the length-constrained $k$ maximum density segments problem in O(n min{k, U-L}) time and O(U+k) space. We present extensions of our algorithms to find all the length-constrained segments having user specified sum and density in O(n+m) and O(nlog (U-L)+m) times respectively, where m is the number of output. Previously, there was no known algorithm with non-trivial result for these problems. We indicate the extensions of our algorithms to higher dimensions. All the algorithms can be extended in a straight forward way to solve the problems with non-uniform width and non-uniform weight.
Event in Compositional Dynamic Semantics
Venue: arXiv cs.CL 2011
Year: 2011

We present a framework which constructs an event-style dis- course semantics. The discourse dynamics are encoded in continuation semantics and various rhetorical relations are embedded in the resulting interpretation of the framework. We assume discourse and sentence are distinct semantic objects, that play different roles in meaning evalua- tion. Moreover, two sets of composition functions, for handling different discourse relations, are introduced. The paper first gives the necessary background and motivation for event and dynamic semantics, then the framework with detailed examples will be introduced.
Orthonormal Expansion l1-Minimization Algorithms for Compressed Sensing
Venue: arXiv cs.IT 2011
Year: 2011

Compressed sensing aims at reconstructing sparse signals from significantly reduced number of samples, and a popular reconstruction approach is $\ell_1$-norm minimization. In this correspondence, a method called orthonormal expansion is presented to reformulate the basis pursuit problem for noiseless compressed sensing. Two algorithms are proposed based on convex optimization: one exactly solves the problem and the other is a relaxed version of the first one. The latter can be considered as a modified iterative soft thresholding algorithm and is easy to implement. Numerical simulation shows that, in dealing with noise-free measurements of sparse signals, the relaxed version is accurate, fast and competitive to the recent state-of-the-art algorithms. Its practical application is demonstrated in a more general case where signals of interest are approximately sparse and measurements are contaminated with noise.
New Results on the Fault-Tolerant Facility Placement Problem
Venue: arXiv cs.DS 2011
Year: 2011

We studied the Fault-Tolerant Facility Placement problem (FTFP) which generalizes the uncapacitated facility location problem (UFL). In FTFP, we are given a set F of sites at which facilities can be built, and a set C of clients with some demands that need to be satisfied by different facilities. A client $j$ has demand $r_j$. Building one facility at a site $i$ incurs a cost $f_i$, and connecting one unit of demand from client $j$ to a facility at site $i\in\fac$ costs $d_{ij}$. $d_{ij}$'s are assumed to form a metric. A feasible solution specifies the number of facilities to be built at each site and the way to connect demands from clients to facilities, with the restriction that demands from the same client must go to different facilities. Facilities at the same site are considered different. The goal is to find a solution with minimum total cost. We gave a 1.7245-approximation algorithm to the FTFP problem. Our technique is via a reduction to the Fault-Tolerant Facility Location problem, in which each client has demand $r_j$ but each site can have at most one facility built.
An Anti-attack Model Based on Complex Network Theory in P2P networks
Venue: arXiv cs.NI 2011
Year: 2011

Complex network theory is a useful way to study many real systems. In this paper, an anti-attack model based on complex network theory is introduced. The mechanism of this model is based on dynamic compensation process and reverse percolation process in P2P networks. The main purpose of the paper is: (i) a dynamic compensation process can turn an attacked P2P network into a power-law (PL) network with exponential cutoff; (ii) a local healing process can restore the maximum degree of peers in an attacked P2P network to a normal level; (iii) a restoring process based on reverse percolation theory connects the fragmentary peers of an attacked P2P network together into a giant connected component. In this way, the model based on complex network theory can be effectively utilized for anti-attack and protection purposes in P2P networks.
Multi-Robot Organisms: State of the Art
Venue: arXiv cs.RO 2011
Year: 2011

This paper represents the state of the art development on the field of artificial multi-robot organisms. It briefly considers mechatronic development, sensor and computational equipment, software framework and introduces one of the Grand Challenges for swarm and reconfigurable robotics.
Multi-Robot Searching Algorithm Using Levy Flight and Artificial Potential Field
Venue: arXiv cs.RO 2011
Year: 2011

An efficient search algorithm is very crucial in robotic area, especially for exploration missions, where the target availability is unknown and the condition of the environment is highly unpredictable. In a very large environment, it is not sufficient to scan an area or volume by a single robot, multiple robots should be involved to perform the collective exploration. In this paper, we propose to combine bio-inspired search algorithm called Levy flight and artificial potential field method to perform an efficient searching algorithm for multi-robot applications. The main focus of this work is not only to prove the concept or to measure the efficiency of the algorithm by experiments, but also to develop an appropriate generic framework to be implemented both in simulation and on real robotic platforms. Several experiments, which compare different search algorithms, are also performed.
Collective Adaptive Systems: Challenges Beyond Evolvability
Venue: arXiv cs.ET 2011
Year: 2011

This position paper overviews several challenges of collective adaptive systems, which are beyond the research objectives of current top-projects in ICT, and especially in FET, initiatives. The attention is paid not only to challenges and new research topics, but also to their impact and potential breakthroughs in information and communication technologies.
Sliding Trellis-Based Frame Synchronization
Venue: arXiv cs.NI 2011
Year: 2011

Frame Synchronization (FS) is required in several communication standards in order to recover the individual frames that have been aggregated in a burst. This paper proposes a low-delay and reducedcomplexity Sliding Trellis (ST)-based FS technique, compared to our previously proposed trellis-based FS method. Each burst is divided into overlapping windows in which FS is performed. Useful information is propagated from one window to the next. The proposed method makes use of soft information provided by the channel, but also of all sources of redundancy present in the protocol stack. An illustration of our STbased approach for the WiMAX Media Access Control (MAC) layer is provided. When FS is performed on bursts transmitted over Rayleigh fading channel, the ST-based approach reduces the FS latency and complexity at the cost of a very small performance degradation compared to our full complexity trellis-based FS and outperforms state-of-the-art FS techniques.
Structure Selection from Streaming Relational Data
Venue: arXiv cs.AI 2011
Year: 2011

Statistical relational learning techniques have been successfully applied in a wide range of relational domains. In most of these applications, the human designers capitalized on their background knowledge by following a trial-and-error trajectory, where relational features are manually defined by a human engineer, parameters are learned for those features on the training data, the resulting model is validated, and the cycle repeats as the engineer adjusts the set of features. This paper seeks to streamline application development in large relational domains by introducing a light-weight approach that efficiently evaluates relational features on pieces of the relational graph that are streamed to it one at a time. We evaluate our approach on two social media tasks and demonstrate that it leads to more accurate models that are learned faster.
Conjugate Variables as a Resource in Signal and Image Processing
Venue: arXiv cs.CV 2011
Year: 2011

In this paper we develop a new technique to model joint distributions of signals. Our technique is based on quantum mechanical conjugate variables. We show that the transition probability of quantum states leads to a distance function on the signals. This distance function obeys the triangle inequality on all quantum states and becomes a metric on pure quantum states. Treating signals as conjugate variables allows us to create a new approach to segment them. Keywords: Quantum information, transition probability, Euclidean distance, Fubini-study metric, Bhattacharyya coefficients, conjugate variable, signal/sensor fusion, signal and image segmentation.
Optimal k-fold colorings of webs and antiwebs
Venue: arXiv cs.DM 2011
Year: 2011

A k-fold x-coloring of a graph is an assignment of (at least) k distinct colors from the set {1, 2, ..., x} to each vertex such that any two adjacent vertices are assigned disjoint sets of colors. The smallest number x such that G admits a k-fold x-coloring is the k-th chromatic number of G, denoted by χ_k(G). We determine the exact value of this parameter when G is a web or an antiweb. Our results generalize the known corresponding results for odd cycles and imply necessary and sufficient conditions under which χ_k(G) attains its lower and upper bounds based on the clique, the fractional chromatic and the chromatic numbers. Additionally, we extend the concept of χ-critical graphs to χ_k-critical graphs. We identify the webs and antiwebs having this property, for every integer k <= 1.
Each normal logic program has a 2-valued Minimal Hypotheses semantics
Venue: arXiv cs.LO 2011
Year: 2011

In this paper we explore a unifying approach --- that of hypotheses assumption --- as a means to provide a semantics for all Normal Logic Programs (NLPs), the Minimal Hypotheses (MH) semantics. This semantics takes a positive hypotheses assumption approach as a means to guarantee the desirable properties of model existence, relevance and cumulativity, and of generalizing the Stable Models in the process. To do so we first introduce the fundamental semantic concept of minimality of assumed positive hypotheses, define the MH semantics, and analyze the semantics' properties and applicability. Indeed, abductive Logic Programming can be conceptually captured by a strategy centered on the assumption of abducibles (or hypotheses). Likewise, the Argumentation perspective of Logic Programs also lends itself to an arguments (or hypotheses) assumption approach. Previous works on Abduction have depicted the atoms of default negated literals in NLPs as abducibles, i.e., assumable hypotheses. We take a complementary and more general view than these works to NLP semantics by employing positive hypotheses instead.
Food Redistribution as Optimization
Venue: arXiv cs.OH 2011
Year: 2011

In this paper we study the simultaneous problems of food waste and hunger in the context of the possible solution of food (waste) rescue and redistribution. To this end, we develop an empirical model that can be used in Monte Carlo simulations to study the dynamics of the underlying problem. Our model's parameters are derived from a unique data set provided by a large food bank and food rescue organization in north central Colorado. We find that food supply is a non-parametric heavy-tailed process that is well-modeled with an extreme value peaks-over-threshold model. Although the underlying process is stochastic, the basic approach of food rescue and redistribution appears to be feasible both at small and large scales. The ultimate efficacy of this model is intimately tied to the rate at which food expires and hence the ability to preserve and quickly transport and redistribute food. The cost of the redistribution is tied to the number and density of participating suppliers, and costs can be reduced (and supply increased) simply by recruiting additional donors to participate. Our results show that with sufficient funding and manpower, a significant amount of food can be rescued from the waste stream and used to feed the hungry.
Confidentiality-Preserving Data Publishing for Credulous Users by Extended Abduction
Venue: arXiv cs.AI 2011
Year: 2011

Publishing private data on external servers incurs the problem of how to avoid unwanted disclosure of confidential data. We study a problem of confidentiality in extended disjunctive logic programs and show how it can be solved by extended abduction. In particular, we analyze how credulous non-monotonic reasoning affects confidentiality.
Information Dissemination in Unknown Radio networks with Large Labels
Venue: arXiv cs.DC 2011
Year: 2011

We consider the problems of deterministic broadcasting and gossiping in completely unknown ad-hoc radio networks. We assume that nothing is known to the nodes about the topology or even the size of the network, $n$, except that $n > 1$. Protocols for vanilla model, when $n$ is known, may be run for increasingly larger estimates $2^i$ on the size of the network, but one cannot determine when such a protocol should terminate. Thus, to carry this design paradigm, successful completion or in-completion of the process should be detected, and this knowledge circulated in the network. We consider the problem of deterministic Acknowledged Broadcasting and Gossiping when nodes can take polynomially large labels. For the above setting, we present the following results for strongly connected networks: (a) A deterministic protocol for acknowledged broadcasting which takes $NRG(n,n^c)$ rounds, where $NRG(n,n^c)$ is the round complexity of deterministic gossiping for vanilla model. (b) A deterministic protocol for acknowledged gossiping, which takes $O(n^2 \lg n)$ rounds when collision detection mechanism is available. The structure of the transmissions of nodes in the network, to enable them to infer collisions, and discover existence of unknown in-neighborhood as a result, is abstracted as a family of integral sets called Selecting-Colliding family. We prove the existence of Selecting-Colliding families using the probabilistic method and employ them to design protocol for acknowledged gossiping when no collision detection mechanism is available. Finally, we present a deterministic protocol for acknowledged broadcasting for bidirectional networks, with a round complexity of $O(n \lg n)$ rounds.
Emotional Analysis of Blogs and Forums Data
Venue: arXiv cs.CL 2011
Year: 2011

We perform a statistical analysis of emotionally annotated comments in two large online datasets, examining chains of consecutive posts in the discussions. Using comparisons with randomised data we show that there is a high level of correlation for the emotional content of messages.
A State-of-the-art Survey on IDS for Mobile Ad-Hoc Networks and Wireless Mesh Networks
Venue: arXiv cs.CR 2011
Year: 2011

An Intrusion Detection System (IDS) detects malicious and selfish nodes in a network. Ad hoc networks are often secured by using either intrusion detection or by secure routing. Designing efficient IDS for wireless ad-hoc networks that would not affect the performance of the network significantly is indeed a challenging task. Arguably, the most common thing in a review paper in the domain of wireless networks is to compare the performances of different solutions using simulation results. However, variance in multiple configuration aspects including that due to different underlying routing protocols, makes the task of simulation based comparative evaluation of IDS solutions somewhat unrealistic. In stead, the authors have followed an analytic approach to identify the gaps in the existing IDS solutions for MANETs and wireless mesh networks. The paper aims to ease the job of a new researcher by exposing him to the state of the art research issues on IDS. Nearly 80% of the works cited in this paper are published with in last 3 to 4 years.
Statistical Model of Downlink Power Consumption in Cellular CDMA Networks
Venue: arXiv cs.SY 2011
Year: 2011

Present work proposes a theoretical statistical model of the downlink power consumption in cellular CDMA networks. The proposed model employs a simple but popular propagation model, which breaks down path losses into a distance dependent and a log-normal shadowing loss term. Based on the aforementioned path loss formalism, closed-form expressions for the first and the second moment of power consumption are obtained taking into account conditions placed by cell selection and handoff algorithms. Numerical results for various radio propagation environments and cell selection as well as handoff schemes are provided and discussed.
Complexity
Venue: arXiv cs.OH 2011
Year: 2011

The term complexity derives etymologically from the Latin plexus, which means interwoven. Intuitively, this implies that something complex is composed by elements that are difficult to separate. This difficulty arises from the relevant interactions that take place between components. This lack of separability is at odds with the classical scientific method - which has been used since the times of Galileo, Newton, Descartes, and Laplace - and has also influenced philosophy and engineering. In recent decades, the scientific study of complexity and complex systems has proposed a paradigm shift in science and philosophy, proposing novel methods that take into account relevant interactions.
Smart Radio Spectrum Management for Cognitive Radio
Venue: arXiv cs.NI 2011
Year: 2011

Today's wireless networks are characterized by fixed spectrum assignment policy. The limited available spectrum and the inefficiency in the spectrum usage necessitate a new communication paradigm to exploit the existing wireless spectrum opportunistically. Cognitive radio is a paradigm for wireless communication in which either a network or a wireless node changes its transmission or reception parameters to communicate efficiently avoiding interference with licensed or unlicensed users. In this work, a fuzzy logic based system for spectrum management is proposed where the radio can share unused spectrum depending on some parameters like distance, signal strength, node velocity and availability of unused spectrum. The system is simulated and is found to give satisfactory results.
Anonymity and verifiability in multi-attribute reverse auction
Venue: arXiv cs.CR 2011
Year: 2011

The use of e-Auction services has been increasing in recent years. Security requirements in conducting e-Auctions are mainly bid privacy, anonymity and public verifiability. Most of the secure protocols concentrate on privacy and anonymity, which are achieved through bidder-resolved multi-party computation, assuming two or more trusted third parties, either through numerous auctioneers or with asymmetric models in which the commercial entity of an auction issuer or registration manager is assumed in addition to the auctioneer. Multi-attribute reverse auctions promise higher market efficiency and effective information exchange. This work extends and uses the existing schemes. This scheme uses scoring function, winner determination in multi-attribute auctions to implement public verifiability. Anonymity is achieved through bidder side pseudonym generation. By results and analysis we say this is very simple and effective scheme. This scheme ensures public verifiability and anonymity in multi-attribute auctions without revelation of the bids received, third parties and complex communications.
Solving Modular Model Expansion Tasks
Venue: arXiv cs.LO 2011
Year: 2011

The work we describe here is a part of a research program of developing foundations of declarative solving of search problems. We consider the model expansion task as the task representing the essence of search problems where we are given an instance of a problem and are searching for a solution satisfying certain properties. Such tasks are common in artificial intelligence, formal verification, computational biology. Recently, the model expansion framework was extended to deal with multiple modules. In the current paper, inspired by practical combined solvers, we introduce an algorithm to solve model expansion tasks for modular systems. We show that our algorithm closely corresponds to what is done in practice in different areas such as Satisfiability Modulo Theories (SMT), Integer Linear Programming (ILP), Answer Set Programming (ASP).
Application of distributed constraint satisfaction problem to the agent-based planning in manufacturing systems
Venue: arXiv cs.MA 2011
Year: 2011

Nowadays, a globalization of national markets requires developing flexible and demand-driven production systems. Agent-based technology, being distributed, flexible and autonomous is expected to provide a short-time reaction to disturbances and sudden changes of environment and allows satisfying the mentioned requirements. The distributed constraint satisfaction approach underlying the suggested method is described by a modified Petri network providing both the conceptual notions and main details of implementation.
Visual Inference Specification Methods for Modularized Rulebases. Overview and Integration Proposal
Venue: arXiv cs.AI 2011
Year: 2011

The paper concerns selected rule modularization techniques. Three visual methods for inference specification for modularized rule- bases are described: Drools Flow, BPMN and XTT2. Drools Flow is a popular technology for workflow or process modeling, BPMN is an OMG standard for modeling business processes, and XTT2 is a hierarchical tab- ular system specification method. Because of some limitations of these solutions, several proposals of their integration are given.
Building Ontologies to Understand Spoken Tunisian Dialect
Venue: arXiv cs.CL 2011
Year: 2011

This paper presents a method to understand spoken Tunisian dialect based on lexical semantic. This method takes into account the specificity of the Tunisian dialect which has no linguistic processing tools. This method is ontology-based which allows exploiting the ontological concepts for semantic annotation and ontological relations for speech interpretation. This combination increases the rate of comprehension and limits the dependence on linguistic resources. This paper also details the process of building the ontology used for annotation and interpretation of Tunisian dialect in the context of speech understanding in dialogue systems for restricted domain.