OpenRaiser/Intern-Atlas huggingface dataset:
Parallel execution of portfolio optimization
Venue: arXiv cs.DC 2008
Year: 2008

Analysis of asset liability management (ALM) strategies especially for long term horizon is a crucial issue for banks, funds and insurance companies. Modern economic models, investment strategies and optimization criteria make ALM studies computationally very intensive task. It attracts attention to multiprocessor system and especially to the cheapest one: multi core PCs and PC clusters. In this article we are analyzing problem of parallel organization of portfolio optimization, results of using clusters for optimization and the most efficient cluster architecture for these kinds of tasks.
Modeling Microscopic Chemical Sensors in Capillaries
Venue: arXiv cs.RO 2008
Year: 2008

Nanotechnology-based microscopic robots could provide accurate in vivo measurement of chemicals in the bloodstream for detailed biological research and as an aid to medical treatment. Quantitative performance estimates of such devices require models of how chemicals in the blood diffuse to the devices. This paper models microscopic robots and red blood cells (erythrocytes) in capillaries using realistic distorted cell shapes. The models evaluate two sensing scenarios: robots moving with the cells past a chemical source on the vessel wall, and robots attached to the wall for longer-term chemical monitoring. Using axial symmetric geometry with realistic flow speeds and diffusion coefficients, we compare detection performance with a simpler model that does not include the cells. The average chemical absorption is quantitatively similar in both models, indicating the simpler model is an adequate design guide to sensor performance in capillaries. However, determining the variation in forces and absorption as cells move requires the full model.
Airport Gate Assignment: New Model and Implementation
Venue: arXiv cs.AI 2008
Year: 2008

Airport gate assignment is of great importance in airport operations. In this paper, we study the Airport Gate Assignment Problem (AGAP), propose a new model and implement the model with Optimization Programming language (OPL). With the objective to minimize the number of conflicts of any two adjacent aircrafts assigned to the same gate, we build a mathematical model with logical constraints and the binary constraints, which can provide an efficient evaluation criterion for the Airlines to estimate the current gate assignment. To illustrate the feasibility of the model we construct experiments with the data obtained from Continental Airlines, Houston Gorge Bush Intercontinental Airport IAH, which indicate that our model is both energetic and effective. Moreover, we interpret experimental results, which further demonstrate that our proposed model can provide a powerful tool for airline companies to estimate the efficiency of their current work of gate assignment.
Decentralized Overlay for Federation of Enterprise Clouds
Venue: arXiv cs.DC 2008
Year: 2008

This chapter describes Aneka-Federation, a decentralized and distributed system that combines enterprise Clouds, overlay networking, and structured peer-to-peer techniques to create scalable wide-area networking of compute nodes for high-throughput computing. The Aneka-Federation integrates numerous small scale Aneka Enterprise Cloud services and nodes that are distributed over multiple control and enterprise domains as parts of a single coordinated resource leasing abstraction. The system is designed with the aim of making distributed enterprise Cloud resource integration and application programming flexible, efficient, and scalable. The system is engineered such that it: enables seamless integration of existing Aneka Enterprise Clouds as part of single wide-area resource leasing federation; self-organizes the system components based on a structured peer-to-peer routing methodology; and presents end-users with a distributed application composition environment that can support variety of programming and execution models. This chapter describes the design and implementation of a novel, extensible and decentralized peer-to-peer technique that helps to discover, connect and provision the services of Aneka Enterprise Clouds among the users who can use different programming models to compose their applications. Evaluations of the system with applications that are programmed using the Task and Thread execution models on top of an overlay of Aneka Enterprise Clouds have been described here.
Characterizations of probe interval graphs
Venue: arXiv cs.DM 2008
Year: 2008

In this paper we obtain several characterizations of the adjacency matrix of a probe interval graph. In course of this study we describe an easy method of obtaining interval representation of an interval bipartite graph from its adjacency matrix. Finally, we note that if we add a loop at every probe vertex of a probe interval graph, then the Ferrers dimension of the corresponding symmetric bipartite graph is at most 3.
Belief functions on lattices
Venue: arXiv cs.DM 2008
Year: 2008

