Docente
|
LEONARDI STEFANO
(programma)
Argomenti di base e avanzati di progetto di algoritmi seguendo principalemente il libro di Kleinberg e Tardos.
-- Network flow: Ford and Fulkerson, Max Flow - Min Cut, scaling algorithm. Applications of network flow.
-- Matching in bipartite graphs and marriage theorem. Stable Matchings.
-- Greedy Algorithms: Interval Scheduling, Interval Partitioning.
-- Dynamic Programming: weighted Interval scheduling, knapsack, Bellman-Ford.
-- Basic concepts of approximation algorithms: simple examples, PTAS.
-- Linear programs and LP-based approximation: LP rounding, randomized rounding, primal-dual scheme
-- Randomised algorithms
-- Computational Game Theory: games efficiency of Equilibria and Price of Anarchy.
Prior
1. Jon Kleinberg and Eva Tardos. Algorithm Design. Cambridge University Press.
|