OpenRaiser/Intern-Atlas huggingface dataset:
A Bayesian Optimisation Algorithm for the Nurse Scheduling Problem
Venue: arXiv cs.NE 2008
Year: 2008

A Bayesian optimization algorithm for the nurse scheduling problem is presented, which involves choosing a suitable scheduling rule from a set for each nurses assignment. Unlike our previous work that used Gas to implement implicit learning, the learning in the proposed algorithm is explicit, ie. Eventually, we will be able to identify and mix building blocks directly. The Bayesian optimization algorithm is applied to implement such explicit learning by building a Bayesian network of the joint distribution of solutions. The conditional probability of each variable in the network is computed according to an initial set of promising solutions. Subsequently, each new instance for each variable is generated, ie in our case, a new rule string has been obtained. Another set of rule strings will be generated in this way, some of which will replace previous strings based on fitness selection. If stopping conditions are not met, the conditional probabilities for all nodes in the Bayesian network are updated again using the current set of promising rule strings. Computational results from 52 real data instances demonstrate the success of this approach. It is also suggested that the learning mechanism in the proposed approach might be suitable for other scheduling problems.
New Upper Bounds on Sizes of Permutation Arrays
Venue: arXiv cs.IT 2008
Year: 2008

A permutation array(or code) of length $n$ and distance $d$, denoted by $(n,d)$ PA, is a set of permutations $C$ from some fixed set of $n$ elements such that the Hamming distance between distinct members $\mathbf{x},\mathbf{y}\in C$ is at least $d$. Let $P(n,d)$ denote the maximum size of an $(n,d)$ PA. New upper bounds on $P(n,d)$ are given. For constant $α,β$ satisfying certain conditions, whenever $d=βn^α$, the new upper bounds are asymptotically better than the previous ones.
New Constructions of Permutation Arrays
Venue: arXiv cs.IT 2008
Year: 2008

A permutation array(permutation code, PA) of length $n$ and distance $d$, denoted by $(n,d)$ PA, is a set of permutations $C$ from some fixed set of $n$ elements such that the Hamming distance between distinct members $\mathbf{x},\mathbf{y}\in C$ is at least $d$. In this correspondence, we present two constructions of PA from fractional polynomials over finite field, and a construction of $(n,d)$ PA from permutation group with degree $n$ and minimal degree $d$. All these new constructions produces some new lower bounds for PA.
e-Science perspectives in Venezuela
Venue: arXiv cs.DC 2008
Year: 2008

We describe the e-Science strategy in Venezuela, in particular initiatives by the Centro Nacional de Calculo Cientifico Universidad de Los Andes (CECALCULA), Merida, the Universidad de Los Andes (ULA), Merida, and the Instituto Venezolano de Investigaciones Cientificas (IVIC), Caracas. We present the plans for the Venezuelan Academic Grid and the current status of Grid ULA supported by Internet2. We show different web-based scientific applications that are being developed in quantum chemistry, atomic physics, structural damage analysis, biomedicine and bioclimate within the framework of the E-Infrastructure shared between Europe and Latin America (EELA)
A statistical mechanical interpretation of algorithmic information theory
Venue: arXiv cs.IT 2008
Year: 2008

We develop a statistical mechanical interpretation of algorithmic information theory by introducing the notion of thermodynamic quantities, such as free energy, energy, statistical mechanical entropy, and specific heat, into algorithmic information theory. We investigate the properties of these quantities by means of program-size complexity from the point of view of algorithmic randomness. It is then discovered that, in the interpretation, the temperature plays a role as the compression rate of the values of all these thermodynamic quantities, which include the temperature itself. Reflecting this self-referential nature of the compression rate of the temperature, we obtain fixed point theorems on compression rate.
Biopsies prostatiques sous guidage échographique 3D et temps réel (4D) sur fantôme. Etude comparative versus guidage 2D
Venue: arXiv cs.OH 2008
Year: 2008

