Lista dei rapporti tecnici dell'anno 1999

Nguyen, S. and Pallottino, Stefano and Scutellà, Maria Grazia
A new dual algorithm for shortest path reoptimization
January 27, 2015
UnipiEprints view

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.

Attardi, Giuseppe and Simi, Maria and Tanganelli, Filippo and Tommasi, Alessandro
Learning conceptual descriptions of categories
January 27, 2015
UnipiEprints view

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.

Frangioni, Antonio and Scutellà, Maria Grazia and Necciari, Emiliano
Multi-exchange algorithms for the minimum makespan machine
January 27, 2015
UnipiEprints view

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.

Semini, Laura and Montangero, Carlo
A Logic with Modalities for Asynchronous Distributed Systems
January 27, 2015
UnipiEprints view

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.

Baldan, Paolo and Corradini, Andrea and Montanari, Ugo
Contextual Petri nets, Asymmetric Event Structures and Processes
January 27, 2015
UnipiEprints view

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.

Ciriani, Valentina
Multipliers based on Wallace trees and pseudo-products
January 27, 2015
UnipiEprints view

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.

Bellia, Marco and Occhiuto, Maria Eugena
Another PRAM algorithm for finding connected components of sparse graphs
January 27, 2015
UnipiEprints view

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.

Danelutto, Marco
Dynamic Run Time Support for Skeletons
January 27, 2015
UnipiEprints view

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.

Nonato, Maddalena and Pallottino, Stefano and Xuewen, B.
SPT_L shortest path algorithms: review, new proposals and some experimental results
January 27, 2015
UnipiEprints view

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.

Bettina, Klinz and Scutellà, Maria Grazia
A strongly polynomial algorithm for the Balanced network flow problem
January 27, 2015
UnipiEprints view

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.

Ahuja, Ravindra K. and Orlin, James B. and Pallottino, Stefano and Scutellà, Maria Grazia
Minimum time and minimum cost path problems in street networks with traffic lights
January 27, 2015
UnipiEprints view

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.

Cappanera, Paola
A Survey on Obnoxious Facility Location Problems
January 27, 2015
UnipiEprints view

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.

Serra Capizzano, Stefano and Tilli, P.
From Partial Differential Equations to generalized Locally Toepliz sequences
January 27, 2015
UnipiEprints view

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.

Semini, Laura and Montangero, Carlo
Modalities for Asynchronous Distributed Systems
January 27, 2015
UnipiEprints view

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.

Aringhieri, R. and Hansen, P. and Malucelli, Federico
A Linear Algorithm for the Hyper-Wiener Number of Chemical Trees
January 27, 2015
UnipiEprints view

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.

Aringhieri, R. and Hansen, P. and Malucelli, Federico
Chemical Tree Enumeration Algorithms
January 27, 2015
UnipiEprints view

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.

Farinaccio, Fernanda and Gallo, Giorgio and Sandi, Claudio
Valutazioni di produttività e misure di efficienza con applicazioni al settore del trasporto pubblico
January 27, 2015
UnipiEprints view

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.

Frangioni, Antonio and Serra Capizzano, Stefano
Matrix-Valued Linear Positive Operators and Applications to Graph Optimization
January 26, 2015
UnipiEprints view

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.

Frangioni, Antonio and Pretolani, Daniele and Scutellà, Maria Grazia
Fast Lower Bounds for the Capacitated Minimum Spanning Tree Problem
January 26, 2015
UnipiEprints view

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.

Farinaccio, Fernanda and Ostanello, Anna
Evaluation of DEA validity as a MCDA/M tool: some problems and issues
January 26, 2015
UnipiEprints view

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.

Crescenzi, Pierluigi and Dardini, Leandro and Grossi, Roberto
IP Address Lookup Made Fast and Simple
January 26, 2015
UnipiEprints view

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.

Gallo, Giorgio and Scutellà, Maria Grazia
Directed Hypergraphs as a Modelling Paradigm
January 26, 2015
UnipiEprints view

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.



NOTA. Da gennaio 2015 il Technical reports possono essere inseriti nel deposito Open Access UnipiEprints.
Una volta pubblicati saranno visibili anche in queste pagine. L'importazione dei dati da UnipiEprints è ancora da perfezionare. Il vecchio sistema TR non è più mantenuto.

Dati importati da UnipiEprints