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:
2022-2023:
final exam,
first exam.
2021-2022:
final exam,
first exam.
2020-2021:
first exam.
2019-2020:
final exam,
first exam.
2018-2019:
final exam,
first exam.