This paper analyzes the impact of using 2D or 3D ultrasound on the efficiency of prostate biopsies. The evaluation is performed on home-made phantoms. The study shows that the accuracy is significantly improved.
Understanding the Paradoxical Effects of Power Control on the Capacity of Wireless Networks
Venue: arXiv cs.NI 2008
Year: 2008

Recent works show conflicting results: network capacity may increase or decrease with higher transmission power under different scenarios. In this work, we want to understand this paradox. Specifically, we address the following questions: (1)Theoretically, should we increase or decrease transmission power to maximize network capacity? (2) Theoretically, how much network capacity gain can we achieve by power control? (3) Under realistic situations, how do power control, link scheduling and routing interact with each other? Under which scenarios can we expect a large capacity gain by using higher transmission power? To answer these questions, firstly, we prove that the optimal network capacity is a non-decreasing function of transmission power. Secondly, we prove that the optimal network capacity can be increased unlimitedly by higher transmission power in some network configurations. However, when nodes are distributed uniformly, the gain of optimal network capacity by higher transmission power is upper-bounded by a positive constant. Thirdly, we discuss why network capacity in practice may increase or decrease with higher transmission power under different scenarios using carrier sensing and the minimum hop-count routing. Extensive simulations are carried out to verify our analysis.
Temporal Correlations of Local Network Losses
Venue: arXiv cs.NI 2008
Year: 2008

We introduce a continuum model describing data losses in a single node of a packet-switched network (like the Internet) which preserves the discrete nature of the data loss process. {\em By construction}, the model has critical behavior with a sharp transition from exponentially small to finite losses with increasing data arrival rate. We show that such a model exhibits strong fluctuations in the loss rate at the critical point and non-Markovian power-law correlations in time, in spite of the Markovian character of the data arrival process. The continuum model allows for rather general incoming data packet distributions and can be naturally generalized to consider the buffer server idleness statistics.
Automatic Text Area Segmentation in Natural Images
Venue: arXiv cs.CV 2008
Year: 2008

We present a hierarchical method for segmenting text areas in natural images. The method assumes that the text is written with a contrasting color on a more or less uniform background. But no assumption is made regarding the language or character set used to write the text. In particular, the text can contain simple graphics or symbols. The key feature of our approach is that we first concentrate on finding the background of the text, before testing whether there is actually text on the background. Since uniform areas are easy to find in natural images, and since text backgrounds define areas which contain "holes" (where the text is written) we thus look for uniform areas containing "holes" and label them as text backgrounds candidates. Each candidate area is then further tested for the presence of text within its convex hull. We tested our method on a database of 65 images including English and Urdu text. The method correctly segmented all the text areas in 63 of these images, and in only 4 of these were areas that do not contain text also segmented.
Accélération des cartes auto-organisatrices sur tableau de dissimilarités par séparation et évaluation
Venue: arXiv cs.NE 2008
Year: 2008

In this paper, a new implementation of the adaptation of Kohonen self-organising maps (SOM) to dissimilarity matrices is proposed. This implementation relies on the branch and bound principle to reduce the algorithm running time. An important property of this new approach is that the obtained algorithm produces exactly the same results as the standard algorithm.
Trusted-HB: a low-cost version of HB+ secure against Man-in-The-Middle attacks
Venue: arXiv cs.CR 2008
Year: 2008

Since the introduction at Crypto'05 by Juels and Weis of the protocol HB+, a lightweight protocol secure against active attacks but only in a detection based-model, many works have tried to enhance its security. We propose here a new approach to achieve resistance against Man-in-The-Middle attacks. Our requirements - in terms of extra communications and hardware - are surprisingly low.
Développement et analyse multi outils d'un protocole MAC déterministe pour un réseau de capteurs sans fil
Venue: arXiv cs.NI 2008
Year: 2008

In this article, we present a multi-tool method for the development and the analysis of a new medium access method. IEEE 802.15.4 / ZigBee technology has been used as a basis for this new determinist MAC layer which enables a high level of QoS. This WPAN can be typically used for wireless sensor networks which require strong temporal constraints. To validate the proposed protocol, three complementary and adequate tools are used: Petri Nets for the formal validation of the algorithm, a dedicated simulator for the temporal aspects, and some measures on a real prototype based on a couple of ZigBee FREESCALE components for the hardware characterization of layers #1 and #2.
Turbo Interleaving inside the cdma2000 and W-CDMA Mobile Communication Systems: A Tutorial
Venue: arXiv cs.IT 2008
Year: 2008

