GALOP – Graphs Algorithms for Optimization Problems

Pays impliqués : France, Brésil, Chili

Projet Stic_AmSud

This proposal aims at allowing to continue the fruitful and long-standing collaboration between Inria and UFC and between Inria and UAI. Another goal is to reinforce the collaboration between UFC and UAI that has been recently initiated. Our goal is to study the Computational Complexity of several important problems arising in networks (routing, resources assignment…). In particular, we will focus on the computation of metric or structural properties and parameters of large networks (e.g., transportation and social networks…). We plan to design efficient exact algorithms for solving these problems or to theoretically prove that such algorithms cannot exist. In the latter case, we will then design approximation algorithms, or prove that none exists. In all cases, we aim at implementing our algorithms and use them on real-world instances such as large road networks or huge social networks.

Coordinateurs :
Julio Araujo – Universidade Federal do Ceará (UFC) Fortaleza, BRAZIL
Karol Suchan, Universidad Adolfo Ibáñez (UAI), Facultad de Ingeniería y Ciencias, Santiago, CHILI
Nicolas Nisse, Inria Sophia Antipolis COATI Team Project – FRANCE