OpenRaiser/Intern-Atlas huggingface dataset:
GRASP for the Coalition Structure Formation Problem
Venue: arXiv cs.AI 2010
Year: 2010

The coalition structure formation problem represents an active research area in multi-agent systems. A coalition structure is defined as a partition of the agents involved in a system into disjoint coalitions. The problem of finding the optimal coalition structure is NP-complete. In order to find the optimal solution in a combinatorial optimization problem it is theoretically possible to enumerate the solutions and evaluate each. But this approach is infeasible since the number of solutions often grows exponentially with the size of the problem. In this paper we present a greedy adaptive search procedure (GRASP) to efficiently search the space of coalition structures in order to find an optimal one. Experiments and comparisons to other algorithms prove the validity of the proposed method in solving this hard combinatorial problem.
Sparse Reconstruction via The Reed-Muller Sieve
Venue: arXiv cs.IT 2010
Year: 2010

This paper introduces the Reed Muller Sieve, a deterministic measurement matrix for compressed sensing. The columns of this matrix are obtained by exponentiating codewords in the quaternary second order Reed Muller code of length $N$. For $k=O(N)$, the Reed Muller Sieve improves upon prior methods for identifying the support of a $k$-sparse vector by removing the requirement that the signal entries be independent. The Sieve also enables local detection; an algorithm is presented with complexity $N^2 \log N$ that detects the presence or absence of a signal at any given position in the data domain without explicitly reconstructing the entire signal. Reconstruction is shown to be resilient to noise in both the measurement and data domains; the $\ell_2 / \ell_2$ error bounds derived in this paper are tighter than the $\ell_2 / \ell_1$ bounds arising from random ensembles and the $\ell_1 /\ell_1$ bounds arising from expander-based ensembles.
Accountable Anonymous Group Messaging
Venue: arXiv cs.CR 2010
Year: 2010

Users often wish to participate in online groups anonymously, but misbehaving users may abuse this anonymity to spam or disrupt the group. Messaging protocols such as Mix-nets and DC-nets leave online groups vulnerable to denial-of-service and Sybil attacks, while accountable voting protocols are unusable or inefficient for general anonymous messaging. We present the first general messaging protocol that offers provable anonymity with accountability for moderate-size groups, and efficiently handles unbalanced loads where few members have much data to transmit in a given round. The N group members first cooperatively shuffle an NxN matrix of pseudorandom seeds, then use these seeds in N "pre-planned" DC-nets protocol runs. Each DC-nets run transmits the variable-length bulk data comprising one member's message, using the minimum number of bits required for anonymity under our attack model. The protocol preserves message integrity and one-to-one correspondence between members and messages, makes denial-of-service attacks by members traceable to the culprit, and efficiently handles large and unbalanced message loads. A working prototype demonstrates the protocol's practicality for anonymous messaging in groups of 40+ member nodes.
Genetic Algorithms for Multiple-Choice Problems
Venue: arXiv cs.NE 2010
Year: 2010

This thesis investigates the use of problem-specific knowledge to enhance a genetic algorithm approach to multiple-choice optimisation problems.It shows that such information can significantly enhance performance, but that the choice of information and the way it is included are important factors for success.Two multiple-choice problems are considered.The first is constructing a feasible nurse roster that considers as many requests as possible.In the second problem, shops are allocated to locations in a mall subject to constraints and maximising the overall income.Genetic algorithms are chosen for their well-known robustness and ability to solve large and complex discrete optimisation problems.However, a survey of the literature reveals room for further research into generic ways to include constraints into a genetic algorithm framework.Hence, the main theme of this work is to balance feasibility and cost of solutions.In particular, co-operative co-evolution with hierarchical sub-populations, problem structure exploiting repair schemes and indirect genetic algorithms with self-adjusting decoder functions are identified as promising approaches.The research starts by applying standard genetic algorithms to the problems and explaining the failure of such approaches due to epistasis.To overcome this, problem-specific information is added in a variety of ways, some of which are designed to increase the number of feasible solutions found whilst others are intended to improve the quality of such solutions.As well as a theoretical discussion as to the underlying reasons for using each operator,extensive computational experiments are carried out on a variety of data.These show that the indirect approach relies less on problem structure and hence is easier to implement and superior in solution quality.
Automatic Mapping Tasks to Cores - Evaluating AMTHA Algorithm in Multicore Architectures
Venue: arXiv cs.PF 2010
Year: 2010

