IIT Home Page CNR Home Page

Algorithmics

Research fields

Algorithms and Computational Mathematics

Activities

Algorithms for Web Technologies

Our research group is using its long-time experience in design and analysis of algorithms, graph theory and information retrieval to improve aspects of the World Wide Web (WWW) Technology. Internet is a distributed system and the applications built on top (such as the WWW) have a natural interpretation as a graph whose nodes represent web pages, or web sites, and the arcs are the navigational hyper-links. This view abstracts from many low level details of single computers and allow to detect global phenomena.

Computational Biology

The objective of the research is the development of efficient and scalable algorithms for high throughput analysis of biological and genomic data, in order to help getting useful indication in a -highly competitive- timely manner. More precisely the areas of interest are: Simple and structured motif identification and extraction; Tandem repeat identification and extraction; Microarray Gene Expression Data Analysis; SNP Haplotyping Analysis; Metabolic Networks Analysis and Diseases and Gene Expression Profiling Classification.

Computational Economy

In the last years the connections among algorithmics, game theory and economics got stronger and many specific themes arised which are of interest for the group. One research area concerns the use of concepts and techniques imported from Game Theory and Mechanism Design for the design and analysis of routing protocols when the network nodes behave in a strategic manner (i.e., driven only by economic interests). A second topic concerns the problem of the existence and computation of market equilibria.

Numerical Methods for Large Problems

This activity is aimed at the analysis and development of algorithms for the solution of very large linear systems (i.e., 10,000 equations and 10,000 variables). These problems are often associated to queue problems or arise in the discretization of infinite domain differential equations. A second topic concerns the study of iterative methods for ill-conditioned problems, like in some problems of image reconstruction. A third reseach activity concerns the analysis of the stability properties of “fast” methods for the solution of structured linear systems.

Wireless network algorithms

This activity is aimed at investigating, both analytically and through simulation, some fundamental properties of wireless multihop networks such as connectivity, radio interference, network lifetime, node spatial distribution in presence of mobility, safety-critical message propagation in vehicular networks, and so on. The general approach to study these problems is defining simplified -- yet detailed enough to capture the most relevant features of real networks -- models, which are then used to analytically study the fundamental tradeoffs involved in the considered network properties.

People

Alessio Vecchio

Foto di Alessio Vecchio

Bruno Codenotti

Foto di Bruno Codenotti

Filippo Geraci

Foto di Filippo Geraci

Francesca Martelli

Foto di Francesca Martelli

Giovanni Manzini

Foto di Giovanni Manzini

Giovanni Resta

Foto di Giovanni Resta

Marco Pellegrini

Foto di Marco Pellegrini

Maria Elena Renda

Foto di Maria Elena Renda

Mauro Leoncini

Foto di Mauro Leoncini

Miriam Baglioni

Foto di Miriam Baglioni

Paola Favati

Foto di Paola Favati

Paolo Santi

Foto di Paolo Santi

Vanessa Gardellin

Foto di Vanessa Gardellin

Projects

COmputational and GamE-theoretic aspects of uncoordinated NeTworks (COGENT)

The emerging global communication and service infrastructures need to be more and more pervasive, high-performing and reliable. The underlying scenario is basically characterized by decentralization, autonomy, and general lack of coordination among the heterogeneous network entities, the network in turn intrinsically being a common playground for a large number of users. These users exhibit various degrees of intentional or unintentional non cooperative behaviour, while competing for shared and often scarce resources. Besides, they increasingly demand also stable connection and seamless access to the network resources, by means of the enormous potential offered by the new wireless equipments and capabilities.

The combination of uncoordination and wireless access induces a degree of dynamism never experienced before, that must be necessarily faced by the emerging services and applications, and calls for a pressing solution of the resulting scientific and technological challenges. In such a highly elusive and mutable setting, the focus of the present project is that of evaluating the impact on the network performance induced by the combination of the lack of users cooperation/collaboration and the presence of users mobility/dynamism. To this respect, the general mismatch between the network optimization goals and the competing users private interests, motivates the following research directions:
1) modeling and analyzing the consequences of the autonomous users behaviour on the network performance;

