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: December 15th, 1997

Universität Bonn / Informatik / Abteilung V / english version