The AMTHA (Automatic Mapping Task on Heterogeneous Architectures) algorithm for task-to-processors assignment and the MPAHA (Model of Parallel Algorithms on Heterogeneous Architectures) model are presented. The use of AMTHA is analyzed for multicore processor-based architectures, considering the communication model among processes in use. The results obtained in the tests carried out are presented, comparing the real execution times on multicores of a set of synthetic applications with the predictions obtained with AMTHA. Finally current lines of research are presented, focusing on clusters of multicores and hybrid programming paradigms.
DBSR: Dynamic base station Repositioning using Genetic algorithm in wireless sensor network
Venue: arXiv cs.NI 2010
Year: 2010

Wireless sensor networks (WSNs) are commonly used in various ubiquitous and pervasive applications. Due to limited power resources, the optimal dynamic base station (BS) replacement could be Prolong the sensor network lifetime. In this paper we'll present a dynamic optimum method for base station replacement so that can save energy in sensors and increases network lifetime. Because positioning problem is a NPhard problem [1], therefore we'll use genetic algorithm to solve positioning problem. We've considered energy and distance parameters for finding BS optimized position. In our represented algorithm base station position is fixed just during each round and its positioning is done at the start of next round then it'll be placed in optimized position. Evaluating our proposed algorithm, we'll execute DBSR algorithm on LEACH & HEED Protocols.
A General Simulation Framework for Supply Chain Modeling: State of the Art and Case Study
Venue: arXiv cs.OH 2010
Year: 2010

Nowadays there is a large availability of discrete event simulation software that can be easily used in different domains: from industry to supply chain, from healthcare to business management, from training to complex systems design. Simulation engines of commercial discrete event simulation software use specific rules and logics for simulation time and events management. Difficulties and limitations come up when commercial discrete event simulation software are used for modeling complex real world-systems (i.e. supply chains, industrial plants). The objective of this paper is twofold: first a state of the art on commercial discrete event simulation software and an overview on discrete event simulation models development by using general purpose programming languages are presented; then a Supply Chain Order Performance Simulator (SCOPS, developed in C++) for investigating the inventory management problem along the supply chain under different supply chain scenarios is proposed to readers.
Database Reverse Engineering based on Association Rule Mining
Venue: arXiv cs.DB 2010
Year: 2010

Maintaining a legacy database is a difficult task especially when system documentation is poor written or even missing. Database reverse engineering is an attempt to recover high-level conceptual design from the existing database instances. In this paper, we propose a technique to discover conceptual schema using the association mining technique. The discovered schema corresponds to the normalization at the third normal form, which is a common practice in many business organizations. Our algorithm also includes the rule filtering heuristic to solve the problem of exponential growth of discovered rules inherited with the association mining technique.
Estimation in Gaussian Noise: Properties of the Minimum Mean-Square Error
Venue: arXiv cs.IT 2010
Year: 2010

Consider the minimum mean-square error (MMSE) of estimating an arbitrary random variable from its observation contaminated by Gaussian noise. The MMSE can be regarded as a function of the signal-to-noise ratio (SNR) as well as a functional of the input distribution (of the random variable to be estimated). It is shown that the MMSE is concave in the input distribution at any given SNR. For a given input distribution, the MMSE is found to be infinitely differentiable at all positive SNR, and in fact a real analytic function in SNR under mild conditions. The key to these regularity results is that the posterior distribution conditioned on the observation through Gaussian channels always decays at least as quickly as some Gaussian density. Furthermore, simple expressions for the first three derivatives of the MMSE with respect to the SNR are obtained. It is also shown that, as functions of the SNR, the curves for the MMSE of a Gaussian input and that of a non-Gaussian input cross at most once over all SNRs. These properties lead to simple proofs of the facts that Gaussian inputs achieve both the secrecy capacity of scalar Gaussian wiretap channels and the capacity of scalar Gaussian broadcast channels, as well as a simple proof of the entropy power inequality in the special case where one of the variables is Gaussian.
Faster Approximation Schemes and Parameterized Algorithms on H-Minor-Free and Odd-Minor-Free Graphs
Venue: arXiv cs.DS 2010
Year: 2010

