Responsable / In charge of : Coudert David (David.COUDERT@inria.fr)

Résumé / Abstract :
The lectures will present problems arising in the design and management of telecommunication networks considered by operators and manufacturers. Several kinds of networks will be considered, including optical WDM networks and wireless radio networks. Examples of problems studied in these networks are routing, wavelength or frequency assignments, placement of access points, placement of sensors, fault tolerance, energy consumption.
For each problem we will show how to give simple models to tackle them. Then we will introduce algorithmic tools to solve them. All these problems being difficult, we will emphasize approximation algorithms, dynamic programming and heuristics. These studies will widely use the tools presented in Graph algorithms and combinatorial optimization.

Prérequis / Prerequisite :
• Basic knowledge of graph theory and combinatorial optimization

Objectifs / Objectives :
• Learn how to model a problem, understand its difficulty and propose methods to solve it

Contenu / Contents :

• Introduction to mixed integer linear programming
• Review of basic optimization problems
• Routing, flows and multi-commodity flows
• Frequency assignment problems in optical and wireless networks
• Network design problems
• Use software to solve integer linear programs in practice

Références / References :

• Michal Pióro, Deepankar Medhi: Routing, flow, and capacity design in communication and computer networks. Morgan Kaufmann 2004, ISBN 978-0-12-557189-0, pp. I-XXVIII, 1-765
• Arie Koster, Xavier Muñoz: Graphs and Algorithms in Communication Networks: Studies in Broadband, Optical, Wireless and Ad Hoc Networks. Texts in Theoretical Computer Science. An EATCS Series, Springer 2010, ISBN 978-3-642-02249-4
• Lectures notes of course EIIN907 “Graph Algorithms and Combinatorial Optimization”: http://www- sop.inria.fr/members/Frederic.Havet/Cours/ubinet.html and references inside.

Acquis / Knowledge :

Evaluation / Assessment :
2 written exams (midterm: 30% of the mark; final: 40% of the mark) and a project (30% of the mark)