Die Begrenzung des "Fehlers" in der kombinatorischen Optimierung

George Mertzios, Chair of Computer Science 1

Es ist oft der Fall, dass eine optimale Lösung nicht effizient zu berechnen ist. Ein Grund dafür kann sein, dass der ganze Input nicht verfügbar ist, oder dass das betrachtete Problem sehr schwer ist (NP-hart). Dafür bauen wir Online-Algorithmen und Approximationsalgorithmen, die aber nicht beliebig weit von dem wirklichen Optimum liegen. Außerdem gibt es Systeme, wo niemand volle Kontrolle hat (mehrere Users, keine zentrale Instanz). Für diese Systeme, ist es sinnvoll zu berechnen, wie schlecht eine Lösung (Equilibrium) im Vergleich zu einem globalem Optimum sein kann (Price of Anarchy). Wir stellen diese Themen vor, um einen kurzen Überblick über die Begrenzung des “Fehlers” in der kombinatorischen Optimierung zu erhalten.