We improve the running time of the general algorithmic technique known as Baker's approach (1994) on H-minor-free graphs from O(n^{f(|H|)}) to O(f(|H|) n^{O(1)}). The numerous applications include e.g. a 2-approximation for coloring and PTASes for various problems such as dominating set and max-cut, where we obtain similar improvements. On classes of odd-minor-free graphs, which have gained significant attention in recent time, we obtain a similar acceleration for a variant of the structural decomposition theorem proved by Demaine et al. (2010). We use these algorithms to derive faster 2-approximations; furthermore, we present the first PTASes and subexponential FPT-algorithms for independent set and vertex cover on these graph classes using a novel dynamic programming technique. We also introduce a technique to derive (nearly) subexponential parameterized algorithms on H-minor-free graphs. Our technique applies, in particular, to problems such as Steiner tree, (directed) subgraph with a property, (directed) longest path, and (connected/independent) dominating set, on some or all proper minor-closed graph classes. We obtain as a corollary that all problems with a minor-monotone subexponential kernel and amenable to our technique can be solved in subexponential FPT-time on H-minor free graphs. This results in a general methodology for subexponential parameterized algorithms outside the framework of bidimensionality.
Control Complexity in Fallback Voting
Venue: arXiv cs.GT 2010
Year: 2010

We study the control complexity of fallback voting. Like manipulation and bribery, electoral control describes ways of changing the outcome of an election; unlike manipulation or bribery attempts, control actions---such as adding/deleting/partitioning either candidates or voters---modify the participative structure of an election. Via such actions one can try to either make a favorite candidate win ("constructive control") or prevent a despised candidate from winning ("destructive control"). Computational complexity can be used to protect elections from control attempts, i.e., proving an election system resistant to some type of control shows that the success of the corresponding control action, though not impossible, is computationally prohibitive. We show that fallback voting, an election system combining approval with majority voting, is resistant to each of the common types of candidate control and to each common type of constructive control. Among natural election systems with a polynomial-time winner problem, only plurality and sincere-strategy preference-based approval voting (SP-AV) were previously known to be fully resistant to candidate control, and only Copeland voting and SP-AV were previously known to be fully resistant to constructive control. However, plurality has fewer resistances to voter control, Copeland voting has fewer resistances to destructive control, and SP-AV (which like fallback voting has 19 out of 22 proven control resistances) is arguably less natural a system than fallback voting.
On Asymptotic Consensus Value in Directed Random Networks
Venue: arXiv cs.MA 2010
Year: 2010

We study the asymptotic properties of distributed consensus algorithms over switching directed random networks. More specifically, we focus on consensus algorithms over independent and identically distributed, directed random graphs, where each agent can communicate with any other agent with some exogenously specified probability. While different aspects of consensus algorithms over random switching networks have been widely studied, a complete characterization of the distribution of the asymptotic value for general \textit{asymmetric} random consensus algorithms remains an open problem. In this paper, we derive closed-form expressions for the mean and an upper bound for the variance of the asymptotic consensus value, when the underlying network evolves according to an i.i.d. \textit{directed} random graph process. We also provide numerical simulations that illustrate our results.
Neuroevolutionary optimization
Venue: arXiv cs.NE 2010
Year: 2010

This paper presents an application of evolutionary search procedures to artificial neural networks. Here, we can distinguish among three kinds of evolution in artificial neural networks, i.e. the evolution of connection weights, of architectures, and of learning rules. We review each kind of evolution in detail and analyse critical issues related to different evolutions. This article concentrates on finding the suitable way of using evolutionary algorithms for optimizing the artificial neural network parameters.
Scheduling Multi-Mode Real-Time Systems upon Uniform Multiprocessor Platforms
Venue: arXiv cs.OS 2010
Year: 2010

