Seminar Online-Algorithmen, SS 98

Vortragsthemen

A. Einführung

In diesem Vortrag sollen die wichtigsten Ergebnisse aus dem Artikel von Sleator und Tarjan [1] vorgestellt werden, mit dem das Gebiet der Online-Algorithmen seinen Anfang genommen hat, und der sich mit den Problemen der Verwaltung von Listen und von Seiten im Hauptspeicher befaßt. Insbesondere sollen die Begriffe "amortisierte Analyse" und "Kompetitivitätsfaktor" erklärt werden. Letzterer findet sich nicht in [1] definiert, und es sollte auf das Buch von Raghavan und Motwani [2] zurückgegriffen werden.

Literatur

  1. D. D. Sleator and R. E. Tarjan, Amortized efficiency of list update and paging rules, Comm. ACM 28 (1985), pp. 202-208.

  2. R. Motwani and P. Raghavan, Randomized Algorithms, Chap. 13, Online algorithms, Cambridge University Press, Cambridge, 1995.

  3. B. Chun, CS294-1 On-line Computation and Network Algorithms, Lecture 3, Scribe notes (Y. Bartal, lecturer), Spring 1997, Sect. 3.1.2.1, http://www.icsi.berkeley.edu/~yairb/courses/on-line.

B. Das k-Server-Problem: Spezialfälle

Bei dem k-Server-Problem gibt es k Server in einem metrischen Raum, und nacheinander auftauchende Anfragen in diesem metrischen Raum müssen dadurch bedient werden, daß ein Server zum Ort jeder Anfrage bewegt wird, bevor die nächste Anfrage bekannt wird; dabei entstehen Kosten, die proportional zum bewegten Abstand sind, und die minimiert werden sollen. In diesem Vortrag soll das k-Server-Problem eingeführt werden, und untere Schranken aus [1] sowie Algorithmen für Spezialfälle des k-Server-Problems aus [1,2,3] sollen vorgestellt werden.

Literatur

  1. M. S. Manasse, L. A. McGeoch, and D. D. Sleator, Competitive algorithms for server problems, J. Algorithms 11 (1990), pp. 208-230.

  2. M. Chrobak, H. Karloff, T. Payne, and S. Vishwanathan, New results on server problems, SIAM J. Disc. Math. 4 (1991), pp. 172-181.

  3. M. Chrobak and L. L. Larmore, An optimal on-line algorithm for k-servers on trees, SIAM J. Comput. 20 (1991), pp. 144-148.

C. Randomisierung in Online-Algorithmen

Randomisierung erlaubt in vielen Fällen eine viel bessere Online-Performanz, wovon wir in späteren Vorträgen Beispiele sehen werden. Allerdings muß man jetzt bei der Definition des Kompetitivitätsfaktors etwas aufpassen, und es gibt mehrere sinnvolle Definitionen, die meist mit Hilfe von verschieden mächtigen "Gegnern" formuliert werden. Der Vortrag soll diese Grundlagenfragen erörtern und allgemeine Ergebnisse zeigen, die die Mächtigkeit der verschiedenen Gegnertypen zueinander und zum deterministischen Fall in Beziehung setzen.

Literatur

  1. S. Ben-David, A. Borodin, R. M. Karp, G. Tardos, and A. Wigderson, On the power of randomization in on-line algorithms, Algorithmica 11 (1994), pp. 2-14.

  2. R. Motwani and P. Raghavan, Randomized Algorithms, Chap. 13, Online algorithms, Cambridge University Press, Cambridge, 1995.

D. Randomisiertes Paging

Dieser Vortrag soll der Frage nachgehen, wie gut das Paging-Problem unter Benutzung von Randomisierung gelöst werden kann. Material hierzu findet sich in den Quellen [1,2]. Außerdem sollen die interessantesten Ergebnisse aus [3] kurz und ohne Beweise vorgestellt werden.

Literatur

  1. A. Fiat, R. M. Karp, M. Luby, L. A. McGeoch, D. D. Sleator, and N. E. Young, Competitive paging algorithms, J. Algorithms 12 (1991), pp. 685-699.

  2. R. Motwani and P. Raghavan, Randomized Algorithms, Chap. 13, Online algorithms, Cambridge University Press, Cambridge, 1995.

  3. P. Raghavan and M. Snir, Memory versus randomization in on-line algorithms, Proc. 16th International Colloquium on Automata, Languages and Programming (ICALP 1989), Lecture Notes in Computer Science, Springer-Verlag, Berlin, Vol. 372, pp. 687-703.

E. Randomisierte Algorithmen für die Verwaltung von Listen

In diesem Vortrag geht es um die besten randomisierten Algorithmen für die Verwaltung von Listen (deterministische Algorithmen haben wir schon in Vortrag A gesehen) und um untere Schranken für solche randomisierten Algorithmen.