We extend the notion of belief function to the case where the underlying structure is no more the Boolean lattice of subsets of some universal set, but any lattice, which we will endow with a minimal set of properties according to our needs. We show that all classical constructions and definitions (e.g., mass allocation, commonality function, plausibility functions, necessity measures with nested focal elements, possibility distributions, Dempster rule of combination, decomposition w.r.t. simple support functions, etc.) remain valid in this general setting. Moreover, our proof of decomposition of belief functions into simple support functions is much simpler and general than the original one by Shafer.
A Cloning Pushout Approach to Term-Graph Transformation
Venue: arXiv cs.LO 2008
Year: 2008

We address the problem of cyclic termgraph rewriting. We propose a new framework where rewrite rules are tuples of the form $(L,R,τ,σ)$ such that $L$ and $R$ are termgraphs representing the left-hand and the right-hand sides of the rule, $τ$ is a mapping from the nodes of $L$ to those of $R$ and $σ$ is a partial function from nodes of $R$ to nodes of $L$. $τ$ describes how incident edges of the nodes in $L$ are connected in $R$. $τ$ is not required to be a graph morphism as in classical algebraic approaches of graph transformation. The role of $σ$ is to indicate the parts of $L$ to be cloned (copied). Furthermore, we introduce a new notion of \emph{cloning pushout} and define rewrite steps as cloning pushouts in a given category. Among the features of the proposed rewrite systems, we quote the ability to perform local and global redirection of pointers, addition and deletion of nodes as well as cloning and collapsing substructures.
Counting number of factorizations of a natural number
Venue: arXiv cs.DM 2008
Year: 2008

In this note we describe a new method of counting the number of unordered factorizations of a natural number by means of a generating function and a recurrence relation arising from it, which improves an earlier result in this direction.
Low-Memory Adaptive Prefix Coding
Venue: arXiv cs.DS 2008
Year: 2008

In this paper we study the adaptive prefix coding problem in cases where the size of the input alphabet is large. We present an online prefix coding algorithm that uses $O(σ^{1 / λ+ ε}) $ bits of space for any constants $\eps>0$, $λ>1$, and encodes the string of symbols in $O(\log \log σ)$ time per symbol \emph{in the worst case}, where $σ$ is the size of the alphabet. The upper bound on the encoding length is $λn H (s) +(λ\ln 2 + 2 + ε) n + O (σ^{1 / λ} \log^2 σ)$ bits.
Finding Sparse Cuts Locally Using Evolving Sets
Venue: arXiv cs.DS 2008
Year: 2008

A {\em local graph partitioning algorithm} finds a set of vertices with small conductance (i.e. a sparse cut) by adaptively exploring part of a large graph $G$, starting from a specified vertex. For the algorithm to be local, its complexity must be bounded in terms of the size of the set that it outputs, with at most a weak dependence on the number $n$ of vertices in $G$. Previous local partitioning algorithms find sparse cuts using random walks and personalized PageRank. In this paper, we introduce a randomized local partitioning algorithm that finds a sparse cut by simulating the {\em volume-biased evolving set process}, which is a Markov chain on sets of vertices. We prove that for any set of vertices $A$ that has conductance at most $ϕ$, for at least half of the starting vertices in $A$ our algorithm will output (with probability at least half), a set of conductance $O(ϕ^{1/2} \log^{1/2} n)$. We prove that for a given run of the algorithm, the expected ratio between its computational complexity and the volume of the set that it outputs is $O(ϕ^{-1/2} polylog(n))$. In comparison, the best previous local partitioning algorithm, due to Andersen, Chung, and Lang, has the same approximation guarantee, but a larger ratio of $O(ϕ^{-1} polylog(n))$ between the complexity and output volume. Using our local partitioning algorithm as a subroutine, we construct a fast algorithm for finding balanced cuts. Given a fixed value of $ϕ$, the resulting algorithm has complexity $O((m+nϕ^{-1/2}) polylog(n))$ and returns a cut with conductance $O(ϕ^{1/2} \log^{1/2} n)$ and volume at least $v_ϕ/2$, where $v_ϕ$ is the largest volume of any set with conductance at most $ϕ$.
A polytime proof of correctness of the Rabin-Miller algorithm from Fermat's little theorem
Venue: arXiv cs.CC 2008
Year: 2008