In this paper, we address the scheduling problem of multi-mode real-time systems upon uniform multiprocessor platforms. We propose two transition protocols, specified together with their schedulability test, and provide the reader with two distinct upper bounds for the length of the transient phases during mode transitions, respectively for the cases where jobs priorities are known and unknown beforehand.
Parcellation of fMRI Datasets with ICA and PLS-A Data Driven Approach
Venue: arXiv cs.CV 2010
Year: 2010

Inter-subject parcellation of functional Magnetic Resonance Imaging (fMRI) data based on a standard General Linear Model (GLM)and spectral clustering was recently proposed as a means to alleviate the issues associated with spatial normalization in fMRI. However, for all its appeal, a GLM-based parcellation approach introduces its own biases, in the form of a priori knowledge about the shape of Hemodynamic Response Function (HRF) and task-related signal changes, or about the subject behaviour during the task. In this paper, we introduce a data-driven version of the spectral clustering parcellation, based on Independent Component Analysis (ICA) and Partial Least Squares (PLS) instead of the GLM. First, a number of independent components are automatically selected. Seed voxels are then obtained from the associated ICA maps and we compute the PLS latent variables between the fMRI signal of the seed voxels (which covers regional variations of the HRF) and the principal components of the signal across all voxels. Finally, we parcellate all subjects data with a spectral clustering of the PLS latent variables. We present results of the application of the proposed method on both single-subject and multi-subject fMRI datasets. Preliminary experimental results, evaluated with intra-parcel variance of GLM t-values and PLS derived t-values, indicate that this data-driven approach offers improvement in terms of parcellation accuracy over GLM based techniques.
Some linear-time algorithms for systolic arrays
Venue: arXiv cs.DS 2010
Year: 2010

We survey some results on linear-time algorithms for systolic arrays. In particular, we show how the greatest common divisor (GCD) of two polynomials of degree n over a finite field can be computed in time O(n) on a linear systolic array of O(n) cells; similarly for the GCD of two n-bit binary numbers. We show how n * n Toeplitz systems of linear equations can be solved in time O(n) on a linear array of O(n) cells, each of which has constant memory size (independent of n). Finally, we outline how a two-dimensional square array of O(n)* O(n) cells can be used to solve (to working accuracy) the eigenvalue problem for a symmetric real n* n matrix in time O(nS(n)). Here S(n) is a slowly growing function of n; for practical purposes S(n) can be regarded as a constant. In addition to their theoretical interest, these results have potential applications in the areas of error-correcting codes, symbolic and algebraic computations, signal processing and image processing.
Solving the Cold-Start Problem in Recommender Systems with Social Tags
Venue: arXiv cs.IR 2010
Year: 2010

In this paper, based on the user-tag-object tripartite graphs, we propose a recommendation algorithm, which considers social tags as an important role for information retrieval. Besides its low cost of computational time, the experiment results of two real-world data sets, \emph{Del.icio.us} and \emph{MovieLens}, show it can enhance the algorithmic accuracy and diversity. Especially, it can obtain more personalized recommendation results when users have diverse topics of tags. In addition, the numerical results on the dependence of algorithmic accuracy indicates that the proposed algorithm is particularly effective for small degree objects, which reminds us of the well-known \emph{cold-start} problem in recommender systems. Further empirical study shows that the proposed algorithm can significantly solve this problem in social tagging systems with heterogeneous object degree distributions.
The SIMO Pre-Log Can Be Larger Than the SISO Pre-Log
Venue: arXiv cs.IT 2010
Year: 2010

