Technical reports

Shortest path problems are among the most studied network flow problems, with interesting applications in various fields. Mainly in large scale transportation systems, a sequence of shortest path problems needs often to be solved, where the (k+1)-th problem differs only slightly from the k-th one. In that context, a promising line of research is to study efficient reoptimization approaches, able to exploit useful information from one shortest path computation to the next one. In this work, we shall focus on the change of the origin node in the shortest path problem to be solved. After reviewing the classical (dual) algorithms described in the literature sofar, which essentially show a Dijkstra's like behavior, a new dual approach will be proposed, which could be particularly promising in practice.

In this work we propose a model to learn conceptual descriptions of categories from precategorized texts. The model is general and parametric, and it captures most of the statistical approaches to classification as well as allowing the definition of more symbolic learning schemes. The algorithm scheme has been instantiated into three different algorithms, which have been implemented and tested on a collection of documents obtained from the Web. As a possible application of the descriptions obtained, classification was done on a test set. Results are somewhat surprising, and stand in contrast with most experiments done in literature, possibly giving hints about a different research direction.

We address the problem of scheduling independent jobs to identical parallel machines in order to minimize the completion time (makespan). This is a hard problem, for which both constructive and improvement heuristics have been proposed. We describe new local search algorithms, whose neighborhood structure is based on multiple exchanges of jobs among machines. Inspired by the work of Thompson and Orlin (1989) on cyclic transfer neighborhood structures, in these algorithms multiple exchanges are modelled in terms of ``disjoint cycles'' on suitably defined improvement graphs, and improvement moves are obtained by heuristically constructing special disjoint cycles in such auxiliary graphs. The algorithms have been tested on benchmark instances, characterized by uniformly distributed processing times, and on a new class of "highly non-uniform" instances, generated by the authors, which seem to be, in some cases, more difficult than the "uniform" ones. The algorithms have shown a potential both for generating highly accurate solutions when the running time is not an issue, and for rapidly obtaining good solutions when the running time has to be kept small.

The purpose of this work is to establish some foundational ground for the logics that can be used to reason on distributed systems where asyncronous message passing is the only possible mechanism for communication, e.g. distributed workflow systems. We define adtl, a logic with modalities for time and locality. We introduce a complete and decidable axiom system, which characterizes the class of structures that reflect the nature of the causal relation when communications are asynchronous.

We present an event structure semantics for contextual nets, an extension of P/T Petri nets where transitions can check for the presence of tokens without consuming them (read-only operations). A basic role is played by asymmetric event structures, a generalization of Winskel's prime event structures where symmetric conflict is replaced by a relation modelling asymmetric conflict or weak causality, used to represent a new kind of dependency between events arising in contextual nets. Extending Winskel's seminal work on safe nets, the truly concurrent event based semantics of contextual nets is given at categorical level via a chain of coreflections leading from the category SW-CN of semi-weighted contextual nets to the category DOM of finitary prime algebraic domains. First an unfolding construction generates from a contextual net a corresponding occurrence contextual net, from where an asymmetric event structure is extracted. Then the configurations of the asymmetric event structure, endowed with a suitable order, are shown to form a finitary prime algebraic domain. We also investigate the relation between the proposed unfolding semantics and several deterministic process semantics for contextual nets in the literature. In particular, the domain obtained via the unfolding is characterized as the collection of the deterministic processes of the net endowed with a kind of prefix ordering.

The new concept of pseudo-product as extension of the concept of product has been introduced in a recent paper by Luccio and Pagli. An arbitrary Boolean function can be expressed as a sum of pseudo-products (SPP), and this expression is, in general, shorter then the SP form. We present new algebraic SPP-expressions for the output functions of parallel integer multipliers based on Wallace Trees and column compression techniques.

