OpenRaiser/Intern-Atlas huggingface dataset:
Distributed Joint Source-Channel Coding on a Multiple Access Channel with Side Information
Venue: arXiv cs.IT 2008
Year: 2008

We consider the problem of transmission of several distributed sources over a multiple access channel (MAC) with side information at the sources and the decoder. Source-channel separation does not hold for this channel. Sufficient conditions are provided for transmission of sources with a given distortion. The source and/or the channel could have continuous alphabets (thus Gaussian sources and Gaussian MACs are special cases). Various previous results are obtained as special cases. We also provide several good joint source-channel coding schemes for a discrete/continuous source and discrete/continuous alphabet channel. Channels with feedback and fading are also considered. Keywords: Multiple access channel, side information, lossy joint source-channel coding, channels with feedback, fading channels.
Simulation Optimization of the Crossdock Door Assignment Problem
Venue: arXiv cs.NE 2008
Year: 2008

The purpose of this report is to present the Crossdock Door Assignment Problem, which involves assigning destinations to outbound dock doors of Crossdock centres such that travel distance by material handling equipment is minimized. We propose a two fold solution; simulation and optimization of the simulation model simulation optimization. The novel aspect of our solution approach is that we intend to use simulation to derive a more realistic objective function and use Memetic algorithms to find an optimal solution. The main advantage of using Memetic algorithms is that it combines a local search with Genetic Algorithms. The Crossdock Door Assignment Problem is a new domain application to Memetic Algorithms and it is yet unknown how it will perform.
A Multi-Agent Simulation of Retail Management Practices
Venue: arXiv cs.NE 2008
Year: 2008

We apply Agent-Based Modeling and Simulation (ABMS) to investigate a set of problems in a retail context. Specifically, we are working to understand the relationship between human resource management practices and retail productivity. Despite the fact we are working within a relatively novel and complex domain, it is clear that intelligent agents do offer potential for developing organizational capabilities in the future. Our multi-disciplinary research team has worked with a UK department store to collect data and capture perceptions about operations from actors within departments. Based on this case study work, we have built a simulator that we present in this paper. We then use the simulator to gather empirical evidence regarding two specific management practices: empowerment and employee development.
An Agent-Based Simulation of In-Store Customer Experiences
Venue: arXiv cs.NE 2008
Year: 2008

Agent-based modelling and simulation offers a new and exciting way of understanding the world of work. In this paper we describe the development of an agent-based simulation model, designed to help to understand the relationship between human resource management practices and retail productivity. We report on the current development of our simulation model which includes new features concerning the evolution of customers over time. To test some of these features we have conducted a series of experiments dealing with customer pool sizes, standard and noise reduction modes, and the spread of the word of mouth. Our multi-disciplinary research team draws upon expertise from work psychologists and computer scientists. Despite the fact we are working within a relatively novel and complex domain, it is clear that intelligent agents offer potential for fostering sustainable organisational capabilities in the future.
Self-Assembly of Discrete Self-Similar Fractals
Venue: arXiv cs.CC 2008
Year: 2008

In this paper, we search for {\it absolute} limitations of the Tile Assembly Model (TAM), along with techniques to work around such limitations. Specifically, we investigate the self-assembly of fractal shapes in the TAM. We prove that no self-similar fractal fully weakly self-assembles at temperature 1, and that certain kinds of self-similar fractals do not strictly self-assemble at any temperature. Additionally, we extend the fiber construction from Lathrop et. al. (2007) to show that any self-similar fractal belonging to a particular class of "nice" self-similar fractals has a fibered version that strictly self-assembles in the TAM.
A Computational Framework for the Near Elimination of Spreadsheet Risk
Venue: arXiv cs.SE 2008
Year: 2008

