Logo des Repositoriums
 
Textdokument

Approximability of cycle covers and smoothed analysis of binary search trees

Lade...
Vorschaubild

Volltext URI

Dokumententyp

Zusatzinformation

Datum

2006

Autor:innen

Zeitschriftentitel

ISSN der Zeitschrift

Bandtitel

Verlag

Gesellschaft für Informatik

Zusammenfassung

Der Beitrag enthält eine Zusammenfassung der Dissertation Approxima- ” bility of Cycle Covers and Smoothed Analysis of Binary Search Trees“. Eine Zyklenüberdeckung eines Graphen ist ein Teilgraph, der nur aus Zyklen besteht, so dass jeder Knoten Teil genau eines Zyklus ist. Bei einer L-Zyklenüberdeckung muss zusätzlich die Länge jedes Zyklus in der Menge L liegen. Im ersten Teil der Dissertation wurde die Komplexität und Approximierbarkeit des Problems untersucht, L- Zyklenüberdeckungen maximalen Gewichts zu berechnen. Es wurden einerseits effiziente Approximationsalgorithmen zur Berechnung von L-Zyklenüberdeckungen entwickelt. Andererseits wurde bewiesen, dass L-Zyklenüberdeckungsprobleme für fast alle Mengen L nicht beliebig gut approximiert werden können. Im zweiten Teil der Dissertation wurde eine Smoothed Analysis der Höhe binärer Suchbäume durchgeführt. Die Smoothed Analysis interpoliert zwischen der Worst- Case-Komplexität, die oft zu pessimistisch ist und durch pathologische“ Instanzen ” dominiert wird, und der Average-Case-Komplexität, die oft zu optimistisch ist.

Beschreibung

Manthey, Bodo (2006): Approximability of cycle covers and smoothed analysis of binary search trees. Ausgezeichnete Informatikdissertationen 2005. Bonn: Gesellschaft für Informatik. PISSN: 1617-5468. ISBN: 978-3-88579-330-X. pp. 57-66

Schlagwörter

Zitierform

DOI

Tags