We present an algorithm which exploits a new approach to the problem of finding the connected components of an undirected graph, CCug for short, with v vertices and e edges. The algorithm has depth O(log**2(e)) (where log is the logarithm whose base is 2) on a CREW PRAM using e processors, hence its cost is not affected by the number v of graph vertices. This makes the algorithm the one with best speedup and best cost for CCug on highly sparse graphs. On dense graphs conversely, its performance is comparable to the one of the algorithm defined by Han and Wagner in 1990 and a little worse than the one defined by Chong and Lam in 1995. A variant of the algorithm with the same bound but running on the EREW model is also included. The algorithm can be used to find the transitive closure of binary, symmetric relations. In this case e is the number of axioms and v is the range of the relation.

We propose a new implementation model for structured parallel programming models based on skeletons. The model is aimed at overcoming some of the problems observed in traditional, template based implementations of skeleton languages, while preserving all the positive features of structured parallel programming models. The proposed implementation model does not rely on static process networks like the template based implementation model for skeletons. It rather implements skeleton programs by properly scheduling macro data-flow instructions (corresponding to the sequential portions of code appearing in the skeleton code) to a set of macro data-flow interpreters running on the processing elements of the target architecture. We discuss some preliminary experimental results demonstrating the feasibility and effectiveness of our approach.

This paper presents in a unified framework the most efficient shortest path algorithms of the List class to highlight strategies for handling the candidate node set as well as issues related to the efficient implementation of such strategies. A deep analysis of the strategies which inspired two of the most robust algorithms for the shortest path tree problem, due to Tarjan [27] and to Goldberg and Radzik [18], allows the proposal of some variants. A computational study of such variants is conducted on the same test problem families used in [6], in order to validate "a posteriori" the implementation choices. The experimental data suggest that all of the new variants are robust in practice and, for each of the tested problem families, at least one of the new variants either improves the performance or performs as well as both benchmark algorithms.

We show that the Balanced Network Flow Problem in the case of general weights, i.e., the problem of finding a feasible flow on a given network which minimizes the difference between the maximum and the minimum weighted flow on single arcs, can be solved in strongly polynomial time. The proposed solution algorithm consists of extending Megiddo's approach for parametric programming.

We shall investigate minimum time and minimum cost path problems in street networks regulated by traffic lights. We shall show that the minimum time path problem is polynomially solvable. On the other hand, in general minimum cost path problems are NP-hard. Particular but realistic cases which are polynomially solvable will be discussed.

Obnoxious location models are models in which customers no longer consider the facility desirable and try to have it as close as possible to their own location, but instead avoid the facility and stay away from it. Typical applications are optimal locations of nuclear reactors, garbage dumps, or water purification plants. This work presents a survey of mathematical models for undesirable location problems in the plane and particularly on networks; solution procedures are briefly described. A brief review of extensive (obnoxious) facility location problems in networks is also given. Finally critical aspects of existing models are identified and some directions for future search are suggested.

Starting from the Finite Difference discretization of a general second order partial differential equation (PDE), we introduce the notion of generalized Locally Toeplitz sequence of matrices. The singular value distribution (the eigenvalue distribution in the Hermitian case)is studied and characterized for generalized Locally Toeplitz sequences in terms of weighted multidimensional Szego" formulas which extend previous results due to the second author and concerning the unilevel case. The application of this theoretic analysis to the numerical solution of elliptic PDEs is finally discussed.

The purpose of this work is to establish some foundational ground for the logics that can be used to reason on distributed systems communicating asyncronously via message passing, e.g. distributed workflow systems. These systems rule out synchronized local clocks, and reasoning on global time or state: message passing is the only possible mechanism for communication, and therefore for causality across components. We introduce {\em adtl}, a logic with modalities for time and locality. We show that its axiom system characterizes the class of structures that reflect the nature of the causal relation when communication is asyncronous. Correspondingly, the axioms are such that any attempt to formulate in the logic properties about the unspeakable entities, like a global state, results in a contradiction.

The paper addresses the problem of computing the Hyper-Wiener index for molecules in the alkanes family. A new algorithm having linear computational complexity is proposed. The algorithm has optimal complexity, and can be extended to the family of all the acyclic molecular structures. Some computational results are reported.

The need to generate graphs representing chemical structures suggested the use of computer and as a consequence the delevopment of efficient enumerating algorithms. This paper considers the isomeric acyclic structures enumeration focusin on the alkane molecular family. Two new algorithms based on Reverse Search are presented. The main concern of this paper is to highlight the importance of the asymptotic complexity and running time behaviour in the analysis of enumeration algorithms.