Although a deterministic polytime algorithm for primality testing is now known, the Rabin-Miller randomized test of primality continues being the most efficient and widely used algorithm. We prove the correctness of the Rabin-Miller algorithm in the theory V1 for polynomial time reasoning, from Fermat's little theorem. This is interesting because the Rabin-Miller algorithm is a polytime randomized algorithm, which runs in the class RP (i.e., the class of polytime Monte-Carlo algorithms), with a sampling space exponential in the length of the binary encoding of the input number. (The class RP contains polytime P.) However, we show how to express the correctness in the language of V1, and we also show that we can prove the formula expressing correctness with polytime reasoning from Fermat's Little theorem, which is generally expected to be independent of V1. Our proof is also conceptually very basic in the sense that we use the extended Euclid's algorithm, for computing greatest common divisors, as the main workhorse of the proof. For example, we make do without proving the Chinese Reminder theorem, which is used in the standard proofs.
The Simultaneous Membership Problem for Chordal, Comparability and Permutation graphs
Venue: arXiv cs.DM 2008
Year: 2008

In this paper we introduce the 'simultaneous membership problem', defined for any graph class C characterized in terms of representations, e.g. any class of intersection graphs. Two graphs G_1 and G_2, sharing some vertices X (and the corresponding induced edges), are said to be 'simultaneous members' of graph class C, if there exist representations R_1 and R_2 of G_1 and G_2 that are "consistent" on X. Equivalently (for the classes C that we consider) there exist edges E' between G_1-X and G_2-X such that G_1 \cup G_2 \cup E' belongs to class C. Simultaneous membership problems have application in any situation where it is desirable to consistently represent two related graphs, for example: interval graphs capturing overlaps of DNA fragments of two similar organisms; or graphs connected in time, where one is an updated version of the other. Simultaneous membership problems are related to simultaneous planar embeddings, graph sandwich problems and probe graph recognition problems. In this paper we give efficient algorithms for the simultaneous membership problem on chordal, comparability and permutation graphs. These results imply that graph sandwich problems for the above classes are tractable for an interesting special case: when the set of optional edges form a complete bipartite graph. Our results complement the recent polynomial time recognition algorithms for probe chordal, comparability, and permutation graphs, where the set of optional edges form a clique.
High resolution dynamical mapping of social interactions with active RFID
Venue: arXiv cs.CY 2008
Year: 2008

In this paper we present an experimental framework to gather data on face-to-face social interactions between individuals, with a high spatial and temporal resolution. We use active Radio Frequency Identification (RFID) devices that assess contacts with one another by exchanging low-power radio packets. When individuals wear the beacons as a badge, a persistent radio contact between the RFID devices can be used as a proxy for a social interaction between individuals. We present the results of a pilot study recently performed during a conference, and a subsequent preliminary data analysis, that provides an assessment of our method and highlights its versatility and applicability in many areas concerned with human dynamics.
Finite Lattice-Size Effects in MIMO Detection
Venue: arXiv cs.IT 2008
Year: 2008

Many powerful data detection algorithms employed in multiple-input multiple-output (MIMO) communication systems, such as sphere decoding (SD) and lattice-reduction (LR)-aided detection, were initially designed for infinite lattices. Detection in MIMO systems is, however, based on finite lattices. In this paper, we systematically study the consequences of finite lattice-size for the performance and complexity of MIMO detection algorithms formulated for infinite lattices. Specifically, we find, considering performance and complexity, that LR does not seem to offer advantages when used in conjunction with SD.
Wide spread spectrum watermarking with side information and interference cancellation
Venue: arXiv cs.MM 2008
Year: 2008