In this paper a discussion of the detailed operation of the interleavers used by the turbo codes defined on the telecommunications standards cdma2000 (3GPP2 C.S0024-B V2.0) and W-CDMA (3GPP TS 25.212 V7.4.0) is presented. Differences in the approach used by each turbo interleaver as well as dispersion analysis and frequency analysis are also discussed. Two examples are presented to illustrate the complete interleaving process defined by each standard. These two interleaving approaches are also representative for other communications standards.
An Empirical Study of Cache-Oblivious Priority Queues and their Application to the Shortest Path Problem
Venue: arXiv cs.DS 2008
Year: 2008

In recent years the Cache-Oblivious model of external memory computation has provided an attractive theoretical basis for the analysis of algorithms on massive datasets. Much progress has been made in discovering algorithms that are asymptotically optimal or near optimal. However, to date there are still relatively few successful experimental studies. In this paper we compare two different Cache-Oblivious priority queues based on the Funnel and Bucket Heap and apply them to the single source shortest path problem on graphs with positive edge weights. Our results show that when RAM is limited and data is swapping to external storage, the Cache-Oblivious priority queues achieve orders of magnitude speedups over standard internal memory techniques. However, for the single source shortest path problem both on simulated and real world graph data, these speedups are markedly lower due to the time required to access the graph adjacency list itself.
Complexity of Combinatorial Market Makers
Venue: arXiv cs.GT 2008
Year: 2008

We analyze the computational complexity of market maker pricing algorithms for combinatorial prediction markets. We focus on Hanson's popular logarithmic market scoring rule market maker (LMSR). Our goal is to implicitly maintain correct LMSR prices across an exponentially large outcome space. We examine both permutation combinatorics, where outcomes are permutations of objects, and Boolean combinatorics, where outcomes are combinations of binary events. We look at three restrictive languages that limit what traders can bet on. Even with severely limited languages, we find that LMSR pricing is $\SP$-hard, even when the same language admits polynomial-time matching without the market maker. We then propose an approximation technique for pricing permutation markets based on a recent algorithm for online permutation learning. The connections we draw between LMSR pricing and the vast literature on online learning with expert advice may be of independent interest.
Ascending runs in dependent uniformly distributed random variables: Application to wireless networks
Venue: arXiv cs.DM 2008
Year: 2008

We analyze in this paper the longest increasing contiguous sequence or maximal ascending run of random variables with common uniform distribution but not independent. Their dependence is characterized by the fact that two successive random variables cannot take the same value. Using a Markov chain approach, we study the distribution of the maximal ascending run and we develop an algorithm to compute it. This problem comes from the analysis of several self-organizing protocols designed for large-scale wireless sensor networks, and we show how our results apply to this domain.
Extreme Learning Machine for land cover classification
Venue: arXiv cs.NE 2008
Year: 2008

This paper explores the potential of extreme learning machine based supervised classification algorithm for land cover classification. In comparison to a backpropagation neural network, which requires setting of several user-defined parameters and may produce local minima, extreme learning machine require setting of one parameter and produce a unique solution. ETM+ multispectral data set (England) was used to judge the suitability of extreme learning machine for remote sensing classifications. A back propagation neural network was used to compare its performance in term of classification accuracy and computational cost. Results suggest that the extreme learning machine perform equally well to back propagation neural network in term of classification accuracy with this data set. The computational cost using extreme learning machine is very small in comparison to back propagation neural network.
ARQ for Network Coding
Venue: arXiv cs.IT 2008
Year: 2008

