ELC Seminar on Theoretical Computer Science in UEC

We are going to have a seminar on Theoretical Computer Science,  
which consists of a talk by 
Professor Wolfgang Bein (University of Nevada, Las Vegas). 
We hope you all participate.  

--

Time and Date: 14:000--15:30, July 16 (Wed), 2014.
Place: Room 302, 3F, West-9 BLDG, The University of Electro-Communications
http://www.uec.ac.jp/eng/about/access/

Speaker: Wolfgang Bein (University of Nevada, Las Vegas)

Title: Knowledge States: A Tool in Randomized Online Algorithms

Abstract: 
We introduce the concept of knowledge states; many well-known algorithms can 
be viewed as knowledge state algorithms. The knowledge state approach can 
be used to to construct competitive randomized online algorithms and study 
the tradeoff between competitiveness and memory.
    We give new results for the two server problem and the paging problem.
We present a knowledge state algorithm for the two server problem over 
Cross Polytope Spaces with a competitive ratio of 19/12, and show that 
it is optimal against the oblivious adversary.
    Regarding the paging problem, Borodin and El-Yaniv had listed as an
open question whether there exists an H_k-competitive randomized 
algorithm which requires O(k) memory for k-paging. We have answered 
this question in the affirmative using knowledge state techniques.

Contact to: ITO Hiro (UEC, Japan)
http://www.alg.cei.uec.ac.jp/itohiro/