Approximability of cycle covers and smoothed analysis of binary search trees

Abstract

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.