A new coding and queue management algorithm is proposed for communication networks that employ linear network coding. The algorithm has the feature that the encoding process is truly online, as opposed to a block-by-block approach. The setup assumes a packet erasure broadcast channel with stochastic arrivals and full feedback, but the proposed scheme is potentially applicable to more general lossy networks with link-by-link feedback. The algorithm guarantees that the physical queue size at the sender tracks the backlog in degrees of freedom (also called the virtual queue size). The new notion of a node "seeing" a packet is introduced. In terms of this idea, our algorithm may be viewed as a natural extension of ARQ schemes to coded networks. Our approach, known as the drop-when-seen algorithm, is compared with a baseline queuing approach called drop-when-decoded. It is shown that the expected queue size for our approach is $O(\frac1{1-ρ})$ as opposed to $Ω(\frac1{(1-ρ)^2})$ for the baseline approach, where $ρ$ is the load factor.
On the Complexity of Elementary Modal Logics
Venue: arXiv cs.CC 2008
Year: 2008

Modal logics are widely used in computer science. The complexity of modal satisfiability problems has been investigated since the 1970s, usually proving results on a case-by-case basis. We prove a very general classification for a wide class of relevant logics: Many important subclasses of modal logics can be obtained by restricting the allowed models with first-order Horn formulas. We show that the satisfiability problem for each of these logics is either NP-complete or PSPACE-hard, and exhibit a simple classification criterion. Further, we prove matching PSPACE upper bounds for many of the PSPACE-hard logics.
Blocking Sets in the complement of hyperplane arrangements in projective space
Venue: arXiv cs.IT 2008
Year: 2008

It is well know that the theory of minimal blocking sets is studied by several author. Another theory which is also studied by a large number of researchers is the theory of hyperplane arrangements. We can remark that the affine space $AG(n,q)$ is the complement of the line at infinity in $PG(n,q)$. Then $AG(n,q)$ can be regarded as the complement of an hyperplane arrangement in $PG(n,q)$! Therefore the study of blocking sets in the affine space $AG(n,q)$ is simply the study of blocking sets in the complement of a finite arrangement in $PG(n,q)$. In this paper the author generalizes this remark starting to study the problem of existence of blocking sets in the complement of a given hyperplane arrangement in $PG(n,q)$. As an example she solves the problem for the case of braid arrangement. Moreover she poses significant questions on this new and interesting problem.
Reconstruction of eye movements during blinks
Venue: arXiv cs.SC 2008
Year: 2008

In eye movement research in reading, the amount of data plays a crucial role for the validation of results. A methodological problem for the analysis of the eye movement in reading are blinks, when readers close their eyes. Blinking rate increases with increasing reading time, resulting in high data losses, especially for older adults or reading impaired subjects. We present a method, based on the symbolic sequence dynamics of the eye movements, that reconstructs the horizontal position of the eyes while the reader blinks. The method makes use of an observed fact that the movements of the eyes before closing or after opening contain information about the eyes movements during blinks. Test results indicate that our reconstruction method is superior to methods that use simpler interpolation approaches. In addition, analyses of the reconstructed data show no significant deviation from the usual behavior observed in readers.
Approximation Resistant Predicates From Pairwise Independence
Venue: arXiv cs.CC 2008
Year: 2008

We study the approximability of predicates on $k$ variables from a domain $[q]$, and give a new sufficient condition for such predicates to be approximation resistant under the Unique Games Conjecture. Specifically, we show that a predicate $P$ is approximation resistant if there exists a balanced pairwise independent distribution over $[q]^k$ whose support is contained in the set of satisfying assignments to $P$.
On the Frame Error Rate of Transmission Schemes on Quasi-Static Fading Channels
Venue: arXiv cs.IT 2008
Year: 2008

It is known that the frame error rate of turbo codes on quasi-static fading channels can be accurately approximated using the convergence threshold of the corresponding iterative decoder. This paper considers quasi-static fading channels and demonstrates that non-iterative schemes can also be characterized by a similar threshold based on which their frame error rate can be readily estimated. In particular, we show that this threshold is a function of the probability of successful frame detection in additive white Gaussian noise, normalized by the squared instantaneous signal-to-noise ratio. We apply our approach to uncoded binary phase shift keying, convolutional coding and turbo coding and demonstrate that the approximated frame error rate is within 0.4 dB of the simulation results. Finally, we introduce performance evaluation plots to explore the impact of the frame size on the performance of the schemes under investigation.
Anisotropic selection in cellular genetic algorithms
Venue: arXiv cs.AI 2008
Year: 2008

