Mittagsseminar (in cooperation with J. Lengler, A. Steger, and D. Steurer)

Date and Time: Thursday, November 10, 2005, 12:15 pm

Duration: This information is not available in the database

Location: This information is not available in the database

Speaker: Alex Souza-Oftermatt

A New Lower Bound for Paging

This talk is the continuation of the talk on paging on Tuesday. Recall that the paging problem is defined as follows. Consider a two-level memory system with fast, but small cache and slow, but large main memory. A sequence of requests to pages has to be served by making each requested page available in the cache. A paging strategy replaces pages in the cache with requested ones. The aim is to minimize the number of page faults that occur whenever a requested page is not in the cache.

First we give some intuition for the lower bound on the offline optimum number of page faults presented in the previous talk. Then we sketch a proof of this lower bound. The proof relies on a LP-formulation of the paging problem. We show that an algorithm which constructs a feasible solution to the dual of that LP achieves at least the claimed value.

Upcoming talks     |     All previous talks     |     Talks by speaker     |     Upcoming talks in iCal format (beta version!)

Previous talks by year:   2025  2024  2023  2022  2021  2020  2019  2018  2017  2016  2015  2014  2013  2012  2011  2010  2009  2008  2007  2006  2005  2004  2003  2002  2001  2000  1999  1998  1997  1996  

Information for students and suggested topics for student talks

Automatic MiSe System Software Version 1.4803M   |   admin login