Nowadays, a popular method used for additive watermarking is wide spread spectrum. It consists in adding a spread signal into the host document. This signal is obtained by the sum of a set of carrier vectors, which are modulated by the bits to be embedded. To extract these embedded bits, weighted correlations between the watermarked document and the carriers are computed. Unfortunately, even without any attack, the obtained set of bits can be corrupted due to the interference with the host signal (host interference) and also due to the interference with the others carriers (inter-symbols interference (ISI) due to the non-orthogonality of the carriers). Some recent watermarking algorithms deal with host interference using side informed methods, but inter-symbols interference problem is still open. In this paper, we deal with interference cancellation methods, and we propose to consider ISI as side information and to integrate it into the host signal. This leads to a great improvement of extraction performance in term of signal-to-noise ratio and/or watermark robustness.
On the Fourier Spectra of the Infinite Families of Quadratic APN Functions
Venue: arXiv cs.IT 2008
Year: 2008

It is well known that a quadratic function defined on a finite field of odd degree is almost bent (AB) if and only if it is almost perfect nonlinear (APN). For the even degree case there is no apparent relationship between the values in the Fourier spectrum of a function and the APN property. In this article we compute the Fourier spectrum of the new quadranomial family of APN functions. With this result, all known infinite families of APN functions now have their Fourier spectra and hence their nonlinearities computed.
Automated Induction for Complex Data Structures
Venue: arXiv cs.LO 2008
Year: 2008

We propose a procedure for automated implicit inductive theorem proving for equational specifications made of rewrite rules with conditions and constraints. The constraints are interpreted over constructor terms (representing data values), and may express syntactic equality, disequality, ordering and also membership in a fixed tree language. Constrained equational axioms between constructor terms are supported and can be used in order to specify complex data structures like sets, sorted lists, trees, powerlists... Our procedure is based on tree grammars with constraints, a formalism which can describe exactly the initial model of the given specification (when it is sufficiently complete and terminating). They are used in the inductive proofs first as an induction scheme for the generation of subgoals at induction steps, second for checking validity and redundancy criteria by reduction to an emptiness problem, and third for defining and solving membership constraints. We show that the procedure is sound and refutationally complete. It generalizes former test set induction techniques and yields natural proofs for several non-trivial examples presented in the paper, these examples are difficult to specify and carry on automatically with related induction procedures.
An Introduction to Knowledge Management
Venue: arXiv cs.DB 2008
Year: 2008

Knowledge has been lately recognized as one of the most important assets of organizations. Managing knowledge has grown to be imperative for the success of a company. This paper presents an overview of Knowledge Management and various aspects of secure knowledge management. A case study of knowledge management activities at Tata Steel is also discussed
On the computational complexity of solving stochastic mean-payoff games
Venue: arXiv cs.GT 2008
Year: 2008

We consider some well-known families of two-player, zero-sum, perfect information games that can be viewed as special cases of Shapley's stochastic games. We show that the following tasks are polynomial time equivalent: - Solving simple stochastic games. - Solving stochastic mean-payoff games with rewards and probabilities given in unary. - Solving stochastic mean-payoff games with rewards and probabilities given in binary.
Cryptanalysis of the RSA-CEGD protocol
Venue: arXiv cs.CR 2008
Year: 2008

Recently, Nenadić et al. (2004) proposed the RSA-CEGD protocol for certified delivery of e-goods. This is a relatively complex scheme based on verifiable and recoverable encrypted signatures (VRES) to guarantee properties such as strong fairness and non-repudiation, among others. In this paper, we demonstrate how this protocol cannot achieve fairness by presenting a severe attack and also pointing out some other weaknesses.
Social networks that matter: Twitter under the microscope
Venue: arXiv cs.CY 2008
Year: 2008

