Worst case instances are fragile [Elektronische Ressource] : average case and smoothed competitive analysis of algorithms / Guido Schäfer

WORST CASE INSTANCES ARE FRAGILEAverage Case and Smoothed Competitive Analysis of AlgorithmsGuido SchäferDissertationzur Erlangung des GradesDoktor der Ingenieurwissenschaften (Dr.-Ing.)der Naturwissenschaftlich-Technischen Fakultätender Universität des SaarlandesSaarbrücken2004Tag des Kolloquiums: 30. April 2004Dekan: Prof. Dr. Jörg EschmeierPrüfungsausschuss: Prof. Dr. Reinhard Wilhelm (Vorsitzender)Prof. Dr. Dr.-Ing. E. h. Kurt Mehlhorn (Berichterstatter)Prof. Dr. Stefano Leonardi (Berichterstatter)Dr. Ernst AlthausABSTRACTWe describe three results in this thesis. We first present a heuristic improvement for a shortestpath problem, which we termed single-source many-targets shortest path problem. In thisproblem, we need to compute a shortest path from a source node to a node that belongs to adesignated target set. Dijkstra’s algorithm can be used to solve this problem. We are interestedin the single-source many-targets shortest path problem since matching algorithms repeatedlysolve this problem so as to compute a maximum weighted matching in a bipartite graph. Theheuristic is easy to implement and, as our experiments show, considerably reduces the runningtime of the matching algorithm. We provide an average case analysis which shows that asubstantial fraction of queue operations is saved by Dijkstra’s algorithm if the heuristic isused.The second and third result are about the extension of smoothed complexity to the areaof online algorithms.