We establish a lower bound on the noncoherent capacity pre-log of a temporally correlated Rayleigh block-fading single-input multiple-output (SIMO) channel. Surprisingly, when the covariance matrix of the channel satisfies a certain technical condition related to the cardinality of its smallest set of linearly dependent rows, this lower bound reveals that the capacity pre-log in the SIMO case is larger than that in the single-input single-output (SISO) case.
Pythagorean Triples and Cryptographic Coding
Venue: arXiv cs.CR 2010
Year: 2010

This paper summarizes basic properties of PPTs and shows that each PPT belongs to one of six different classes. Mapping an ordered sequence of PPTs into a corresponding sequence of these six classes makes it possible to use them in cryptography. We pose problems whose solution would facilitate such cryptographic application.
Bregman Distance to L1 Regularized Logistic Regression
Venue: arXiv cs.LG 2010
Year: 2010

In this work we investigate the relationship between Bregman distances and regularized Logistic Regression model. We present a detailed study of Bregman Distance minimization, a family of generalized entropy measures associated with convex functions. We convert the L1-regularized logistic regression into this more general framework and propose a primal-dual method based algorithm for learning the parameters. We pose L1-regularized logistic regression into Bregman distance minimization and then apply non-linear constrained optimization techniques to estimate the parameters of the logistic model.
A Study of Medium Access Control Protocols for Wireless Body Area Networks
Venue: arXiv cs.NI 2010
Year: 2010

The seamless integration of low-power, miniaturised, invasive/non-invasive lightweight sensor nodes have contributed to the development of a proactive and unobtrusive Wireless Body Area Network (WBAN). A WBAN provides long-term health monitoring of a patient without any constraint on his/her normal dailylife activities. This monitoring requires low-power operation of invasive/non-invasive sensor nodes. In other words, a power-efficient Medium Access Control (MAC) protocol is required to satisfy the stringent WBAN requirements including low-power consumption. In this paper, we first outline the WBAN requirements that are important for the design of a low-power MAC protocol. Then we study low-power MAC protocols proposed/investigated for WBAN with emphasis on their strengths and weaknesses. We also review different power-efficient mechanisms for WBAN. In addition, useful suggestions are given to help the MAC designers to develop a low-power MAC protocol that will satisfy the stringent WBAN requirements.
Performance Evaluation of DCA and SRC on a Single Bot Detection
Venue: arXiv cs.AI 2010
Year: 2010

Malicious users try to compromise systems using new techniques. One of the recent techniques used by the attacker is to perform complex distributed attacks such as denial of service and to obtain sensitive data such as password information. These compromised machines are said to be infected with malicious software termed a "bot". In this paper, we investigate the correlation of behavioural attributes such as keylogging and packet flooding behaviour to detect the existence of a single bot on a compromised machine by applying (1) Spearman's rank correlation (SRC) algorithm and (2) the Dendritic Cell Algorithm (DCA). We also compare the output results generated from these two methods to the detection of a single bot. The results show that the DCA has a better performance in detecting malicious activities.
Secrecy Gain: a Wiretap Lattice Code Design
Venue: arXiv cs.IT 2010
Year: 2010

We propose the notion of secrecy gain as a code design criterion for wiretap lattice codes to be used over an additive white Gaussian noise channel. Our analysis relies on the error probabilites of both the legitimate user and the eavesdropper. We focus on geometrical properties of lattices, described by their theta series, to characterize good wiretap codes.
Real-Time Alert Correlation with Type Graphs
Venue: arXiv cs.AI 2010
Year: 2010

The premise of automated alert correlation is to accept that false alerts from a low level intrusion detection system are inevitable and use attack models to explain the output in an understandable way. Several algorithms exist for this purpose which use attack graphs to model the ways in which attacks can be combined. These algorithms can be classified in to two broad categories namely scenario-graph approaches, which create an attack model starting from a vulnerability assessment and type-graph approaches which rely on an abstract model of the relations between attack types. Some research in to improving the efficiency of type-graph correlation has been carried out but this research has ignored the hypothesizing of missing alerts. Our work is to present a novel type-graph algorithm which unifies correlation and hypothesizing in to a single operation. Our experimental results indicate that the approach is extremely efficient in the face of intensive alerts and produces compact output graphs comparable to other techniques.