Spezielle Online-Probleme

Kontakt

Janosch Fuchs

Telefon

work
+49 241 80 21115

E-Mail

E-Mail
  Ausarbeiten einer Arbeit Urheberrecht: Lukas Netz

Online Algorithmen bestimmen Lösungen für Probleme bei denen die Eingabe nicht bekannt ist. Durch die mangelnde Information über die Zukunft ist es oftmals nicht Möglich die Probleme optimal zu lösen. Um Probleme mit einander vergleichen zu können gibt es den so genannten „competitive ratio“, der das Verhältnis von der berechneten Lösung zu der optimalen bestimmt.

Einige Probleme können aber beliebig schlecht gelöst werden. Da sich diese Probleme nicht mit dem klassischen Online Modell vergleichen lassen, wurde „advice complexity“ eingeführt. In dieser Erweiterung hat der Algorithmus zugriff auf ein „advice tape“ beschrieben von einem hilfreichen Orakel. Das „advice tape“ ist in Binärform gegeben. Zugriff auf die Informationen generiert kosten, hilft aber bei der Lösung des Problems. Die Anzahl der benötigten Bits, vor Fertigstellung der Lösung, ist die „advice complexity“ des Algorithmus. Dies ermöglicht es nun obere und untere Schranken, für die „advice complexity“ von vorher nicht vergleichbaren online Problemen, zu bestimmen.

Das Ziel dieser Arbeit ist es für graphentheoretische Probleme wie „Graph Exploration“ untere und obere Schranken zu definieren. Im „Graph Expoloration Problem“ muss die kürzeste Tour bestimmt werden, die alle Knoten eines Graphen besucht ohne die Struktur im Vorhinein zu kennen. Die Bisher beste bekannte obere Schranke für das Problem bestand darin alle Knoten nach ihren Erstbesuchen zu nummerieren und diese Ordnung dem Algorithmus mitzuteilen. Dies zu kommunizieren kostet n log(n) „advice bits“. Es ist jedoch auch Möglich mit linearem aufwand eine optimale Tour zu kodieren.