Rapporti tecnici

Due to a printing problem, the revised version of our paper (Efficient cross-trees for external memory, in ``External Memory Algorithms and Visualization'', James Abello and Jeffrey Scott Vitter eds., DIMACS Series in Discrete Mathematics and Theoretical Computer Science, American Mathematical Society Press, Providence, RI, 1999) has been replaced by the (shorter) submitted version. In this technical report, we include the revised version that has not been published by mistake. In particular, we describe efficient methods for organizing and maintaining large multidimensional data sets in external memory. This is particular important as access to external memory is currently several order of magnitudes slower than access to main memory, and current technology advances are likely to make this gap even wider. We focus particularly on multidimensional data sets which must be kept simultaneously sorted under several total orderings: these orderings may be defined by the user, and may also be changed dynamically by the user throughout the lifetime of the data structures, according to the application at hand. Besides standard insertions and deletions of data, our proposed solution can perform efficiently {\em split\/} and {\em concatenate\/} operations on the whole data sets according to any ordering. This allows the user: (1)~to dynamically rearrange any ordering of a segment of data, in a time that is faster than recomputing the new ordering from scratch; (2)~to efficiently answer queries related to the data contained in a particular range of the current orderings. Our solution fully generalizes the notion of B-trees to higher dimensions by carefully combining space-driven and data-driven partitions. Balancing is easy as we introduce a new multidimensional data structure, {\em the cross-tree}, that is the cross product of balanced trees. As a result, the cross-tree is competitive with other popular index data structures that require linear space (including k-d trees, quad-trees, grid files, space filling curves, hB-trees, and R-trees).

We propose new local search algorithms for minimum makespan machine scheduling problems, which perform multiple exchanges of jobs among machines. Inspired by the work of Thompson and Orlin (1989) on cyclic transfer neighborhood structures, we model multiple exchanges of jobs as special disjoint cycles and paths in a suitably defined improvement graph, by extending definitions and properties introduced in the context of VRP (Thompson and Psaraftis, 1993) and of CMST (Ahuja, Orlin and Sharma, 1998). Several algorithms for searching the neighborhood are suggested. We report the results of a wide computational experimentation, on different families of benchmark instances, performed for the case of identical machines. The minimum makespan machine scheduling problem with identical machines has been selected as a case study to perform a comparison among the alternative algorithms, and to discover families of instances for which the proposed neighborhood may be promising in practice. The obtained results are very interesting. On some families of instances, which are very hard to solve exactly, the most promising multi-exchange algorithms proved to dominate, in gap and in time, competitive benchmark heuristics.

We study a class of generalized bundle methods where the stabilizing term can be any closed convex function satisfying certain properties. This setting covers several algorithms from the literature that have been so far regarded as distinct. Under different hypothesis on the stabilizing term and/or the function to be minimized, we prove finite termination, asymptotic convergence and finite convergence to an optimal point, with or without limits on the number of serious steps and/or requiring the proximal parameter to go to infinity. The convergence proofs are conceived for leaving a high degree of freedom in the crucial implementative features of the algorithm, i.e., the management of the bundle of subgradients (b-strategy) and of the proximal parameter (t-strategy). We extensively exploit a dual view of bundle methods, which are shown to be a dual ascent approach to one nonlinear problem in an appropriate dual space, where nonlinear subproblems are approximately solved at each step with an inner linearization approach. This allows to precisely characterize the changes in the subproblems during the serious steps, since the dual problem is not tied to the local concept of e-subdifferential. For some of the proofs, a generalization of inf-compactness, called *-compactness, is required; this concept is related to that of asymptotically well-behaved function.

In this paper we present heuristic techniques for the reduction of the bandwidth of a sparse matrix as well as for the reduction of the cost of the associated Cholesky factorization. Our algorithms are inspired by the Spectral Method of Barnard, Pothen and Simon [BPS95] which derives a permutation for reducing the envelope-size of a sparse matrix by computing the second eigenvector of the associated Laplacian matrix. Two main modifications of that method are proposed and tested. The first is based on the experimental observation that it is often preferable to perform only few iterations of an iterative method converging to the second eigenvector; the second is the introduction of a weighted Laplacian. These simple ideas allows us to obtain a family of spectral methods that have been carefully tested on a set of matrices whose size range from few hundred to one-million.

