From worst-case to average-case efficiency [Elektronische Ressource] : approximating combinatorial optimization problems / vorgelegt von Kai Plociennik

From Worst-Case to Average-Case Eciency –Approximating Combinatorial OptimizationProblemsvon der Fakultät für Informatikder Technischen Universität Chemnitzgenehmigte Dissertationzur Erlangung des akademischen GradesDoktor der Naturwissenschaften (Dr. rer. nat.)vorgelegt vonDipl.-Inf. Kai Plociennikgeboren am 13. Juni 1975 in RecklinghausenTag der Einreichung: 3. August 2010Tag der Verteidigung: 27. Januar 2011Gutachter: Prof. Dr. Hanno Lefmann,Technische Universität ChemnitzProf. Dr. Andreas Goerdt,Technische Universität ChemnitzAbstractFor many important combinatorial optimization problems, inapproximability re-sults exist, stating that under reasonable complexity-theoretic assumptions such asP , NP, no worst-case ecient algorithm exists that achieves a certain (good)approximation guarantee. This is an unfortunate situation, since in practical appli-cations, one often has to find a (good) solution for such a problem, and resourceslike the available time are limited. It turns out, however, that many problems withsuch inapproximability results can be solved satisfactorily in practice, i.e., there arealgorithms which typically find in relatively short time a relatively good solution.Hence, there is a discrepancy between worst-case results and empirical observa-tions.The reason for this discrepancy is that often, worst-case instances for an al-gorithm are somehow artificial and do not typically appear in practice.