[Mittagsseminar TI] Mittagsseminar am 25.02.2016

[Tamara Knoll <knoll@mi.fu-berlin.de>]

Im Rahmen des Mittagsseminars der
Theoretischen Informatik der FU Berlin
spricht am

  	Donnerstag, 25.02.2016
        Maximilian Haselbek
        zum Thema: Verified Analysis of List Update Algorithms

	Abstract
	We formalize the quantitative analysis of a number of classical
	algorithms for the list update problem: 2-competitiveness of
	move-to-front, the lower bound of 2 for the competitive- ness of
	deterministic list update algorithms and 1.6-competitiveness of the
	randomized COMB algorithm, the best randomized list update algorithm
	known to date.

Weitere Resourcen zu der Formalisierung gibt es im AFP Eintrag [1].

[1] http://afp.sourceforge.net/entries/List_Update.shtml


***************************************************
Ort: Takustr. 9, RM 055

Uhrzeit: 12 Uhr s.t.
***************************************************

-- 
------------------------------------------------------------------------
Tamara Knoll                         Sekretariat Theoretische Informatik  
Institut für Informatik                           knoll@inf.fu-berlin.de  
Freie Universität Berlin                         Phone: +49-30-838 75103
Takustr.9, D-14195 Berlin                          Fax: +49-30-838 75192 
------------------------------------------------------------------------