Consider the following two problems. Problem 1. We are given a collection of 2-tuples T={T_1,...,T_k} where each T_i=(T_i^1,T_i^2), for two strings T_i^1 and T_i^2. This collection may be preprocessed. A query takes as input a pattern tuple P=(P^1,P^2) and the problem is to determine all tuples T_i for which P^1 is a substring of T_i^1 and P^2 is a substring of $T_i^2. Problem 2. We are given a collection of documents D={D_1,...,D_k} that may be preprocessed. Each query is a pair of pattern strings p_1 and p_2, and the goal is to determine the set of all documents that contain both patterns as substrings. In this paper, we show that these two problems are related and make progress on solving them efficiently by proposing the first non trivial results.

The uniqueness of the KKT multipliers of a nonlinear program has been studied in a well-known paper by Kyparisis. In the first part of this note, we show that the characterization obtained in that paper does not provide a satisfactory result for the multiobjective case. Thus, we introduce a new regularity condition, which involves also the objective functions, and we show that it is necessary and sufficient in order to have unique KKT multipliers. Moreover, we use this condition to refine a second order necessary optimality condition, which has been obtained in a recent paper.

The distributed coordination and control of a set of autonomous, mobile agents/ robots is a widely studied topic in a variety of fields, such as engineering, artificial intelligence, and artificial life. In the majority of the studies, the problem has been approached from an empirical point of view. A different approach to the problem has been introduced in [6], where the authors analyzed the distributed coordination and control of a set of autonomous, mobile robots from a computational point of view. With this purpose, they defined a model where the world was inhabited by a set of totally autonomous, mobile, memoryless entities that were requested to form a generic pattern. From that study, it turned out that whether or not such a task could be accomplished depended on the amount of common knowledge the robots had; in particular, on the direction and orientation of the local coordinate system. Among the issues left open was which kind of patterns a set of such mobile units can form when they are even in number and agree on the orientation and direction of only one axis. This paper answers that question.

