OpenRaiser/Intern-Atlas huggingface dataset:
Essential arity gap of Boolean functions
Venue: arXiv cs.DM 2008
Year: 2008

We investigate the Boolean functions with essential arity gap 2. We use Full Conjunctive Normal Forms instead of Zhegalkin's polynomials, which allow us to simplify the proofs and to obtain several combinatorial results, concerning the Boolean functions with a given arity gap.
Tableau-based decision procedure for the multi-agent epistemic logic with operators of common and distributed knowledge
Venue: arXiv cs.LO 2008
Year: 2008

We develop an incremental-tableau-based decision procedure for the multi-agent epistemic logic MAEL(CD) (aka S5_n (CD)), whose language contains operators of individual knowledge for a finite set Ag of agents, as well as operators of distributed and common knowledge among all agents in Ag. Our tableau procedure works in (deterministic) exponential time, thus establishing an upper bound for MAEL(CD)-satisfiability that matches the (implicit) lower-bound known from earlier results, which implies ExpTime-completeness of MAEL(CD)-satisfiability. Therefore, our procedure provides a complexity-optimal algorithm for checking MAEL(CD)-satisfiability, which, however, in most cases is much more efficient. We prove soundness and completeness of the procedure, and illustrate it with an example.
Light Logics and the Call-by-Value Lambda Calculus
Venue: arXiv cs.LO 2008
Year: 2008

The so-called light logics have been introduced as logical systems enjoying quite remarkable normalization properties. Designing a type assignment system for pure lambda calculus from these logics, however, is problematic. In this paper we show that shifting from usual call-by-name to call-by-value lambda calculus allows regaining strong connections with the underlying logic. This will be done in the context of Elementary Affine Logic (EAL), designing a type system in natural deduction style assigning EAL formulae to lambda terms.
A Computational Study of Genetic Crossover Operators for Multi-Objective Vehicle Routing Problem with Soft Time Windows
Venue: arXiv cs.AI 2008
Year: 2008

The article describes an investigation of the effectiveness of genetic algorithms for multi-objective combinatorial optimization (MOCO) by presenting an application for the vehicle routing problem with soft time windows. The work is motivated by the question, if and how the problem structure influences the effectiveness of different configurations of the genetic algorithm. Computational results are presented for different classes of vehicle routing problems, varying in their coverage with time windows, time window size, distribution and number of customers. The results are compared with a simple, but effective local search approach for multi-objective combinatorial optimization problems.
The Semiotic Machine
Venue: arXiv cs.HC 2008
Year: 2008

A semiotic model of the user interface in human-computer interaction. Algorithmic sign, semotics, algorithmic art.
A framework for the interactive resolution of multi-objective vehicle routing problems
Venue: arXiv cs.AI 2008
Year: 2008

The article presents a framework for the resolution of rich vehicle routing problems which are difficult to address with standard optimization techniques. We use local search on the basis on variable neighborhood search for the construction of the solutions, but embed the techniques in a flexible framework that allows the consideration of complex side constraints of the problem such as time windows, multiple depots, heterogeneous fleets, and, in particular, multiple optimization criteria. In order to identify a compromise alternative that meets the requirements of the decision maker, an interactive procedure is integrated in the resolution of the problem, allowing the modification of the preference information articulated by the decision maker. The framework is prototypically implemented in a computer system. First results of test runs on multiple depot vehicle routing problems with time windows are reported.
Low ML-Decoding Complexity, Large Coding Gain, Full-Rate, Full-Diversity STBCs for 2 X 2 and 4 X 2 MIMO Systems
Venue: arXiv cs.IT 2008
Year: 2008

This paper (Part of the content of this manuscript has been accepted for presentation in IEEE Globecom 2008, to be held in New Orleans) deals with low maximum likelihood (ML) decoding complexity, full-rate and full-diversity space-time block codes (STBCs), which also offer large coding gain, for the 2 transmit antenna, 2 receive antenna ($2\times 2$) and the 4 transmit antenna, 2 receive antenna ($4\times 2$) MIMO systems. Presently, the best known STBC for the $2\times2$ system is the Golden code and that for the $4\times2$ system is the DjABBA code. Following the approach by Biglieri, Hong and Viterbo, a new STBC is presented in this paper for the $2\times 2$ system. This code matches the Golden code in performance and ML-decoding complexity for square QAM constellations while it has lower ML-decoding complexity with the same performance for non-rectangular QAM constellations. This code is also shown to be \emph{information-lossless} and \emph{diversity-multiplexing gain} (DMG) tradeoff optimal. This design procedure is then extended to the $4\times 2$ system and a code, which outperforms the DjABBA code for QAM constellations with lower ML-decoding complexity, is presented. So far, the Golden code has been reported to have an ML-decoding complexity of the order of $M^4$ for square QAM of size $M$. In this paper, a scheme that reduces its ML-decoding complexity to $M^2\sqrt{M}$ is presented.
Improving Local Search for Fuzzy Scheduling Problems
Venue: arXiv cs.AI 2008
Year: 2008

