Analyse von Heuristiken

Inhaltlich unver nderte Neuauflage. Heuristiken treten insbesondere im Zusammenhang mit Optimierungsproblemen in Erscheinung. Beim Problem k rzester Superstrings werden Heuristiken herangezogen, da das Problem APX-Vollst ndigkeit ist. Die prominenteste Heuristik f r das Problem k rzester Superstrings ist die Greedy-Heuristik, deren Approximationsfaktor derzeit jedoch nur unzureichend beschr nkt werden kann. F r die nichttriviale, gro e Teilklasse der bilinearen Greedyordnungen wird gezeigt, dass die L nge des von der Greedy-Heuristik gefundenen Superstrings und die des optimalen Superstrings sich h chstens um die Gr e einer optimalen Kreis berdeckung der Strings unterscheiden. Mit der Analyse von Queueing Strategien im Adversarial Queueing Modell wird auch ein Fall betrachtet, in dem Heuristiken auf Grund von anwendungsspezifischen Forderungen wie Online-Setup und Lokalit t eingesetzt werden. Es wird untersucht, wovon Queueing Strategien ihre lokalen Entscheidungen abh ngig machen sollten, um ein gewisses Qualit tsmerkmal zu erreichen. Es wird gezeigt, dass jede Queueing Strategie, die ohne Zeitstempel arbeitet, zu einer exponentiell gro er Verz gerung gezwungen werden kann.