Algorithm Design and Engineering

Resarch lines:

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

Members:
Giorgio Ausiello (leader), Fabrizio D’Amore, Camil Demetrescu, Stefano Leonardi, Alberto Marchetti-Spaccamela,
Umberto Nanni.

PhD Students:
Donatella Firmani.

Post Docs:
Aris Anagnostopoulos, Vincenzo Bonifaci, Luigi Laura, Andrea Ribichini, Piotr Sankowski.

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: reoptimization techniques for combinatorial problems, models of computation for very large data sets

* Experimental Algorithmics: implementation and engineering of advanced algorithms and data structures for graph problems

* 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 network 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

In the future we plan to tackle fundamental problems arising in emerging applications involving the analysis and optimization of software systems and networks, real-time systems, scheduling and resource allocation. 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 incremental 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 focus on problems arising from the scheduling of recurrent tasks in real-time systems. 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 consider the simultaneous approximation on several objective functions and on network instances.

Projects:
MAINSTREAM: Algorithms for massive information structures and data streams
May 2007 - February 2009 - PRIN MIUR

AEOLUS: Algorithmic principles for building overlay computers
December 2005 - December 2010 - EU FP6 - FET

FRONTS: Foundations of Adaptive Networked Societies of Tiny Artefacts
March 2008 - March 2012 - EU FP7 - FET

SIMBIOSI: INRIA associated team
January 2009 - January 2011 - INRIA