We present Risk Integrated's Enterprise Spreadsheet Platform (ESP), a technical approach to the near-elimination of spreadsheet risk in the enterprise computing environment, whilst maintaining the full flexibility of spreadsheets for modelling complex financial structures and processes. In its Basic Mode of use, the system comprises a secure and robust centralised spreadsheet management framework. In Advanced Mode, the system can be viewed as a robust computational framework whereby users can "submit jobs" to the spreadsheet, and retrieve the results from the computations, but with no direct access to the underlying spreadsheet. An example application, Monte Carlo simulation, is presented to highlight the benefits of this approach with regard to mitigating spreadsheet risk in complex, mission-critical, financial calculations.
Improved evolutionary generation of XSLT stylesheets
Venue: arXiv cs.NE 2008
Year: 2008

This paper introduces a procedure based on genetic programming to evolve XSLT programs (usually called stylesheets or logicsheets). XSLT is a general purpose, document-oriented functional language, generally used to transform XML documents (or, in general, solve any problem that can be coded as an XML document). The proposed solution uses a tree representation for the stylesheets as well as diverse specific operators in order to obtain, in the studied cases and a reasonable time, a XSLT stylesheet that performs the transformation. Several types of representation have been compared, resulting in different performance and degree of success.
Compressed Modular Matrix Multiplication
Venue: arXiv cs.SC 2008
Year: 2008

We propose to store several integers modulo a small prime into a single machine word. Modular addition is performed by addition and possibly subtraction of a word containing several times the modulo. Modular Multiplication is not directly accessible but modular dot product can be performed by an integer multiplication by the reverse integer. Modular multiplication by a word containing a single residue is a also possible. Therefore matrix multiplication can be performed on such a compressed storage. We here give bounds on the sizes of primes and matrices for which such a compression is possible. We also explicit the details of the required compressed arithmetic routines.
An Investigation of the Sequential Sampling Method for Crossdocking Simulation Output Variance Reduction
Venue: arXiv cs.NE 2008
Year: 2008

This paper investigates the reduction of variance associated with a simulation output performance measure, using the Sequential Sampling method while applying minimum simulation replications, for a class of JIT (Just in Time) warehousing system called crossdocking. We initially used the Sequential Sampling method to attain a desired 95% confidence interval half width of plus/minus 0.5 for our chosen performance measure (Total usage cost, given the mean maximum level of 157,000 pounds and a mean minimum level of 149,000 pounds). From our results, we achieved a 95% confidence interval half width of plus/minus 2.8 for our chosen performance measure (Total usage cost, with an average mean value of 115,000 pounds). However, the Sequential Sampling method requires a huge number of simulation replications to reduce variance for our simulation output value to the target level. Arena (version 11) simulation software was used to conduct this study.
Danger Theory: The Link between AIS and IDS?
Venue: arXiv cs.NE 2008
Year: 2008

We present ideas about creating a next generation Intrusion Detection System based on the latest immunological theories. The central challenge with computer security is determining the difference between normal and potentially harmful activity. For half a century, developers have protected their systems by coding rules that identify and block specific events. However, the nature of current and future threats in conjunction with ever larger IT systems urgently requires the development of automated and adaptive defensive tools. A promising solution is emerging in the form of Artificial Immune Systems. The Human Immune System can detect and defend against harmful and previously unseen invaders, so can we not build a similar Intrusion Detection System for our computers.
On $(P_5,\bar{P_5})$-sparse graphs and other families
Venue: arXiv cs.DM 2008
Year: 2008

We extend the notion of $P_4$-sparse graphs previously introduced by {\scshape Hoàng} by considering $\mathcal{F}$-sparse graphs were $\mathcal{F}$ denotes a finite set of graphs on $p$ vertices. Thus we obtain some results on $(P_5,\bar{P_5})$-sparse graphs already known on $(P_5,\bar{P_5})$-free graphs. Finally we completely describe the structure of $(P_5,\bar{P_5}, bull$)-sparse graphs, it follows that those graphs have bounded clique-width.
Conditioning Probabilistic Databases
Venue: arXiv cs.DB 2008
Year: 2008