Literatur

  1. N. Reingold, J. Westbrook, and D. D. Sleator, Randomized competitive algorithms for the list update problem, Algorithmica 11 (1994), pp. 15-32.

  2. S. Albers, B. von Stengel, and R. Werchner, A combined BIT and TIMESTAMP algorithm for the list update problem, Inform. Process. Lett. 56 (1995), pp. 135-139.

  3. B. Teia, A lower bound for randomized list update algorithms, Inform. Process. Lett. 47 (1993), pp. 5-9.

F. Das k-Server-Problem: Der allgemeine Fall

Koutsoupias und Papadimitriou [1] beschreiben den besten bekannten Algorithmus für das allgemeine k-Server-Problem, und Grove [2] zeigt, daß ein sehr einfacher randomisierter Algorithmus für dieses Problem Ck-kompetitiv ist, wobei Ck nur von k abhängt (aber ziemlich groß ist). Im Vortrag soll eine der beiden Arbeiten vorgestellt und die Ergebnisse der anderen Arbeit kurz skizziert werden. Dieses Thema kann wahlweise von zwei Personen bearbeitet werden.

Literatur

  1. E. Koutsoupias and C. H. Papadimitriou, On the k-server conjecture, J. Assoc. Comput. Mach. 42 (1995), pp. 971-983.

  2. E. F. Grove, The harmonic online k-server algorithm is competitive, in On-Line Algorithms (L. A. McGeoch and D. D. Sleator, eds.), DIMACS Series in Discrete Mathematics and Theoretical Computer Science, Vol. 7, Amer. Math. Soc., 1992.

G. Datenverwaltung in verteilten Systemen

In diesem Vortrag soll das Problem betrachtet werden, Dateien bei den Prozessoren eines Prozessornetzwerks möglichst kostengünstig abzuspeichern. Ein Zugriff eines Prozessors P auf eine beim Prozessor P' gespeicherte Datei hat Kosten proportional zum Abstand zwischen P und P' im Netz, aber Dateien können auch, unter größeren Kosten, durch das Netzwerk verschickt werden (um näher an den häufigsten Benutzern zu sein).

Literatur

  1. D. L. Black and D. D. Sleator, Competitive algorithms for replication and migration problems, Tech. Rep. No. CMU-CS-89-201, Carnegie-Mellon University, 1989.

  2. J. Westbrook, Randomized algorithms for multiprocessor page migration, SIAM J. Comput. 23 (1994), pp. 951-965.

H. Färbung von Graphen

Eine Färbung der Knoten eines ungerichteten Graphen ist legal, wenn keine zwei benachbarten Knoten dieselbe Farbe haben. Ein häufig auftretendes Problem besteht darin, einen Graphen unter Benutzung von möglichst wenig Farben legal zu färben. In der Online-Variante des Problems werden die Knoten mit ihren Kanten zu früheren Knoten nacheinander bekannt, und jeder Knoten muß unwiderruflich gefärbt werden, sobald er bekannt wird. Der Vortrag soll die besten bekannten deterministischen und randomisierten Online-Algorithmen für Graphenfärbung vorstellen.

Literatur

  1. M. H. Halldórsson, Parallel and on-line graph coloring, J. Algorithms 23 (1997), pp. 265-280.

  2. L. Lovász, M. Saks, and W. T. Trotter, An on-line graph coloring algorithm with sublinear performance ratio, Disc. Math. 75 (1989), pp. 319-325.

I. Navigieren in unbekannter Umgebung

Dieser Vortrag betrachtet das Problem, sich von einem Punkt zu einem anderen Punkt in der Ebene oder im Raum in der Gegenwart von undurchdringlichen Hindernissen zu bewegen. Dieses Problem ist kein eigentliches Online-Problem (und der Vortrag soll erklären, warum), aber bei seiner Behandlung werden ähnliche Methoden eingesetzt. Das Thema kann wahlweise von zwei Personen bearbeitet werden.

Literatur

  1. A. Blum, P. Raghavan, and B. Schieber, Navigating in unfamiliar geometric terrain, SIAM J. Comput. 26 (1997), pp. 110-137.

  2. E. Bar-Eli, P. Berman, A. Fiat, and P. Yan, Online navigation in a room, J. Algorithms 17 (1994), pp. 319-341.

J. Finanz-Transaktionen

Finanzmärkte und Börsen erfordern ständig Entscheidungen auf der Basis von unvollständiger Information. Im Vortrag soll beispielhaft untersucht werden, wie man angesichts eines schwankenden Umtauschkurses am besten einen Umtausch zwischen zwei Währungen vornimmt. Der Vortrag soll auch diskutieren, ob alle Seminarteilnehmer jetzt reich werden können.

Literatur

  1. R. El-Yaniv, A. Fiat, R. Karp, and G. Turpin, Competitive analysis of financial games, Proc. 33rd Annual Symposium on Foundations of Computer Science (FOCS 1992), pp. 327-333.

  2. A. Chou, J. Cooperstock, R. El-Yaniv, M. Klugermann, and T. Leighton, The statistical adversary allows optimal money-making trading strategies, Proc. 6th ACM-SIAM Symposium on Discrete Algorithms (SODA 1995), pp. 467-476.