Campus Event Calendar
Event Entry
What and Who
Zwei neue Familien von deterministischen List Update Algorithmen
Frank Schulz
Seminar des Graduiertenkollegs
AG 1, AG 2
AG Audience
English
Note: We use this to send email in the morning.
Date, Time and Location
Monday, 3 November 97
16:00
60 Minutes
45 - FB14
015
Saarbrücken
Abstract
Wir betrachten das Problem, Online-Zugriffe auf eine Liste zu
bearbeiten. Ein sogenannter List Update Algorithmus dient dazu,
die Ordnung der Elemente dynamisch zu veraendern und dadurch
die Suchkosten fuer zukuenftige Zugriffe zu reduzieren.
bearbeiten. Ein sogenannter List Update Algorithmus dient dazu,
die Ordnung der Elemente dynamisch zu veraendern und dadurch
die Suchkosten fuer zukuenftige Zugriffe zu reduzieren.
Wir stellen die Klasse der SORT-BY-RANK(alpha)
Algorithmen vor, deren Verhalten zwischen dem der Strategien
MOVE-TO-FRONT und TIMESTAMP liegt. Fuer jedes reelle
alpha, 0 kleiner/gleich alpha kleiner/gleich 1, ist SBR(alpha) 2-kompetitiv.
Wir fuehren ausserdem eine weitere Klasse SORT-BY-DELAY(k) ein.
Fuer k groesser/gleich 2 ist SBD(k) k-kompetitiv, und auf stochastischen
Anfragequellen ohne Gedaechtnis sind diese Regeln asymptotisch optimal.
Empirische Untersuchungen mit verschiedenen Anfragefolgen werden
ebenfalls vorgestellt.
Contact
--email hidden
passcode not visible
logged in users only
Tags, Category, Keywords and additional notes
EINLADUNG ZUM SEMINAR DES GRADUIERTENKOLLEGS INFORMATIK
Am Montag, den 03.11.1997, spricht um 16 c. t. Uhr im Gebaeude 45,
EG, Raum 015,
Frank Schulz
zum Thema
Zwei neue Familien von deterministischen List Update Algorithmen
Wir betrachten das Problem, Online-Zugriffe auf eine Liste zu
bearbeiten. Ein sogenannter List Update Algorithmus dient dazu,
die Ordnung der Elemente dynamisch zu veraendern und dadurch
die Suchkosten fuer zukuenftige Zugriffe zu reduzieren.
Wir stellen die Klasse der SORT-BY-RANK(alpha)
Algorithmen vor, deren Verhalten zwischen dem der Strategien
MOVE-TO-FRONT und TIMESTAMP liegt. Fuer jedes reelle
alpha, 0 kleiner/gleich alpha kleiner/gleich 1, ist SBR(alpha) 2-kompetitiv.
Wir fuehren ausserdem eine weitere Klasse SORT-BY-DELAY(k) ein.
Fuer k groesser/gleich 2 ist SBD(k) k-kompetitiv, und auf stochastischen
Anfragequellen ohne Gedaechtnis sind diese Regeln asymptotisch optimal.
Empirische Untersuchungen mit verschiedenen Anfragefolgen werden
ebenfalls vorgestellt.
Alle InteressentInnen sind zu dem Vortrag herzlich eingeladen.
Am Montag, den 03.11.1997, spricht um 16 c. t. Uhr im Gebaeude 45,
EG, Raum 015,
Frank Schulz
zum Thema
Zwei neue Familien von deterministischen List Update Algorithmen
Wir betrachten das Problem, Online-Zugriffe auf eine Liste zu
bearbeiten. Ein sogenannter List Update Algorithmus dient dazu,
die Ordnung der Elemente dynamisch zu veraendern und dadurch
die Suchkosten fuer zukuenftige Zugriffe zu reduzieren.
Wir stellen die Klasse der SORT-BY-RANK(alpha)
Algorithmen vor, deren Verhalten zwischen dem der Strategien
MOVE-TO-FRONT und TIMESTAMP liegt. Fuer jedes reelle
alpha, 0 kleiner/gleich alpha kleiner/gleich 1, ist SBR(alpha) 2-kompetitiv.
Wir fuehren ausserdem eine weitere Klasse SORT-BY-DELAY(k) ein.
Fuer k groesser/gleich 2 ist SBD(k) k-kompetitiv, und auf stochastischen
Anfragequellen ohne Gedaechtnis sind diese Regeln asymptotisch optimal.
Empirische Untersuchungen mit verschiedenen Anfragefolgen werden
ebenfalls vorgestellt.
Alle InteressentInnen sind zu dem Vortrag herzlich eingeladen.