Diese Seite auf DE

Event

[SS200160000]

Type
lecture (V)
Term
SS 2020
SWS
4
Language
Englisch
Appointments
40
Links
ILIAS

Lecturers

Organisation

  • KIT-Fakultät für Mathematik

Part of

Literature

  • Boucheron, S., Lugosi, G., Massart, P. Concentration Inequalities, Oxford University Press, Oxford, 2013.
  • Dubhashi, D., Panconesi, A. Concentration of Measure for the Analysis of Randomized Algorithms, Cambridge University Press, Cambridge, 2009.
  • Ledoux, M. The Concentration of Measure Phenomenon. American Mathematical Society, vol. 89, 2001.
  • Steele, J.M. Probability Theory and Combinatorial Optimization. SIAM, 1997.
  • Yukich, J.E. Probability Theory of Classical Euclidean Optimization Problems. Lecture Notes in Mathematics, Vol. 1675, Springer, Berlin, 1998.
  • Vershynin, R. High-dimensional probability. An Introduction with Applications in Data Science. Cambridge University Press. 2018.

Appointments

  • 22.04.2020 09:45 - 11:15 - Room: 20.30 SR 2.058
  • 22.04.2020 11:30 - 13:00 - Room: 20.30 SR 2.058
  • 23.04.2020 09:45 - 11:15 - Room: 20.30 SR 3.061
  • 29.04.2020 09:45 - 11:15 - Room: 20.30 SR 2.058
  • 29.04.2020 11:30 - 13:00 - Room: 20.30 SR 2.058
  • 30.04.2020 09:45 - 11:15 - Room: 20.30 SR 3.061
  • 06.05.2020 09:45 - 11:15 - Room: 20.30 SR 2.058
  • 06.05.2020 11:30 - 13:00 - Room: 20.30 SR 2.058
  • 07.05.2020 09:45 - 11:15 - Room: 20.30 SR 3.061
  • 13.05.2020 09:45 - 11:15 - Room: 20.30 SR 2.058
  • 13.05.2020 11:30 - 13:00 - Room: 20.30 SR 2.058
  • 14.05.2020 09:45 - 11:15 - Room: 20.30 SR 3.061
  • 20.05.2020 09:45 - 11:15 - Room: 20.30 SR 2.058
  • 20.05.2020 11:30 - 13:00 - Room: 20.30 SR 2.058
  • 27.05.2020 09:45 - 11:15 - Room: 20.30 SR 2.058
  • 27.05.2020 11:30 - 13:00 - Room: 20.30 SR 2.058
  • 28.05.2020 09:45 - 11:15 - Room: 20.30 SR 3.061
  • 03.06.2020 09:45 - 11:15 - Room: 20.30 SR 2.058
  • 03.06.2020 11:30 - 13:00 - Room: 20.30 SR 2.058
  • 04.06.2020 09:45 - 11:15 - Room: 20.30 SR 3.061
  • 10.06.2020 09:45 - 11:15 - Room: 20.30 SR 2.058
  • 10.06.2020 11:30 - 13:00 - Room: 20.30 SR 2.058
  • 17.06.2020 09:45 - 11:15 - Room: 20.30 SR 2.058
  • 17.06.2020 11:30 - 13:00 - Room: 20.30 SR 2.058
  • 18.06.2020 09:45 - 11:15 - Room: 20.30 SR 3.061
  • 24.06.2020 09:45 - 11:15 - Room: 20.30 SR 2.058
  • 24.06.2020 11:30 - 13:00 - Room: 20.30 SR 2.058
  • 25.06.2020 09:45 - 11:15 - Room: 20.30 SR 3.061
  • 01.07.2020 09:45 - 11:15 - Room: 20.30 SR 2.058
  • 01.07.2020 11:30 - 13:00 - Room: 20.30 SR 2.058
  • 02.07.2020 09:45 - 11:15 - Room: 20.30 SR 3.061
  • 08.07.2020 09:45 - 11:15 - Room: 20.30 SR 2.058
  • 08.07.2020 11:30 - 13:00 - Room: 20.30 SR 2.058
  • 09.07.2020 09:45 - 11:15 - Room: 20.30 SR 3.061
  • 15.07.2020 09:45 - 11:15 - Room: 20.30 SR 2.058
  • 15.07.2020 11:30 - 13:00 - Room: 20.30 SR 2.058
  • 16.07.2020 09:45 - 11:15 - Room: 20.30 SR 3.061
  • 22.07.2020 09:45 - 11:15 - Room: 20.30 SR 2.058
  • 22.07.2020 11:30 - 13:00 - Room: 20.30 SR 2.058
  • 23.07.2020 09:45 - 11:15 - Room: 20.30 SR 3.061

Note

This course is devoted to the analysis of algorithms and combinatorial optimization problems in a probabilistic framework. A natural setting for the investigation of such problems is often provided by a (geometric) graph. For a given system (graph), the average or most likely behavior of an objective function of the system will be studied. In addition to asymptotic results, which describe a system as its size increases, quantitative laws for systems of fixed size will be described. Among the specific problems to be explored are

  • the long-common-subsequence problem,
  • packing problems,
  • the Euclidean traveling salesman problem,
  • minimal Euclidean matching,
  • minimal Euclidean spanning tree.

For the analysis of problems of this type, several techniques and concepts have been developed and will be introduced and applied in this course. Some of these are

  • concentration inequalities and concentration of measure,
  • subadditivity and superadditivity,
  • martingale methods,
  • isoperimetry,
  • entropy.