Scholars, advertisers and political activists see massive online social networks as a representation of social interactions that can be used to study the propagation of ideas, social bond dynamics and viral marketing, among others. But the linked structures of social networks do not reveal actual interactions among people. Scarcity of attention and the daily rythms of life and work makes people default to interacting with those few that matter and that reciprocate their attention. A study of social interactions within Twitter reveals that the driver of usage is a sparse and hidden network of connections underlying the declared set of friends and followers.
Sélection de la structure d'un perceptron multicouches pour la réduction dun modèle de simulation d'une scierie
Venue: arXiv cs.NE 2008
Year: 2008

Simulation is often used to evaluate the relevance of a Directing Program of Production (PDP) or to evaluate its impact on detailed scénarii of scheduling. Within this framework, we propose to reduce the complexity of a model of simulation by exploiting a multilayer perceptron. A main phase of the modeling of one system using a multilayer perceptron remains the determination of the structure of the network. We propose to compare and use various pruning algorithms in order to determine the optimal structure of the network used to reduce the complexity of the model of simulation of our case of application: a sawmill.
Unary finite automata vs. arithmetic progressions
Venue: arXiv cs.CC 2008
Year: 2008

We point out a subtle error in the proof of Chrobak's theorem that every unary NFA can be represented as a union of arithmetic progressions that is at most quadratically large. We propose a correction for this and show how Martinez's polynomial time algorithm, which realizes Chrobak's theorem, can be made correct accordingly. We also show that Martinez's algorithm cannot be improved to have logarithmic space, unless L = NL.
Conceptual approach through an annotation process for the representation and the information contents enhancement in economic intelligence (EI)
Venue: arXiv cs.IR 2008
Year: 2008

In the era of the information society, the impact of the information systems on the economy of material and immaterial is certainly perceptible. With regards to the information resources of an organization, the annotation involved to enrich informational content, to track the intellectual activities on a document and to set the added value on information for the benefit of solving a decision-making problem in the context of economic intelligence. Our contribution is distinguished by the representation of an annotation process and its inherent concepts to lead the decisionmaker to an anticipated decision: the provision of relevant and annotated information. Such information in the system is made easy by taking into account the diversity of resources and those that are well annotated so formally and informally by the EI actors. A capital research framework consist of integrating in the decision-making process the annotator activity, the software agent (or the reasoning mechanisms) and the information resources enhancement.
Achievable Rates and Training Optimization for Fading Relay Channels with Memory
Venue: arXiv cs.IT 2008
Year: 2008

In this paper, transmission over time-selective, flat fading relay channels is studied. It is assumed that channel fading coefficients are not known a priori. Transmission takes place in two phases: network training phase and data transmission phase. In the training phase, pilot symbols are sent and the receivers employ single-pilot MMSE estimation or noncausal Wiener filter to learn the channel. Amplify-and-Forward (AF) and Decode-and-Forward (DF) techniques are considered in the data transmission phase and achievable rate expressions are obtained. The training period, and data and training power allocations are jointly optimized by using the achievable rate expressions. Numerical results are obtained considering Gauss-Markov and lowpass fading models. Achievable rates are computed and energy-per-bit requirements are investigated. The optimal power distributions among pilot and data symbols are provided.
Transmission Techniques for Relay-Interference Networks
Venue: arXiv cs.IT 2008
Year: 2008

In this paper we study the relay-interference wireless network, in which relay (helper) nodes are to facilitate competing information flows over a wireless network. We examine this in the context of a deterministic wireless interaction model, which eliminates the channel noise and focuses on the signal interactions. Using this model, we show that almost all the known schemes such as interference suppression, interference alignment and interference separation are necessary for relay-interference networks. In addition, we discover a new interference management technique, which we call interference neutralization, which allows for over-the-air interference removal, without the transmitters having complete access the interfering signals. We show that interference separation, suppression, and neutralization arise in a fundamental manner, since we show complete characterizations for special configurations of the relay-interference network.