Current Research interests

- On-line algorithms
- Approximation algorithms
- Dynamic graph algorithms
- Optimization problems in vehicle routing and logistics
- Streaming algorithms

Past Research interests

Throughout my research career I have addressed various research issues in a wide variety of domains: theory of programming, database theory, computational complexity, algorithmics, discrete optimization. The domains in which I see my major contributions and which still form my main research interest, are the domains concerning the approximate solution of NP-hard optimization problems and the design of advanced algorithms. The major results in such domains can be summarized as follows.

- Approximability of NP-hard optimization problems: in this field, we have addressed the problem of the approximability of NP-hard optimization problems, with the aim to characterize those problems that can be efficiently approximated and those problems that are hard to approximate and to establish relationships between structural and approximability properties of problems. In particular, we introduced for the first time new measures of the quality of approximation and the notions of structure preserving reducibility and of approximation preserving reducibility, we proved the existence of complete problems in the class of NP optimization problems, we studied the power of approximation techniques such as local search and greedy algorithms.
- Dynamic and on-line algorithms: in the field of dynamic graph algorithms we have been among the first researchers to address the problem of efficiently maintaining graphs in a dynamic setting, in which edges can be inserted and/or deleted, and, in particular, to provide efficient algorithms for maintaining shortest paths. In the field of on-line algorithms we have addressed some on line versions of the traveling salesman problem, laying down the foundations for a large number of subsequent papers, by various authors, devoted to on line vehicle routing problems.
- Directed hypergraph algorithms: we have introduced the notion of directed hypergraph (a generalization of directed graphs) and studied the complexity and the design of efficient algorithms for static and dynamic solutions of the transitive closure, the transitive reduction, the shortest hyperpath problem. Such algorithms have been applied to a wide variety of problems such as minimization of functional dependency in databases, satisfiability of propositional Horn clauses and truth maintenance in fuzzy Horn logics.

Beside the main research contributions related to the above mentioned fields we have also contributed to the following domains:

- in theory of programming we designed and developed the first LISP interpreter in Italy and took part in the development of one of the earliest symbolic manipulation systems; we studied the relationship between the computation models of LISP, of lambda calculus and of related algorithmic languages such as the language CUCH designed by Corrado Böhm; we studied the modeling of parallel computing in lambda calculus and we provided one of the first treatment of symbolic manipulation systems in the framework of abstract data types;
- in computational complexity we proposed a variation of Blum's axioms for abstract complexity measures in such a way to make possible to give a more appropriate treatment of space-like resources; we addressed the study of the complexity of functions defined by multiple recurrence relations; also, for the first time, we applied Gold's notion of limiting approximation in the context of the complexity classes P and PSPACE;
- in database theory we have addressed the problem of establishing equivalence among databases both from an intensional and from an extensional point of view; we have addressed the problem of determining minimum equivalent database schemes; we have studied the problem of acyclicity in database schemes;
- in the field of graph algorithms we have addressed optimum graph searching problems, related to web exploration.

For this research activity I am indebted to all my coauthors and in particular to: Pierluigi Crescenzi, Fabrizio d'Amore, Alessandro D'Atri, Paolo Giulio Franciosa, Giorgio Gambosi, Pino Italiano, Stefano Leonardi, Alberto Marchetti Spaccamela, Marina Moscarini, Umberto Nanni, Marco Protasi, Domenico Sacca', Maurizio Talamo.

Some of my past Master and Ph. D. Students.

- Giuseppe Longo
- Beppe Attardi
- Marina Moscarini
- Marco Protasi
- Maurizio Talamo
- Umberto Nanni
- Pino Italiano
- Alessandro Panconesi
- Fabrizio d'Amore
- Paolo Franciosa
- Esteban Feuerstein
- Stefano Leonardi
- Luigi Laura
- Vincenzo Bonifaci