In this paper we introduce a new selection scheme in cellular genetic algorithms (cGAs). Anisotropic Selection (AS) promotes diversity and allows accurate control of the selective pressure. First we compare this new scheme with the classical rectangular grid shapes solution according to the selective pressure: we can obtain the same takeover time with the two techniques although the spreading of the best individual is different. We then give experimental results that show to what extent AS promotes the emergence of niches that support low coupling and high cohesion. Finally, using a cGA with anisotropic selection on a Quadratic Assignment Problem we show the existence of an anisotropic optimal value for which the best average performance is observed. Further work will focus on the selective pressure self-adjustment ability provided by this new selection scheme.
Order-Optimal Consensus through Randomized Path Averaging
Venue: arXiv cs.IT 2008
Year: 2008

Gossip algorithms have recently received significant attention, mainly because they constitute simple and robust message-passing schemes for distributed information processing over networks. However for many topologies that are realistic for wireless ad-hoc and sensor networks (like grids and random geometric graphs), the standard nearest-neighbor gossip converges as slowly as flooding ($O(n^2)$ messages). A recently proposed algorithm called geographic gossip improves gossip efficiency by a $\sqrt{n}$ factor, by exploiting geographic information to enable multi-hop long distance communications. In this paper we prove that a variation of geographic gossip that averages along routed paths, improves efficiency by an additional $\sqrt{n}$ factor and is order optimal ($O(n)$ messages) for grids and random geometric graphs. We develop a general technique (travel agency method) based on Markov chain mixing time inequalities, which can give bounds on the performance of randomized message-passing algorithms operating over various graph topologies.
Distributed Joint Source-Channel Coding for arbitrary memoryless correlated sources and Source coding for Markov correlated sources using LDPC codes
Venue: arXiv cs.IT 2008
Year: 2008

In this paper, we give a distributed joint source channel coding scheme for arbitrary correlated sources for arbitrary point in the Slepian-Wolf rate region, and arbitrary link capacities using LDPC codes. We consider the Slepian-Wolf setting of two sources and one destination, with one of the sources derived from the other source by some correlation model known at the decoder. Distributed encoding and separate decoding is used for the two sources. We also give a distributed source coding scheme when the source correlation has memory to achieve any point in the Slepian-Wolf rate achievable region. In this setting, we perform separate encoding but joint decoding.
On strongly controllable group codes and mixing group shifts: solvable groups, translation nets, and algorithms
Venue: arXiv cs.IT 2008
Year: 2008

The branch group of a strongly controllable group code is a shift group. We show that a shift group can be characterized in a very simple way. In addition it is shown that if a strongly controllable group code is labeled with Latin squares, a strongly controllable Latin group code, then the shift group is solvable. Moreover the mathematical structure of a Latin square (as a translation net) and the shift group of a strongly controllable Latin group code are closely related. Thus a strongly controllable Latin group code can be viewed as a natural extension of a Latin square to a sequence space. Lastly we construct shift groups. We show that it is sufficient to construct a simpler group, the state group of a shift group. We give an algorithm to find the state group, and from this it is easy to construct a stronlgy controllable Latin group code.
On the decomposition of k-valued rational relations
Venue: arXiv cs.IT 2008
Year: 2008

We give a new, and hopefully more easily understandable, structural proof of the decomposition of a $k$-valued transducer into $k$ unambiguous functional ones, a result established by A. Weber in 1996. Our construction is based on a lexicographic ordering of computations of automata and on two coverings that can be build by means of this ordering. The complexity of the construction, measured as the number of states of the transducers involved in the decomposition, improves the original one by one exponential. Moreover, this method allows further generalisation that solves the problem of decomposition of rational relations with bounded length-degree, which was left open in Weber's paper.