Past research on probabilistic databases has studied the problem of answering queries on a static database. Application scenarios of probabilistic databases however often involve the conditioning of a database using additional information in the form of new evidence. The conditioning problem is thus to transform a probabilistic database of priors into a posterior probabilistic database which is materialized for subsequent query processing or further refinement. It turns out that the conditioning problem is closely related to the problem of computing exact tuple confidence values. It is known that exact confidence computation is an NP-hard problem. This has led researchers to consider approximation techniques for confidence computation. However, neither conditioning nor exact confidence computation can be solved using such techniques. In this paper we present efficient techniques for both problems. We study several problem decomposition methods and heuristics that are based on the most successful search techniques from constraint satisfaction, such as the Davis-Putnam algorithm. We complement this with a thorough experimental evaluation of the algorithms proposed. Our experiments show that our exact algorithms scale well to realistic database sizes and can in some scenarios compete with the most efficient previous approximation algorithms.
The Anatomy of Mitos Web Search Engine
Venue: arXiv cs.IR 2008
Year: 2008

Engineering a Web search engine offering effective and efficient information retrieval is a challenging task. This document presents our experiences from designing and developing a Web search engine offering a wide spectrum of functionalities and we report some interesting experimental results. A rather peculiar design choice of the engine is that its index is based on a DBMS, while some of the distinctive functionalities that are offered include advanced Greek language stemming, real time result clustering, and advanced link analysis techniques (also for spam page detection).
The Abella Interactive Theorem Prover (System Description)
Venue: arXiv cs.LO 2008
Year: 2008

Abella is an interactive system for reasoning about aspects of object languages that have been formally presented through recursive rules based on syntactic structure. Abella utilizes a two-level logic approach to specification and reasoning. One level is defined by a specification logic which supports a transparent encoding of structural semantics rules and also enables their execution. The second level, called the reasoning logic, embeds the specification logic and allows the development of proofs of properties about specifications. An important characteristic of both logics is that they exploit the lambda tree syntax approach to treating binding in object languages. Amongst other things, Abella has been used to prove normalizability properties of the lambda calculus, cut admissibility for a sequent calculus and type uniqueness and subject reduction properties. This paper discusses the logical foundations of Abella, outlines the style of theorem proving that it supports and finally describes some of its recent applications.
Tableau-based decision procedures for logics of strategic ability in multi-agent systems
Venue: arXiv cs.LO 2008
Year: 2008

We develop an incremental tableau-based decision procedures for the Alternating-time temporal logic ATL and some of its variants. While running within the theoretically established complexity upper bound, we claim that our tableau is practically more efficient in the average case than other decision procedures for ATL known so far. Besides, the ease of its adaptation to variants of ATL demonstrates the flexibility of the proposed procedure.
Two Algorithms for Solving A General Backward Pentadiagonal Linear Systems
Venue: arXiv cs.SC 2008
Year: 2008

In this paper we present an efficient computational and symbolic algorithms for solving a backward pentadiagonal linear systems. The implementation of the algorithms using Computer Algebra Systems (CAS) such as MAPLE, MACSYMA, MATHEMATICA, and MATLAB are straightforward. An examples are given in order to illustrate the algorithms. The symbolic algorithm is competitive the other methods for solving a backward pentadiagonal linear systems.
lambda-Connectedness Determination for Image Segmentation
Venue: arXiv cs.CV 2008
Year: 2008

Image segmentation is to separate an image into distinct homogeneous regions belonging to different objects. It is an essential step in image analysis and computer vision. This paper compares some segmentation technologies and attempts to find an automated way to better determine the parameters for image segmentation, especially the connectivity value of $λ$ in $λ$-connected segmentation. Based on the theories on the maximum entropy method and Otsu's minimum variance method, we propose:(1)maximum entropy connectedness determination: a method that uses maximum entropy to determine the best $λ$ value in $λ$-connected segmentation, and (2) minimum variance connectedness determination: a method that uses the principle of minimum variance to determine $λ$ value. Applying these optimization techniques in real images, the experimental results have shown great promise in the development of the new methods. In the end, we extend the above method to more general case in order to compare it with the famous Mumford-Shah method that uses variational principle and geometric measure.
Rapport de recherche sur le problème du plus court chemin contraint
Venue: arXiv cs.DS 2008
Year: 2008

