Network Design

Description

 
This is a 4-credits doctoral course. 
The course aims at developing efficient methods to solve mathematical problems often arising in the context of network design.
The focus is on exact and approximation algorithms, mainly based on combinatorial techniques. 

                       

Content

We discuss fundamental mathematical problems from the field of Network Design, that are frequent and crucial in the telecommunications and transportations world. In particular, we focus on optimization problems that belong to two main categories: connectivity network problems and routing network problems. 

Regarding connectivity problems, we briefly review exact combinatorial algorithms for basic problems such as shortest paths and spanning trees. We then move to famous NP-hard problems such as Steiner Trees, Generalized Steiner networks and Facility Location problems. We present approximation algorithms based on two fundamental techniques: primal-dual schemes and iterated rounding. 

We then focus on routing problems in networks. We quickly review the basic structure and properties of single-commodity flow problem, and then concentrate on important generalizations. Specifically, we study the characterization of multi-commodity network flows, and we describe approximation algorithms for computing unsplittable flows. We close with the investigation of some important results in the interesting field of flows over time.

Required prior knowledge

Basic knowledge in Linear Programming. 

Program and Grading

Grading will be determined by an oral exam at the end of the semester. Bonus points can be collected during the semester, by solving the assignments below.

Detailed Program:

  •   15.09.09: Introduction and overview of the course. Reminder on basic connectivity problems: Minimum Spanning Trees. Kruskal and Prim algorithms.
    first_assignment.pdf

  •   22.09.09: Reminder on shortest paths: Feasible potential. Ford/Ford-Bellman/Dijkstra algorithms. Min-cost disjoint s-t paths. Successive shortest path algorithm.
    second_assignment.pdf

  •   29.09.09: Steiner trees. Metric Steiner tree. A 3/2-approximation for Steiner trees on quasi-bipartite graphs.
    third_assignment.pdf

  •   06.10.09: A general primal-dual approximation technique for constrained forest problems.
    4th_assignment.pdf

  •   20.10.09: Generalized Steiner Networks. A 2-approximation based on iterated rounding.
    6th_assignment.pdf

  •   27.10.09: Generalized Steiner Networks. Iterated rounding VS Primal-dual scheme.
    7th_assignment.pdf

  •   03.11.09: Network flows. Reminder on single-commodity flow. Multi-commodity flow. Hu’s two-commodity flow theorem.
    8th_assignment.pdf

  •   10.11.09: Primal-dual algorithm for integer multi-commodity flow in trees.
    9th_assignment.pdf

  •   17.11.09: Single-source unsplittable flow problem. A 2-approximation algorithm for congestion.
    10th_assignment.pdf

  •   24.11.09: Single-source unsplittable flow problem. A bicriteria (3,1)-approximation for congestion and cost.  
  •   01.12.09: Maximum flow over time. 
  •   08.12.09: Earliest arrival flows.
  •   15.12.09: Multi-commodity flows over time.

Scheduling

Tuesday 10.15 -12.00 Lecture, room: (MA A3 30) 
Tuesday 12.15 – 14.00 Exercise session, room:  (MA A3 30)
The course will start on Tuesday 15th September 2009.

Want to join?

Please, send an email to Laura Sanità: laura[dot]sanita[at]epfl[dot]ch