**Algorithms for Telecommunication**

Ubinet track -

Master IFI -

University of Nice-Sophia Antipolis
*The goal of this class is to show how combinatorial tools can be used to improve telecom networks.*
Class document:

pdf (5 chapters)

Going further: An extended version of the notes

pdf (14 chapters)

#### Combinatorial Algorithms:

Session 1:

*Introduction to graphs.*
- Graph, basic concepts (Chapter 1).

- Search in graphs and digraphs (Chapter 2).

Session2:

*Algorithms in edge-weighted graphs* (Chapter 3).

- Dijkstra's algorithm or computing shortest paths.

- What about spanning trees or Boruvka-Kruskal algorithms.

Session 3:

*Solving flow problems* (Chapter 4).

- Ford-Fulkerson algorithm.

Session 4:

*Applications of flow problems and other things.*
Going further:

- Connectivity (Chapter 5 of the extended notes).

- Matching (Chapter 6 of the extended notes).

- Coloring (Chapter 8 of the extended notes).

#### Linear Programming: (Chapter 5)

Session 1:

*Introduction to linear programming* slides.

*Modelling combinatorial problems* slides.

Session 2:

*Duality or assessing the quality of a solution* slides.

Session 3:
Simplex Algorithm or Solving linear programmes

slides. Simplex, Reduced Cost, and Duality

slides.

*Approximation algorithms via fractional relaxation* slides.

Session 4:

*Solving problems in practice or using solvers* (Glpk and Sagemath)

pdf.

- Sagemath worksheet: Minimum vertex cover

worksheet.

Going further:

- Column Generation

slides.

- Polynomial Methods or Solving linear programmes when you are not in a hurry (The ellipsoid method) (Chapter 10 of the extended notes).

- Approximation techniques (Lagrangian relaxation, Fractional relaxation, Primal-Dual algorithms) (Chapters 11, 12, 13 of the extended notes).

#### Exam archives:

2018-2019:

final exam,

first exam.
2017-2018:

final exam,

first exam.
2016-2017:

final exam,

first exam.
2015-2016:

final exam