This article provides an overview of the performance and the theoretical complexity of approximate and exact methods for various versions of the shortest path problem. The proposed study aims to improve the resolution of a more general covering problem within a column generation scheme in which the shortest path problem is the sub-problem.
Figuring out Actors in Text Streams: Using Collocations to establish Incremental Mind-maps
Venue: arXiv cs.CL 2008
Year: 2008

The recognition, involvement, and description of main actors influences the story line of the whole text. This is of higher importance as the text per se represents a flow of words and expressions that once it is read it is lost. In this respect, the understanding of a text and moreover on how the actor exactly behaves is not only a major concern: as human beings try to store a given input on short-term memory while associating diverse aspects and actors with incidents, the following approach represents a virtual architecture, where collocations are concerned and taken as the associative completion of the actors' acting. Once that collocations are discovered, they become managed in separated memory blocks broken down by the actors. As for human beings, the memory blocks refer to associative mind-maps. We then present several priority functions to represent the actual temporal situation inside a mind-map to enable the user to reconstruct the recent events from the discovered temporal results.
An Indirect Genetic Algorithm for a Nurse Scheduling Problem
Venue: arXiv cs.NE 2008
Year: 2008

This paper describes a Genetic Algorithms approach to a manpower-scheduling problem arising at a major UK hospital. Although Genetic Algorithms have been successfully used for similar problems in the past, they always had to overcome the limitations of the classical Genetic Algorithms paradigm in handling the conflict between objectives and constraints. The approach taken here is to use an indirect coding based on permutations of the nurses, and a heuristic decoder that builds schedules from these permutations. Computational experiments based on 52 weeks of live data are used to evaluate three different decoders with varying levels of intelligence, and four well-known crossover operators. Results are further enhanced by introducing a hybrid crossover operator and by making use of simple bounds to reduce the size of the solution space. The results reveal that the proposed algorithm is able to find high quality solutions and is both faster and more flexible than a recently published Tabu Search approach.
Idiotypic Immune Networks in Mobile Robot Control
Venue: arXiv cs.NE 2008
Year: 2008

Jerne's idiotypic network theory postulates that the immune response involves inter-antibody stimulation and suppression as well as matching to antigens. The theory has proved the most popular Artificial Immune System (ais) model for incorporation into behavior-based robotics but guidelines for implementing idiotypic selection are scarce. Furthermore, the direct effects of employing the technique have not been demonstrated in the form of a comparison with non-idiotypic systems. This paper aims to address these issues. A method for integrating an idiotypic ais network with a Reinforcement Learning based control system (rl) is described and the mechanisms underlying antibody stimulation and suppression are explained in detail. Some hypotheses that account for the network advantage are put forward and tested using three systems with increasing idiotypic complexity. The basic rl, a simplified hybrid ais-rl that implements idiotypic selection independently of derived concentration levels and a full hybrid ais-rl scheme are examined. The test bed takes the form of a simulated Pioneer robot that is required to navigate through maze worlds detecting and tracking door markers.
Loss Fluctuations and Temporal Correlations in Network Queues
Venue: arXiv cs.NI 2008
Year: 2008

We consider data losses in a single node of a packet-switched Internet-like network. We employ two distinct models, one with discrete and the other with continuous one-dimensional random walks, representing the state of a queue in a router. Both models {have} a built-in critical behavior with {a sharp} transition from exponentially small to finite losses. It turns out that the finite capacity of a buffer and the packet-dropping procedure give rise to specific boundary conditions which lead to strong loss rate fluctuations at the critical point even in the absence of such fluctuations in the data arrival process.
Facing the Facts
Venue: arXiv cs.HC 2008
Year: 2008