The definition of SOS formats ensuring that bisimilarity on closed terms is a congruence has received much attention in the last two decades. For dealing with open system specifications, the congruence is usually lifted from closed terms to open terms by instantiating the free variables in all possible ways; the only alternatives considered in the literature relying on Larsen and Xinxin's context systems and Rensink's conditional transition systems. We propose a different approach based on tile logic, where both closed and open terms are managed analogously. In particular, we analyze the `bisimilarity as congruence' property for several tile formats that accomplish different concepts of subterm sharing.

Abstract La crisi di dentita'in atto nella nostra societa'dovuta a motivi politici ed economici, e' stata ulteriormente evidenziata nel processo contemporaneo di costruzione dell'identita' nella cultura della simulazione; le processo va inserito nel contesto piu' ampio di confronto, ed ormai di lenta ma continua erosione dei confini tra il reale e il virtuale, l'animato e l'inanimato,l'io unitario e l'io multiplo. Vengono esposte queste nuove idee sull'identita' umana che riguardano l'insieme dei concetti raccolti sotto il nome di "Postmodernità": concetti quali decentrato, fluido, opaco, non lineare. Si traccia una breve storia degli argomenti dell'informatica che hanno avuto un impatto maggiore con la nostra cultura, quali Intelligenza artificiale, Vita artificiale, Internet. Non si entra nei dettagli tecnici di tali tematiche, ma si cerca di approfondire le idee ed i concetti su cui si basano, e le conseguenze che hanno avuto nel pensiero umano e nella cultura della vita quotidiana. Si considerano cioe' i vari argomenti e materie di ricerca che hanno contribuito alla nascita e sviluppo di un nuovo filone di studio che prende nome di "Filosofia del computer".

There is an upsurging interest in designing succinct data structures for basic searching problems (see [Munro99] and references therein). The motivation has to be found in the exponential increase of electronic data nowadays available which is even surpassing the significant increase in memory and disk storage capacities of current computers. Space reduction is an attractive issue because it is also intimately related to performance improvements as noted by several authors (e.g. Knuth [knuth3], Bentley [bentley]). In designing these implicit data structures the goal is to reduce as much as possible the auxiliary information kept together with the input data without introducing a significant slowdown in the final query performance. Yet input data are represented in their entirety thus taking no advantage of possible repetitiveness into them. The importance of those issues is well known to programmers who typically use various tricks to squeeze data as much as possible and still achieve good query performance. Their approaches, thought, boil down to heuristics whose effectiveness is witnessed only by experimentation. In this paper, we address the issue of compressing and indexing data by studying it in a theoretical framework. We devise a novel data structure for indexing and searching whose space occupancy is a function of the entropy of the underlying data set. The novelty resides in the careful combination of a compression algorithm, proposed by Burrows-Wheeler [bw], with the structural properties of a well known indexing tool, the Suffix Array [MM93]. We call the data structure opportunistic since its space occupancy is decreased when the input is compressible at no significant slowdown in the query performance and without any assumption on a particular fixed distribution. More precisely, its space occupancy is optimal in a information-content sense because a text $T[1,u]$ is stored using $O(k(T)) + o(1)$ bits per input symbol, where $k(T)$ is the $k$th order entropy of $T$ (the bound holds for any fixed $k$). Given an arbitrary string $P[1,p]$, the opportunistic data structure allows to search for the $occ$ occurrences of $P$ in $T$ requiring $O(p + occ \log^\epsilon u)$ time complexity (for any fixed $\epsilon >0$). If data are non compressible, then we achieve the best space bound currently known [GV00]; otherwise our solution improves the succinct suffix array in [GV00] and the classical suffix tree and suffix array data structures either in space or in query time complexity or both. It was a belief [Witten:1999:MGC] that some space overhead should be paid to use full-text indices (i.e. suffix trees or suffix arrays) with respect to the word-based indices (i.e. inverted lists). The results in this paper show that no space overhead is needed at all, and as an application we improve space and query time complexity of the well-known Glimpse tool [glimpse]. We finally investigate the modifiability of our opportunistic data structure by studying how to choreograph its basic ideas with a dynamic setting thus achieving effective searching and updating time bounds.

Multi-algebras allow to model nondeterminism in an algebraic framework by interpreting operators as functions from individual arguments to sets of possible results. Starting from a functorial presentation of multi-algebras based on "gs-monoidal theories" we argue that specifications for multi-algebras should be based on the notion of term graphs instead of on standard terms. We consider the simplest case of (term graph) equational specification, showing that it enjoys an unrestricted form of substitutivity. We discuss the expressive power of equational specification for multi-algebras, and we sketch possible extensions of the calculus.

We propose a functorial concurrent semantics for Petri nets extended with read and inhibitor arcs, that we call inhibitor nets. Along the lines of the seminal work of Winskel on safe nets and extending a previous work in [1] for nets with read arcs, the truly concurrent semantics is given at a categorical level via a chain of functors leading from the category SW-IN of semi-weighted inhibitor nets to the category Dom of finitary prime algebraic domains (equivalent to the category PES of prime event structures). As an intermediate semantic model, we introduce inhibitor event structures, an extension of prime event structures able to faithfully capture the dependencies among events which arise in the presence of read and inhibitor arcs. [1] P. Baldan, A. Corradini, U. Montanari "An Event Structure Semantics for P/T Contextual Nets: Asymmetric Event Structures" FoSSaCS '98 Conference Proceedings, Springer LNCS vol. 1378, 1998, pp. 63-80.

Recently introduced pseudocubes and SPP forms have made possible to represent Boolean functions with a more compact expression than in the SP form. In this report we present new properties of pseudocubes. In order to study and manipulate pseudocubes we count and characterize sub-pseudocubes. Letting P be a pseudocube, we derive a normal form and the canonical expression of any sub-pseudoproduct of P.

We present an analytic evaluation of the run-time behavior of the C4.5 algorithm which highlights some efficiency improvements. We have implemented a more efficient version of the algorithm, called EC4.5, that improves on C4.5 by adopting the best among three strategies at each node construction. The first strategy uses a binary search of thresholds instead of the linear search of C4.5. The second strategy adopts a counting sort method instead of the quicksort of C4.5. The third strategy uses a main-memory version of the RainForest algorithm for constructing decision trees. Our implementation computes the same decision trees as C4.5 with a performance gain of up to 5 times.

In this paper we introduce SFPM, a category of SFP domains which provides very satisfactory domain-models, i.e. partializations, of separable Stone spaces (2-Stone spaces). More specifically, SFPM is a subcategory of SFPep, closed under direct limits as well as many constructors, such as lifting, sum, product and Plotkin powerdomain. SFPM is structurally well behaved, in the sense that the functor MAX, which associates to each object of SFPM the Stone space of its maximal elements, is compositional with respect to the constructors above, and omega-continuous. A correspondence can be established between these constructors over SFPM and appropriate constructors on Stone spaces, whereby SFP domain-models of Stone spaces defined as solutions of a vast class of recursive equations in 2-Stone, can be obtained simply by solving the corresponding equations in SFPM. Moreover any continuous function between two 2-Stone spaces can be extended to a continuous function between any two SFPM domain-models of the original spaces. The category SFPM does not include all the SFP's with a 2-Stone space of maximal elements (CSFP's). We show that the CSFP's can be characterized precisely as suitable retracts of SFPM objects. Then the results proved for SFPM easily extends to the wider category having CSFP's as objects. Using SFPM , we explain two classical partializations of the space of finitary hypersets (the hyperuniverse N-omega [Forti, Honsell, Lenisa]) based on SFP domains (see [Abramsky], [Mislove, Moss, Oles]). We also show that these two domains are not isomorphic, thus providing a negative answer to a problem raised in [Mislove, Moss,Oles].

Most often, space is the scarce resource in Bus Depots located in congested urban areas: vehicles arriving at the end of their trips are packed together in a rather small space. That implies that, when a vehicle has to leave to start a new trip, most often, other vehicles have to be moved to clear the way. Here a new model, based on "Min Non Crossing Matching" and "Generalized Assignment", is presented to allocate parking spaces to vehicles in a Depot in order to minimize the shunting cost. The results obtained applying our approach to a real life case are discussed.

The problem of simultaneously locating obnoxious facilities and routing obnoxious materials between a set of built-up areas and the facilities is addressed. Obnoxious facilities are those facilities which cause nuisance to people as well as to the environment i.e. dump sites, chemical industrial plants, electric power supplier networks, nuclear reactors and so on. A discrete combined location-routing model, which we refer to as Obnoxious Facility Location and Routing model (OFLR), is defined. OFLR is a np-hard problem for which a Lagrangean heuristic approach is presented. The Lagrangean relaxation proposed allows to decompose OFLR into a Location subproblem and a Routing subproblem; such subproblems are then strenghtened by adding suitable inequalities. Based on this Lagrangean relaxation two simple Lagrangean heuristics are provided. An effective Branch and Bound algorithm is then presented, which aims at reducing the gap between the above mentioned lower and upper bounds. Our Branch and Bound exploits the information gathered while going down in the enumeration tree in order to solve efficiently the subproblems related to other nodes. This is accomplished by using a bundle method to solve at each node the Lagrangean dual. Some variants of the proposed Branch and Bound method are defined in order to identify the best strategy for different classes of instances. A comparison of computational results relative to these variants is presented.

An effective Branch and Bound algorithm based on Lagrangean heuristic is presented, which aims at reducing the gap between the lower and upper bounds. The Branch and Bound method proposed exploits the information gathered while going down in the enumeration tree in order to solve efficiently the subproblems related to other nodes. This is accomplished by using a bundle method to solve at each node the Lagrangean dual. A discrete combined location-routing model, which we refer to as Obnoxious Facility Location and Routing model (OFLR), is used as a benchmark to validate the efficiency of the method proposed. Such model simultaneously locates obnoxious facilities and routes obnoxious materials between a set of built-up areas and the facilities. Obnoxious facilities are those facilities which cause nuisance to people as well as to the environment i.e. dump sites, chemical industrial plants, electric power supplier networks, nuclear reactors and so on. OFLR is a particular case of the Obnoxious Network Design problem which occurs when also an obnoxious network has to be designed such as the case of electric power supplier networks. These are meaningful problems given the industrial development and the increasing importance of environmental issues in our society. The use of the B&B to solve this latter problem is under development.

Over the past few years, the focus of robotic design has been moving from a scenario where few, specialized (and expensive) units were used to solve a variety of tasks, to a scenario where many, general purpose (and cheap) units were used to achieve some common goal. Consequently, part of the focus has been to better understand how to efficiently coordinate and control a set of such