Analyse von Heuristiken

Inhaltlich unveranderte Neuauflage. Heuristiken treten insbesondere im Zusammenhang mit Optimierungsproblemen in Erscheinung.

Beim Problem kurzester Superstrings werden Heuristiken herangezogen, da das Problem APX-Vollstandigkeit ist.

Die prominenteste Heuristik fur das Problem kurzester Superstrings ist die Greedy-Heuristik, deren Approximationsfaktor derzeit jedoch nur unzureichend beschrankt werden kann.

Fur die nichttriviale, groe Teilklasse der bilinearen Greedyordnungen wird gezeigt, dass die Lange des von der Greedy-Heuristik gefundenen Superstrings und die des optimalen Superstrings sich hochstens um die Groe einer optimalen Kreisuberdeckung 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 Lokalitat eingesetzt werden.

Es wird untersucht, wovon Queueing Strategien ihre lokalen Entscheidungen abhangig machen sollten, um ein gewisses Qualitatsmerkmal zu erreichen.

Es wird gezeigt, dass jede Queueing Strategie, die ohne Zeitstempel arbeitet, zu einer exponentiell groer Verzogerung gezwungen werden kann.