The integration of fuzzy set theory and fuzzy logic into scheduling is a rather new aspect with growing importance for manufacturing applications, resulting in various unsolved aspects. In the current paper, we investigate an improved local search technique for fuzzy scheduling problems with fitness plateaus, using a multi criteria formulation of the problem. We especially address the problem of changing job priorities over time as studied at the Sherwood Press Ltd, a Nottingham based printing company, who is a collaborator on the project.
Network Protection Codes Against Link Failures Using Network Coding
Venue: arXiv cs.IT 2008
Year: 2008

Protecting against link failures in communication networks is essential to increase robustness, accessibility, and reliability of data transmission. Recently, network coding has been proposed as a solution to provide agile and cost efficient network protection against link failures, which does not require data rerouting, or packet retransmission. To achieve this, separate paths have to be provisioned to carry encoded packets, hence requiring either the addition of extra links, or reserving some of the resources for this purpose. In this paper, we propose network protection codes against a single link failure using network coding, where a separate path using reserved links is not needed. In this case portions of the link capacities are used to carry the encoded packets. The scheme is extended to protect against multiple link failures and can be implemented at an overlay layer. Although this leads to reducing the network capacity, the network capacity reduction is asymptotically small in most cases of practical interest. We demonstrate that such network protection codes are equivalent to error correcting codes for erasure channels. Finally, we study the encoding and decoding operations of such codes over the binary field.
Domain Specific Software Architecture for Design Center Automation
Venue: arXiv cs.SE 2008
Year: 2008

Domain specific software architecture aims at software reuse through construction of domain architecture reference model. The constructed reference model presents a set of individual components and their interaction points. When starting on a new large software project, the design engineer starts with pre-constructed model, which can be easily browsed and picks up opportunities of use in the new solution design. This report discusses application of domain reference design methods by deriving domain specific reference architecture for a product ordering system in a design center. The product in this case is instock and special order blinds from different manufacturers in a large supply store. The development of mature domain specific reference software architecture for this domain is not the objective of this report. However, this report would like to capture the method used in one such process and that is the primary concern of this report. This report lists subjective details of such a process applied to the domain of ordering custom and instock blinds from a large home construction and goods supply store. This report also describes the detailed process of derivation of knowledge models, unified knowledge models and the reference architecture for this domain. However, this domain model is only partially complete which may not be used for any real applications. This report is a result of a course project undertaken while studying this methodology.
Improved Smoothed Analysis of the k-Means Method
Venue: arXiv cs.DS 2008
Year: 2008

The k-means method is a widely used clustering algorithm. One of its distinguished features is its speed in practice. Its worst-case running-time, however, is exponential, leaving a gap between practical and theoretical performance. Arthur and Vassilvitskii (FOCS 2006) aimed at closing this gap, and they proved a bound of $\poly(n^k, σ^{-1})$ on the smoothed running-time of the k-means method, where n is the number of data points and $σ$ is the standard deviation of the Gaussian perturbation. This bound, though better than the worst-case bound, is still much larger than the running-time observed in practice. We improve the smoothed analysis of the k-means method by showing two upper bounds on the expected running-time of k-means. First, we prove that the expected running-time is bounded by a polynomial in $n^{\sqrt k}$ and $σ^{-1}$. Second, we prove an upper bound of $k^{kd} \cdot \poly(n, σ^{-1})$, where d is the dimension of the data space. The polynomial is independent of k and d, and we obtain a polynomial bound for the expected running-time for $k, d \in O(\sqrt{\log n/\log \log n})$. Finally, we show that k-means runs in smoothed polynomial time for one-dimensional instances.
Dynamic index selection in data warehouses
Venue: arXiv cs.DB 2008
Year: 2008

Analytical queries defined on data warehouses are complex and use several join operations that are very costly, especially when run on very large data volumes. To improve response times, data warehouse administrators casually use indexing techniques. This task is nevertheless complex and fastidious. In this paper, we present an automatic, dynamic index selection method for data warehouses that is based on incremental frequent itemset mining from a given query workload. The main advantage of this approach is that it helps update the set of selected indexes when workload evolves instead of recreating it from scratch. Preliminary experimental results illustrate the efficiency of this approach, both in terms of performance enhancement and overhead.
Knowledge and Metadata Integration for Warehousing Complex Data
Venue: arXiv cs.DB 2008
Year: 2008

