[
Universität Bonn
|
Informatik
|
Abteilung V
|
english version
]
PROCOPE: VC-Dimension und Approximation
Das Projekt konzentriert sich auf die miteinander verzahnten Themen
der Zufallsentscheidungen und dem Begriff der Vapnik-Chervonenkis (VC)
Dimension, die beim Entwurf von randomisierten Approximationsalgorithmen
und bei den verschiedenen Methoden sie zu derandomisieren, nützlich sind.
Das Interesse am Begriff der VC-Dimension ist durch folgende Bemerkung
gerechtfertigt: Bei der Analyse von Zufallsentscheidungen und von
randomisierten Algorithmen sind die wichtigsten Werkzeuge das Gesetz der
grossen Zahlen, und die Ungleichungen für große Abweichungen
(Chernoffsche Bounds). Grob gesagt ist die VC-Dimension gerade der Begriff,
der das Gesetz der grossen Zahlen und die Ungleichungen für große
Abweichungen zueinander
in Beziehung setzt und somit die Kontrolle des Restgliedverhaltens von
unendlich vielen Zufallsvariablen erlaubt.
Ferner untersuchen wir Approximationsverfahren auf dichten Instanzen
von Optimierungsproblemen, beispielsweise die Approximation
eines vertex cover und BISECTION in einem dichten Graphen.
Letzte Änderung: 8. September 2004
[
Universität Bonn
|
Informatik
|
Abteilung V
|
english version
]