\documentclass[12pt]{article}
\usepackage{url}
\usepackage{fullpage}
\begin{document}
\thispagestyle{empty}
\begin{center}
{\Large \textsc{CS 270 Combinatorial Algorithms \& Data Structures} --- Spring 2023}
\bigskip
{\Large \textsc{Problem Set 5}}
\smallskip
Due: 11:59pm, Friday, March 17th
Solution maximum page limit: 4 pages
\bigskip
{\footnotesize See homework policy at \url{https://cs270.org/spring23/syllabus/#homework-policies}}
\end{center}
\paragraph{Problem 1:} (20 points) Here you will prove that \textsf{LRU} is $2$-competitive against an omniscient paging rule with half the cache size. More specifically, let $\mathcal A_k$ denote an algorithm $\mathcal A$ with cache size $k$. Show that for any $h\le k$,
$$
\mathop{cost}(\mathsf{LRU}_k) \le \left(\frac k{k-h+1}\cdot \mathsf{OPT}_h\right) + h
$$
\paragraph{Problem 2:} (20 points) Prove ``approximate complementary slackness'' from Lecture 16.
\paragraph{Problem 3:} (20 points; Problem due to Nikhil Bansal). In Lecture 15 we showed that 1-bit LRU is $k$-competitive. Let us try to give a different proof using the online primal-dual framework. First, let's write the primal LP. Let $k$ denote the size of cache and $n$ denote the total number of pages in the universe. There are variables $x^t_i$ for each page $i$. This is intended to be $1$ if $i$ is absent from the cache immediately after servicing the request time $t$, and $0$ otherwise. Let $r(t)\in\{1,\ldots,n\}$ denote the page requested at time $t$. The variable $z_i^t$ is intended to be $1$ if we evict page $i$ at time $t$ and is $0$ otherwise. This leads to the following LP relaxation:
\begin{eqnarray*}
\min \sum_{t=1}^T \sum_{i=1}^n z_i^t & & \\
s.t. \quad \sum_{i=1}^n x^t_i & \geq & n-k \qquad \forall 1\le t\le T\\
x^t_{r(t)} & \leq & 0 \qquad \forall 1\le t\le T \\
x^{t}_i & \leq & 1 \qquad \forall 1\le i\le n, 1\le t\le T \\
z^t_{i} & \geq & x^{t}_i - x^{t-1}_i \qquad \forall 1\le i\le n, 1< t\le T \\
x^t_i, z^{t}_i & \geq & 0 \qquad \forall 1\le i\le n, 1\le t\le T
\end{eqnarray*}
\begin{itemize}
\item[(a)] (6 points) Write the dual of the above LP. (Note any LP can be written in the form stated in class.) \textbf{Hint:} Other than the final nonnegativity constraints, there are four types of constraints above. These should give rise to four types of variables in the dual.
\item[(b)] (14 points) Give a primal/dual analysis of the online 1-bit LRU algorithm, showing that it suffers at most $k(\textsf{OPT} + 1)$ page faults. \textbf{Hint:} One of the types of variables in the dual, let's call them the $d_i^t$ variables, should keep track of whether page $i$ is marked at time $t$. Define a potential function $\Phi(t) = \sum_i d_i^t$ and show that if $P(t)$ is the primal cost at time $t$ and $D(t)$ is the dual profit, then there is a way to maintain primal and dual feasible solutions online so that for all $t$, $P(t) \le k\cdot D(t) + (\Phi(t) - \Phi(t-1))$.
\end{itemize}
\paragraph{Problem 4:} (1 point) How much time did you spend on this problem set? If you can remember the breakdown, please report this per problem. (sum of time spent solving problem and typing up your solution)
\end{document}