|
Research activities
The research activity of the group of Algorithm Engineering (AE) is concentrated
on the design, the engineering, the theoretical and experimental performance
analysis of combinatorial algorithms for problems arising in modern Computer
Systems and Networks, and in applications related to complex resource management
problems. Our main research interests deal with the solution of optimization
problems and the design of efficient data structures, with special emphasis
on those applications involving large data sets.
In particular we concentrate on
(i.) algorithms that perform efficiently in a dynamically changing environment,
(ii.) models and methodologies for the analysis and design of algorithms for
multilevel memories,
(iii.) the efficient management of communication and information delivery and
recovery in Wireless Networks and on the Internet, (iv.) the design and analysis
of approximation algorithms for NP-hard optimization problems,
(v.) the design of on-line algorithms that work with incomplete information
on the input instance,
(vi.) the efficient solution of problems arising in geometric applications with
emphasis on numeric robustness,
(vii.) the design and implementation of tools and platforms for the experimental
analysis and visualization of the behaviour of algorithms and data strucures.
Members of the group
Selected papers
Pankaj K. Agarwal and Lars Arge and Jeff Erickson and Paolo G. Franciosa and Jeffry Scott Vitter. Efficient Searching with Linear Constraints. Proceedings of the ACM SIGACT--SIGMOD--SIGART Symposium on Principles of Database Systems, pp. 169--178. To appear in Journal of Computer and System Science.
S. Albers, N. Garg and S. Leonardi. Minimizing Stall Time in Single and Parallel Disk Systems. To appear in Journal of the ACM, Vol 48, No 1, 2001.
G. Ausiello, P. Crescenzi, G. Gambosi, V. Kann, A. Marchetti Spaccamela, M. Protasi, Complexity and Approximation. Combinatorial Optimization Problems and their Approximability Properties. Springer Verlag, 1999.
G. Ausiello, E. Feuerstein, S. Leonardi, L. Stougie, M. Talamo. Algorithms for the on-line traveling salesman. To appear in Algorithmica, 2001.
F. d'Amore, P. G. Franciosa, G. Liotta. A robust region approach to the computation of geometric graphs. Proc. of the Sixth Annual European Symp. on Algorithms (ESA '98), Lecture Notes in Computer Science, Vol. 1461, Springer Verlag, 1998, 175--186.
L. Becchetti, S. Leonardi and S. Muthukrishnan. Scheduling to minimize Average Stretch without Migration. Proceedings of the 11th ACM-SIAM Annual Symposium on Discrete Algorithms (SODA '00), pp. 448-557, 2000.
C. Demetrescu, G. F. Italiano, Dynamic Transitive Closure: Breaking Through the O(n^2) Barrier'. Proc. 41st Annual Symp. on Foundations of Computer Science (FOCS 2000), November 2000.
C. Demetrescu, D. Frigioni, A. Marchetti-Spaccamela, and U. Nanni. Maintaining Shortest Paths in Digraphs with Arbitrary Arc Weights: An Experimental Study, Proc. 4th Workshop on Algorithm Engineering (WAE'00), September 2000.
C. Demetrescu, I. Finocchi and G. Liotta. Visualizing Algorithms over the Web with the Publication-Driven Approach, Proc. 4th Workshop on Algorithm Engineering (WAE'00), September 2000
D. Frigioni, A. Marchetti Spaccamela, and U. Nanni Fully dynamic algorithms
for maintaining shortest path trees. Journal of Algorithms, 34 (2):351-381,
2000 S. Leonardi, A. Marchetti-Spaccamela, A. Presciutti and A. Rosen. On-line
Randomized Call-Control Revisited. To appear in SIAM Journal on Computing, 2001.
Other activities
Giorgio Ausiello is Chairman of the Technical Committee on Foundations of Computer Science of the International Federation of Information Processing (IFIP - TC 1) since 1997 and Editor in Chief of Theoretical Computer Science, Series A, Algorithms and Complexity.
Members of the AE group are continuously involved in the Program Committes of prestigeous International Conferences. Prof. Alberto Marchetti-Spaccamela will co-chair the Program Committee of the Workshop on Algorithm Engineering of year 2001.
The AE group has recently organized the 1997 Workshop on Graph Theoretical
Concepts in Computer Science (WG 97), the 1998 School and Workshop on On-line
Algorithms, and will organize in Rome CONF 2002, where the European Symposium
on Algorithms, the Workshop on Algorithm Engineering and the Workshop on Approximation
Algorithms will be co-located. A regular Seminar, The Interdepartmental Seminar
on Algorithms (SIA), is also organized in cooperation with the Department of
Information Science of this University.
Ongoing research projects
Cooperation with other research groups
Max Planck fuer Informatik - Saarbruecken, Germany
CTI-Patras, Greece
ETH-Zurich, Switzerland
Universite' de Paris-Dauphine, France
Tel-Aviv University, Israel
AT&T - Research Labs, Florham Park, USA
ICSI-Berkeley, USA
Brown University, Providence, USA