[Mittagsseminar TI] Fwd: [i-prof] Einladung zur Verteidigung meiner Bachelorarbeit

[Wolfgang Mulzer <mulzer@inf.fu-berlin.de>]

-------- Forwarded Message --------
Subject: [i-prof] Einladung zur Verteidigung meiner Bachelorarbeit
Date: Tue, 10 Feb 2015 19:11:31 +0100
From: Alexander Kauer <alexander.kauer@fu-berlin.de>
To: i-profs@inf.fu-berlin.de, i-wimis@inf.fu-berlin.de, 
i-studi@inf.fu-berlin.de
CC: renee.zentiks@fu-berlin.de

Sehr geehrte Damen und Herren,

hiermit lade ich Sie zur Verteidigung meiner Bachelorarbeit mit dem Titel

	Implementation of and Experiments on
	Centerpoint Approximation Algorithms

ein. Die Verteidigung findet Dienstag, den 17.02.2015 im Rahmen des
Mittagssemiars für Theoretische Informatik um 12:00 s.t. in SR055 statt.
Die Arbeit wurde von Prof. Dr. Wolfgang Mulzer betreut, Zweitkorrektor
ist Prof. Dr. Helmut Alt.

Mit freundlichen Grüßen

Alexander Kauer


Zusammenfassung:
Der eindimensionale Median ist einer der grundlegenden Bestandteile der
Informatik und Mathematik. Die Idee des Medians kann auf höhere
Dimensionen als Centerpoint verallgemeinert werden. Hierbei zerlegen
alle Hyperebenen durch einen Centerpoint die Eingabe in zwei etwa gleich
große Teile.

Der bisher schnellste Algorithmus um einen Centerpoint für n Punkte in d
Dimensionen zu finden hat eine erwartete Laufzeit von O(n^(d - 1)).
Durch die in d exponentielle Laufzeit ist dieser Algorithmus nur für
kleinere Dimensionen sinnvoll anwendbar. Es ist kein Algorithmus bekannt
um einen Centerpoint in polynomieller Laufzeit bezüglich sowohl n als
auch beliebiger Dimension d zu finden. Aus diesem Grund sind vor allem
approximative Algorithmen für dieses Themengebiet von großem Interesse.

In dieser Arbeit werden mehrere approximative Algorithmen für eine
beliebige Anzahl an Dimensionen vorgestellt. Diese Algorithmen haben ein
bezüglich Anzahl der Punkte n und der Dimension d polynomielles
Laufzeitverhalten. Weiterhin wurden diese Algorithmen implementiert und
deren durchschnittliche Güte bei zufälliger Eingabe ermittelt, da die
Algorithmen nur eine untere Schranke der Güte des Ergebnisses garantieren.

_______________________________________________
Automatischer Mailverteiler an Gruppe 'ml-i-prof-mi'.
Hinweise dazu siehe Hilfeseite:
https://www.mi.fu-berlin.de/w/Tec/AnkuendigungsVerteiler

Attachment: smime.p7s
Description: S/MIME Cryptographic Signature