Human error research on overconfidence supports the benefits of early visibility of defects and disciplined development. If risk to the enterprise is to be reduced, individuals need to become aware of the reality of the quality of their work. Several cycles of inspection and defect removal are inevitable. Software Quality Management measurements of defect density and removal efficiency are applicable. Research of actual spreadsheet error rates shows data consistent with other software depending on the extent to which the work product was reviewed before inspection. The paper argues that the payback for an investment in early review time is justified by the saving in project delay and expensive errors in use. 'If debugging is the process of removing bugs, then programming must be the process of putting them in' - Anon.
Secure Hop-by-Hop Aggregation of End-to-End Concealed Data in Wireless Sensor Networks
Venue: arXiv cs.CR 2008
Year: 2008

In-network data aggregation is an essential technique in mission critical wireless sensor networks (WSNs) for achieving effective transmission and hence better power conservation. Common security protocols for aggregated WSNs are either hop-by-hop or end-to-end, each of which has its own encryption schemes considering different security primitives. End-to-end encrypted data aggregation protocols introduce maximum data secrecy with in-efficient data aggregation and more vulnerability to active attacks, while hop-by-hop data aggregation protocols introduce maximum data integrity with efficient data aggregation and more vulnerability to passive attacks. In this paper, we propose a secure aggregation protocol for aggregated WSNs deployed in hostile environments in which dual attack modes are present. Our proposed protocol is a blend of flexible data aggregation as in hop-by-hop protocols and optimal data confidentiality as in end-to-end protocols. Our protocol introduces an efficient O(1) heuristic for checking data integrity along with cost-effective heuristic-based divide and conquer attestation process which is $O(\ln{n})$ in average -O(n) in the worst scenario- for further verification of aggregated results.
Void Traversal for Guaranteed Delivery in Geometric Routing
Venue: arXiv cs.OS 2008
Year: 2008

Geometric routing algorithms like GFG (GPSR) are lightweight, scalable algorithms that can be used to route in resource-constrained ad hoc wireless networks. However, such algorithms run on planar graphs only. To efficiently construct a planar graph, they require a unit-disk graph. To make the topology unit-disk, the maximum link length in the network has to be selected conservatively. In practical setting this leads to the designs where the node density is rather high. Moreover, the network diameter of a planar subgraph is greater than the original graph, which leads to longer routes. To remedy this problem, we propose a void traversal algorithm that works on arbitrary geometric graphs. We describe how to use this algorithm for geometric routing with guaranteed delivery and compare its performance with GFG.
A New Sphere-Packing Bound for Maximal Error Exponent for Multiple-Access Channels
Venue: arXiv cs.IT 2008
Year: 2008

In this work, a new lower bound for the maximal error probability of a two-user discrete memoryless (DM) multiple-access channel (MAC) is derived. This is the first bound of this type that explicitly imposes independence of the users' input distributions (conditioned on the time-sharing auxiliary variable) and thus results in a tighter sphere-packing exponent when compared to the tightest known exponent derived by Haroutunian.
Lower Bounds on the Minimum Pseudodistance for Linear Codes with $q$-ary PSK Modulation over AWGN
Venue: arXiv cs.IT 2008
Year: 2008

We present lower bounds on the minimum pseudocodeword effective Euclidean distance (or minimum "pseudodistance") for coded modulation systems using linear codes with $q$-ary phase-shift keying (PSK) modulation over the additive white Gaussian noise (AWGN) channel. These bounds apply to both binary and nonbinary coded modulation systems which use direct modulation mapping of coded symbols. The minimum pseudodistance may serve as a first-order measure of error-correcting performance for both linear-programming and message-passing based receivers. In the case of a linear-programming based receiver, the minimum pseudodistance may be used to form an exact bound on the codeword error rate of the system.