Analyse von Heuristiken

Die Neuauflage behandelt Heuristiken bei Optimierungsproblemen, insbesondere beim kürzesten Superstring. Die Greedy-Heuristik wird analysiert, wobei ihr Approximationsfaktor begrenzt ist. Zudem wird die Abhängigkeit von Queueing Strategien im Adversarial Queueing Modell untersucht, insbesondere hinsichtlich der lokalen Entscheidungsfindung und deren Auswirkungen auf die Verzögerung.