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.