With the ever-growing availability of so-called complex data, especially on the Web, decision-support systems such as data warehouses must store and process data that are not only numerical or symbolic. Warehousing and analyzing such data requires the joint exploitation of metadata and domain-related knowledge, which must thereby be integrated. In this paper, we survey the types of knowledge and metadata that are needed for managing complex data, discuss the issue of knowledge and metadata integration, and propose a CWM-compliant integration solution that we incorporate into an XML complex data warehousing framework we previously designed.
On (Omega-)Regular Model Checking
Venue: arXiv cs.LO 2008
Year: 2008

Checking infinite-state systems is frequently done by encoding infinite sets of states as regular languages. Computing such a regular representation of, say, the set of reachable states of a system requires acceleration techniques that can finitely compute the effect of an unbounded number of transitions. Among the acceleration techniques that have been proposed, one finds both specific and generic techniques. Specific techniques exploit the particular type of system being analyzed, e.g. a system manipulating queues or integers, whereas generic techniques only assume that the transition relation is represented by a finite-state transducer, which has to be iterated. In this paper, we investigate the possibility of using generic techniques in cases where only specific techniques have been exploited so far. Finding that existing generic techniques are often not applicable in cases easily handled by specific techniques, we have developed a new approach to iterating transducers. This new approach builds on earlier work, but exploits a number of new conceptual and algorithmic ideas, often induced with the help of experiments, that give it a broad scope, as well as good performances.
An Energy-Aware On-Demand Routing Protocol for Ad-Hoc Wireless Networks
Venue: arXiv cs.NI 2008
Year: 2008

An ad-hoc wireless network is a collection of nodes that come together to dynamically create a network, with no fixed infrastructure or centralized administration. An ad-hoc network is characterized by energy constrained nodes, bandwidth constrained links and dynamic topology. With the growing use of wireless networks (including ad-hoc networks) for real-time applications, such as voice, video, and real-time data, the need for Quality of Service (QoS) guarantees in terms of delay, bandwidth, and packet loss is becoming increasingly important. Providing QoS in ad-hoc networks is a challenging task because of dynamic nature of network topology and imprecise state information. Hence, it is important to have a dynamic routing protocol with fast re-routing capability, which also provides stable route during the life-time of the flows. In this thesis, we have proposed a novel, energy aware, stable routing protocol named, Stability-based QoS-capable Ad-hoc On-demand Distance Vector (SQ-AODV), which is an enhancement of the well-known Ad-hoc On-demand Distance Vector (AODV) routing protocol for ad-hoc wireless networks. SQ-AODV utilizes a cross-layer design approach in which information about the residual energy of a node is used for route selection and maintenance. An important feature of SQ-AODV protocol is that it uses only local information and requires no additional communication or co-operation between the network nodes. SQ-AODV possesses a make-before-break re-routing capability that enables near-zero packet drops and is compatible with the basic AODV data formats and operation, making it easy to adopt in ad-hoc networks.
Structures de réalisabilité, RAM et ultrafiltre sur N
Venue: arXiv cs.LO 2008
Year: 2008

We show how to transform into programs the proofs in classical Analysis which use the existence of an ultrafilter on the integers. The method mixes the classical realizability introduced by the author, with the "forcing" of P. Cohen. The programs we obtain, use read and write instructions in random access memory.
NP-Completeness of Hamiltonian Cycle Problem on Rooted Directed Path Graphs
Venue: arXiv cs.DM 2008
Year: 2008

The Hamiltonian cycle problem is to decide whether a given graph has a Hamiltonian cycle. Bertossi and Bonuccelli (1986, Information Processing Letters, 23, 195-200) proved that the Hamiltonian Cycle Problem is NP-Complete even for undirected path graphs and left the Hamiltonian cycle problem open for directed path graphs. Narasimhan (1989, Information Processing Letters, 32, 167-170) proved that the Hamiltonian Cycle Problem is NP-Complete even for directed path graphs and left the Hamiltonian cycle problem open for rooted directed path graphs. In this paper we resolve this open problem by proving that the Hamiltonian Cycle Problem is also NP-Complete for rooted directed path graphs.
A Simple Framework to Typify Social Bibliographic Communities
Venue: arXiv cs.DL 2008
Year: 2008

Social Communities in bibliographic databases exist since many years, researchers share common research interests, and work and publish together. A social community may vary in type and size, being fully connected between participating members or even more expressed by a consortium of small and individual members who play individual roles in it. In this work, we focus on social communities inside the bibliographic database DBLP and characterize communities through a simple typifying description model. Generally, we understand a publication as a transaction between the associated authors. The idea therefore is to concern with directed associative relationships among them, to decompose each pattern to its fundamental structure, and to describe the communities by expressive attributes. Finally, we argue that the decomposition supports the management of discovered structures towards the use of adaptive-incremental mind-maps.
An Efficient Algorithm for Cooperative Spectrum Sensing in Cognitive Radio Networks
Venue: arXiv cs.IT 2008
Year: 2008