2) accounting for specific features imposed by the dynamic nature of these networks (e.g., users mobility, wireless medium, unreliable connectivity, etc.);

3) investigating the influence of the different degrees of users social knowledge on users behaviour when analyzing items 1) and 2) above, and, consequently, on the system performance and on the induced mobility patterns and network topology;

4) evaluating the solutions developed in 1), 2), and 3) also through extensive simulations.

As a final outcome, the most significant algorithm/protocols and application scenarios will be packaged in a software tool (a "demonstrator") which will be made available to the research community.

IPERMOB - A Pervasive and Heterogeneous Infrastructure to control Urban Mobility in Real-Time

Within the domain of "Intelligent Transport Systems" IPERMOB proposes a multi-tier approach for developing an Information System for urban mobility.
IPERMOB proposes a new generation of integrated systems based on the optimization and inter-operability of the chain formed by:

MimoNet

The MimoNet project aims at developing tools and techniques for network-level exploitation of MIMO technology. In particular, MimoNet targets a specific type of networks, wireless mesh networks.

Virtual Physiological Human Network of Excellence (VPH NoE)

The VPH NoE is a project which aims to help support and progress European research in biomedical modelling and simulation of the human body. This will improve our ability to predict, diagnose and treat disease, and have a dramatic impact on the future of healthcare, the pharmaceutical and medical device industries.

Publications and editorial products

Ab initio detection of fuzzy amino acid tandem repeats in protein sequences

A Measurement-based Study of Beaconing Performance in IEEE 802.11p Vehicular Networks

A Measurement-based Study of Beaconing Performance in IEEE 802.11p Vehicular Networks

An Efficient Combinatorial Approach for Solving the DNA Motif Finding Problem

A Personalized Collaborative Digital Library Environment: a model and an Application

A Personalized Information Search Assistant

Automatic Structured Query Transformation Over Distributed Digital Libraries

Detecting Fuzzy Amino Acid Tandem Repeats in Protein Sequences

Enabling Efficient Peer-to-Peer Resource Sharing in Wireless Mesh Networks

Evaluating Load Balancing in Peer-to-Peer Resource Sharing Algorithms for Wireless Mesh Networks

Evaluating Load Balancing in Peer-to-Peer Resource Sharing Algorithms for Wireless Mesh Networks

FPF-SB: a Scalable Algorithm for Microarray Gene Expression Data Clustering

K-Boost: A Scalable Algorithm for High-Quality Clustering of Microarray Gene Expression Data

Load Balancing Hashing for Geographic Hash Tables

Load Balancing Hashing for Geographic Hash Tables

Measuring IEEE 802.11p Performance for Active Safety Applications in Cooperative Vehicular Systems

Measuring IEEE 802.11p Performance for Active Safety Applications in Cooperative Vehicular Systems

Measuring VoIP performance in IEEE 802.11p Vehicular Networks

MeshChord: A Location-Aware, Cross-Layer Specialization of Chord for Wireless Mesh Networks

MeshChord: A Location-Aware, Cross-Layer Specialization of Chord for Wireless Mesh Networks.

OO3-1,2,3: Dispositivo prototipale

OO3–3.3-6: Scelta della tecnologia di comunicazione radio per la rete veicolare sulla base di test sul campo

OO3-3.5: Relazione finale

Personalized Information Search and Retrieval Through a Desktop Application

Personalized Information Search and Retrieval Through a Desktop Application

P I S A: A Personalized Information Search Assistant

Poster del Workshop BINET 2012 - Business Intelligence & Network Analysis

Proceedings of the VIII Annual Meeting of the Bioinformatics Italian Society

Programma Workshop BINET 2012 - Business Intelligence & Network Analysis

Tandem Repeats Discovery Service (TReaDS) applied to finding novel Cis-acting factors in Repeat Expansion Diseases

The IPERMOB System for Effective Real-Time Road Travel Time Measurement and Prediction

TReaDS: Tandem Repeats Discovery Service

TRStalker: an Efficient Heuristic for Finding Fuzzy Tandem Repeats

TRStalker: an Efficient Heuristic for Finding NP-Complete Tandem Repeats