Algorithm Design and Engineering Group

Department of Computer and System Sciences, University of Rome "La Sapienza"
welcome people events activities projects software publications


Research activity regarding design and engineering of computer algorithms and computational complexity analysis has been developed at DIS 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
  • Experimental Algorithmics
  • External Memory and Streaming Algorithms for Massive Data Processing
  • Incremental Algorithms and Dynamic Data Structures
  • Approximation and On-line Algorithms
  • Algorithmic Game Theory

The group is currently cooperating with several prestigious research institutions: Max Planck fuer Informatik (Saarbrueken, Germany), University of Paderborn (Germany), CTI-Patrasand University of Athens (Greece), ETH (Zurich, Switzerland), Université de Paris (Dauphine, France), Tel-Aviv University (Israel), AT&T - Research Labs (Florham Park, NJ, USA), Polytechnic Uni- versity of Catalunya, ICSI-Berkeley (USA), Brown University (Providence, RI, USA), Carnegie-Mellon University (Pittsburgh, PA, USA), Microsoft Research (Mountain View, CA, USA), Yahoo! Research (Barcelona, Spain).

The main recent research activities of the group are summarized in the 2009 ADE Group Research Report.