We consider the problem of Spectrum Sensing in Cognitive Radio Systems. We have developed a distributed algorithm that the Secondary users can run to sense the channel cooperatively. It is based on sequential detection algorithms which optimally use the past observations. We use the algorithm on secondary users with energy detectors although it can be used with matched filter and other spectrum sensing algorithms also. The algorithm provides very low detection delays and also consumes little energy. Furthermore it causes low interference to the primary users. We compare this algorithm to several recently proposed algorithms and show that it detects changes in spectrum faster than these algorithms and uses significantly less energy.
A Geometrical Description of the SINR Region of the Gaussian Interference Channel: the two and three-user case
Venue: arXiv cs.IT 2008
Year: 2008

This paper addresses the problem of computing the achievable rates for two (and three) users sharing a same frequency band without coordination and thus interfering with each other. It is thus primarily related to the field of cognitive radio studies as we look for the achievable increase in the spectrum use efficiency. It is also strongly related to the long standing problem of the capacity region of a Gaussian interference channel (GIC) because of the assumption of no user coordination (and the underlying assumption that all signals and interferences are Gaussian). We give a geometrical description of the SINR region for the two-user and three-user channels. This geometric approach provides a closed-form expression of the capacity region of the two-user interference channel and an insightful of known optimal power allocation scheme.
A Control Variate Approach for Improving Efficiency of Ensemble Monte Carlo
Venue: arXiv cs.CE 2008
Year: 2008

In this paper we present a new approach to control variates for improving computational efficiency of Ensemble Monte Carlo. We present the approach using simulation of paths of a time-dependent nonlinear stochastic equation. The core idea is to extract information at one or more nominal model parameters and use this information to gain estimation efficiency at neighboring parameters. This idea is the basis of a general strategy, called DataBase Monte Carlo (DBMC), for improving efficiency of Monte Carlo. In this paper we describe how this strategy can be implemented using the variance reduction technique of Control Variates (CV). We show that, once an initial setup cost for extracting information is incurred, this approach can lead to significant gains in computational efficiency. The initial setup cost is justified in projects that require a large number of estimations or in those that are to be performed under real-time constraints.
A Local Clustering Algorithm for Massive Graphs and its Application to Nearly-Linear Time Graph Partitioning
Venue: arXiv cs.DS 2008
Year: 2008

We study the design of local algorithms for massive graphs. A local algorithm is one that finds a solution containing or near a given vertex without looking at the whole graph. We present a local clustering algorithm. Our algorithm finds a good cluster--a subset of vertices whose internal connections are significantly richer than its external connections--near a given vertex. The running time of our algorithm, when it finds a non-empty local cluster, is nearly linear in the size of the cluster it outputs. Our clustering algorithm could be a useful primitive for handling massive graphs, such as social networks and web-graphs. As an application of this clustering algorithm, we present a partitioning algorithm that finds an approximate sparsest cut with nearly optimal balance. Our algorithm takes time nearly linear in the number edges of the graph. Using the partitioning algorithm of this paper, we have designed a nearly-linear time algorithm for constructing spectral sparsifiers of graphs, which we in turn use in a nearly-linear time algorithm for solving linear systems in symmetric, diagonally-dominant matrices. The linear system solver also leads to a nearly linear-time algorithm for approximating the second-smallest eigenvalue and corresponding eigenvector of the Laplacian matrix of a graph. These other results are presented in two companion papers.
More on Combinatorial Batch Codes
Venue: arXiv cs.CR 2008
Year: 2008

Paterson, Stinson and Wei \cite{PSW} introduced Combinatorial batch codes, which are combinatorial description of Batch code. Batch codes were first presented by Ishai, Kushilevita, Ostrovsky and Sahai \cite{IKOS} in STOC'04. In this paper we answer some of the questions put forward by Paterson, Stinson and Wei and give some results for the general case $t>1$ which were not studied by the authors.
Ten weeks in the life of an eDonkey server
Venue: arXiv cs.NI 2008
Year: 2008

This paper presents a capture of the queries managed by an eDonkey server during almost 10 weeks, leading to the observation of almost 9 billion messages involving almost 90 million users and more than 275 million distinct files. Acquisition and management of such data raises several challenges, which we discuss as well as the solutions we developed. We obtain a very rich dataset, orders of magnitude larger than previously avalaible ones, which we provide for public use. We finally present basic analysis of the obtained data, which already gives evidence of non-trivial features.