FMVE180 Optimisation problems in random models

Kursens poäng (högskolepoäng, hp) 7.5
Kursen ges normalt Fall 2008, next time not yet planned
Tillhör forskarskola
Tillhör institution Matematiska vetenskaper
Kursansvarig
Johan Wästlund, wastlund@chalmers.se
Kursbeskrivning
We mainly study optimization problems on graphs with random edge weights. Examples are shortest path, minimum spanning tree, minimum matching and the travelling salesman problem. Several of the techniques are applicable in other contexts: Useful properties of the exponential distribution and the Poisson process, probabilistic methods for discrete problems, concentration inequalities, expander properties of random graphs etc.

Publicerad: ti 29 jan 2013. Ändrad: må 13 nov 2017