Models and Algorithms for Matching and Assignment Problems

Course in common with other curricula.

Agenda

• Thursday November 30
  from 2.30 pm to 7.30 pm, room 5.6
• Thursday December 7, 2017
  from 2:30 pm to 7:30 pm, room 5.6
• Thursday December 14, 2017
  from 3:00 pm- 7:30 pm, room 5.1 
• Tuesday December 19, 2017
  from 2:30 pm to 7:30 pm, room 5.2

Length: 20 hours

Contents

1. Introduction: matching, assignment, graphs, bipartite graphs, adjacency matrix, incidence matrix;
2. Theoretical foundations: matching problems, Hall’s marriage theorem, Koenig’s algorithm, augmenting path, complexity, stable marriage problem;
3. Maximum matching applications: vehicle scheduling, time slot assignment (TDMA), open shop scheduling;
4. Linear sum assignment problem: weighted matching, constraint matrix, unimodularity, duality, Egervary’s theorem, initialization algorithms;
5. The Hungarian algorithm: main structure, rooted alternating tree, complexity, Kuhn’s algorithm, Jacobi’s theorem;
6. Non-Hungarian algorithms: Dinic-Kronrod’s algorithm, primal simplex algorithms, Egervary’s algorithm, Birkhoff-Von Neumann theorem;
7. Other linear assignment problems: k-cardinality assignment, bottleneck assignment, threshold algorithm, balanced assignment;
8. Quadratic assignment problems: combinatorial formulation, complexity, integer quadratic formulation, inner product formulation, trace formulation, exact solution, heuristics.