Home » Gruppi Di Ricerca » 18310
Algorithm Design and Engineering

Research activity regarding design and engineering of computer algorithms and computational complexity analysis has been developed at DIAG since when the Department has been created in the early Eighties. In the first years the emphasis has been on theoretical aspects such as those related to the notion of approximation preserving reductions among optimization problems and the classification of optimization problems based on their approximability properties.

Subsequently, research activities have evolved in various directions according to the evolution of information technology and of application domains. New emerging topics have been addressed such as dynamic graph algorithms, on line algorithms, external memory, and streaming algorithms for massive data sets. Also the emphasis of the approach has changed moving from traditional worst case analysis to experimental performance analysis.


The most relevant recent results include contributions in the following areas:

  • Principles of Design and Analysis of Algorithms: re-optimization techniques for combinatorial problems, models of computation for very large data sets;
  • Experimental Algorithmics: implementation and engineering of advanced algo- rithms and data structures for graph problems;
  • Performance Engineering: design and implementation of methodologies and tools for analying and optimizing software systems;
  • External Memory and Streaming Algorithms for Massive Data Processing: external- memory and streaming algorithms for very large graph problems;
  • Incremental Algorithms and Dynamic Data Structures: incremental algorithms for path problems in graphs;
  • Approximation and On-line Algorithms: scheduling algorithms, algorithms for metabolic networks, vehicle routing, approximation algorithms for rent-or-buy net- work design problems, on-line algorithms for stochastic optimization problems such as Steiner tree and set cover under several models;
  • Algorithmic Game Theory: quality of strong equilibria in network formation games under restricted communication model;
  • Algorithmic approaches for bioinformatics and elearning: application of algorith- mic models and techniques to bioinformatics and elearning.

In the future we plan to tackle fundamental problems arising in emerging applications involving the analysis and optimization of networks, real-time systems, scheduling and resource allocation, as well as in other areas. Special emphasis will be given to problems on very large data sets and multi-core platforms. In particular, our research goals include:

  • External Memory and Streaming Algorithms for Massive Data Processing: external- memory and streaming algorithms for problems arising in the dynamic analysis of large software systems and networks. Among other goals, we plan to investigate novel approaches to performance profiling and optimization based on provably efficient streaming techniques;
  • Incremental Algorithms and Dynamic Data Structures: we will study efficient incre- mental change propagation techniques for constraint-based systems on multi-core platforms;
  • Approximation and On-line Algorithms: we aim at investigating the complexity and the approximability of combinatorial resource allocation problems, with a fo- cus on problems arising from the scheduling of recurrent tasks in real-time sys- tems. In particular, we aim at the design and analysis of efficient tests of feasibility for the scheduling of tasks on multiprocessor platforms. We will push further the study of on-line algorithms for stochastic optimization problems. We’ll also con- sider the simultaneous approximation on several objective functions and on net- work instances;
  • Algorithmic approaches for bioinformatics and elearning: several models and tech- niques, studied and evolved within the area of algorithm engineering turned out to be very pervasive. In various contexts these has lead to effective solutions to problems with complex structure. In the last years we have devised representa- tions, based on graphs and hypergraphs, suitable to model processes and biologi- cal systems. Then, working with groups of researchers in other disciplines - such as bioinformatics and elearning - we aim at boosting research results in these areas.

Giorgio Ausiello is editor of the following journals:

  • Theoretical Computer Science - Series A.
  • Computer Science Review.
  • SN Computer Science.
  • co-Editor in Chief of the ARCoSS series of Springer Lecture Notes in Computer Science.



© Università degli Studi di Roma "La Sapienza" - Piazzale Aldo Moro 5, 00185 Roma