In questa nota vengono elencate e brevemente riassunte le tecniche disponibili per misurare l'efficienza di sistemi predisposti alla produzione di beni e servizi. Lo scopo è quello di valutare l'efficacia di tali tecniche, in particolare per la valutazione di sistemi di trasporto finalizzati, più che al profitto, a scopi di pubblica utilità. Sono analizzate in dettaglio due tecniche di valutazione di efficienza diventate ormai operative, note con le denominazioni di metodi parametrici e metodi non parametrici. Infine vengono riportate applicazioni di tali tecniche al settore del trasporto pubblico.

In this paper, we extend some general results on linear positive operators to the case of matrix-valued operators taking values in certain spaces of Hermitian matrices. These results are then used to show that certain matrices are optimal preconditioners for the linear systems arising in Interior Point methods for Linear Programs. In the case of graph matrices, corresponding to Min Cost Flow problems, we are able to find superlinear preconditioners for a class of ``local'' graphs generalizing the grid graphs commonly used in applications. For general graphs, we are able to give a spectral characterization of the preconditioners that may have a theoretical interest in its own.

We propose some techniques, based on minimum cost flow computations, for efficiently computing lower bounds for the Capacitated Minimum Spanning Tree problem (CMST). With respect to other methods proposed in the literature, our approaches often provide comparable bounds, with a substantially lower computational cost. For this reason, and for other features discussed in the paper, the proposed methods may be particularly promising in the context of exact algorithms for CMST.

Some questions regarding the possibility of considering DEA as a MCDM tool have been put in literature. Some of the answers, however, areproblematic more than "resolutive" . The multiplicity of "criteria" or "objectives" involved in a DEA model, does not necessarily mean that such a kind of representation might answer some questions, which concern the preferences on a given candidate (or alternative) set, as other MCDM tools can do validly, both conceptually and formally. A few methodological considerations and research proposal regarding these aspects shall be presented in the paper. In particular, the importance of clearly defining the "Decision Maker" figure is underlined to distinguish situations in which an individual, rather than a group of judges, is involved in the evaluation and ranking of candidate set.

The IP address lookup problem is one of the major bottlenecks in high performance routers. Previous solutions to this problem first describe it in the general terms of longest prefix matching and, then, are experimented on real routing tables $T$. In this paper, we follow the opposite direction. We start out from the experimental analysis of real data and, based upon our findings, we provide a new and simple solution to the IP address lookup problem. More precisely, our solution for $m$-bit IP addresses is a reasonable trade-off between performing a binary search on $T$ with $O(\log |T|)$ accesses, where $|T|$ is the number of entries in $T$, and executing a single access on a table of $2^m$ entries obtained by fully expanding $T$. While the previous results start out from space-efficient data structures and aim at lowering the $O(\log |T|)$ access cost, we start out from the expanded table with $2^m$ entries and aim at compressing it without an excessive increase in the number of accesses. Our algorithm takes \emph{exactly three} memory accesses and occupies $O(2^{m/2} + |T|^2)$ space in the worst case. Experiments on real routing tables for $m=32$ show that the space bound is overly pessimistic. Our solution occupies approximately one megabyte for the MaeEast routing table (which has $|T|\approx 44,000$ and requires approximately 250 KB) and, thus, takes three \emph{cache} accesses on any processor with 1 MB of L2 cache. According to the measurement obtained by the VTune tool on a Pentium II processor, each lookup requires 3 additional clock cycles besides the ones needed for the memory accesses. Assuming a clock cycle of 3.33 nanoseconds and an L2 cache latency of 15 nanoseconds, search of MaeEast can be estimated in 55 nanoseconds or, equivalently, our method performs 18 millions of lookups per second.

We address a generalization of graphs, the directed hypergraphs, and show that they are a powerful tool in modelling and solving several relevant problems in many application areas. Such application areas include Linear Production Problems, Flexible Manufacturing Systems, Propositional Logic, Relational Databases, and Public Transportation Systems.