diff options
| -rw-r--r-- | ps4/main.tex | 31 |
1 files changed, 16 insertions, 15 deletions
diff --git a/ps4/main.tex b/ps4/main.tex index c8a8b3f..6c0915e 100644 --- a/ps4/main.tex +++ b/ps4/main.tex @@ -59,7 +59,7 @@ and $y$ satisfy the approximate complementary slackness conditions. Then: \end{align*} where we used the first approximate complementary slackness condition in the first line. In the second line, we first used that the dot product is linear in -its first coordinate, then the definition of the matrix-product vector. Finally +its first coordinate, then the definition of the matrix-vector product. Finally we used the second complementary slackness condition in the last line. \section*{Problem 2} @@ -100,7 +100,7 @@ for page $i$ at time $t$ arrives: cache which are not $i$ to maintain dual feasibility. \end{enumerate*} We show that at time $t$, $P(t) \leq k D(t) + \big(\Phi(t) - \Phi(t-1)\big)$ in -all three cases. $P(t)$ is simply one or zero depending on whether or not ther +all three cases above. $P(t)$ is simply one or zero depending on whether or not there has been an eviction. $\Delta\Phi$ is the difference in the number of marked pages: \begin{enumerate*} @@ -108,17 +108,17 @@ pages: marked). This is ok. \item $P(t) = 1$ (one eviction), $D(t) = 0$ and $\Delta\Phi = 1$ (one page marked). This is still ok. - \item $P(t) = 1$ (one eviction), $D(t) = (n-k) - (n-k-1)$ (there are + \item $P(t) = 1$ (one eviction), $D(t) = (n-k) - (n-k-1) = 1$ (there are $n-k+1$ pages outside the cache which are not $i$) and $\Delta\phi = -k - + 1$. This is still ok. + + 1$. This is again ok. \end{enumerate*} -If we some the previous inequality over $t$, we have $\sum_t P(t)$ on the +If we sum the previous inequality over $t$, we have $\sum_t P(t)$ on the left-hand side, this is the cost of the $1$-bit LRU algorithm. On the right hand side, we get $k\sum_t D(t) + \Phi(T) - \Phi(1)$. The difference in potential is at most $k$, and $\sum_t D(t)$, the value of our dual solution is less than the value of any feasible solution for the primal (weak duality) and -in particual the optimal integral solution $\text{OPT}$. Hence, we have proved +in particular the optimal integral solution $\text{OPT}$. Hence, we have proved that the cost attained by $1$-bit LRU is bounded by $k\text{OPT} + k= k(\text{OPT} +1)$ @@ -140,8 +140,9 @@ can be written as: \paragraph{(b)} We propose the following algorithm. We iterate over all edges. At each iteration we increase the dual variable of that edge until one or both -of the two dual constraints for its edge points become tight. Whenever -a constraint becomes tight, we set the primal variable its vertex to 1. +of the two dual constraints for its end points become tight. Whenever +a constraint becomes tight, we set the primal variable of its associated vertex +to 1. \begin{algorithm} \begin{algorithmic}[1] \For{$e=(u,v)\in E$} @@ -166,9 +167,9 @@ We can now conclude by observing that: 2\sum_e y_e = \sum_{v\in V}\sum_{e:v\in e} y_e \geq \sum_v c_v x_v \end{displaymath} -The equality comes from the fact that the double summation counts each -edge twice. The inequality comes from the fact that when $x_v = 1$ it means -that the dual constraint was tight, that is $c_v = \sum_{e: v\in e} y_e$. +The equality comes from the fact that the double summation counts each edge +twice. The inequality comes from the fact that $x_v = 1$ implies that that the +associated dual constraint was tight, that is $c_v = \sum_{e: v\in e} y_e$. But by weak duality, $\sum_e y_e$ is smaller than any primal feasible solution, and in particular the optimal integral solution. Hence $\sum_e y_e\leq @@ -186,8 +187,8 @@ and in particular the optimal integral solution. Hence $\sum_e y_e\leq By substitution in the objective function. We see that all feasible flows have the same value 3. Thus every feasible solution is optimal. As a consequence, the fractional solution $x =\frac{1}{2}, y = \frac{3}{2}, z =\frac{1}{2}$ is -optimal and has the same value as the integral solution $x = 1, y = 1$ (the -other integral solution is $y=1, z=1$). +optimal and has the same value as the integral solution $x = 1, y = 1, z=0$ (the +other integral solution is $x=0, y=1, z=1$). \paragraph{(b)} We introduce a dual variable $p_v$ for each vertex. The dual problem can be written: @@ -210,8 +211,8 @@ following two properties throughout the execution: \end{itemize*} At the beginning, we set $f_{u,v} = 0$ for all $(u,v)\in E$, $d_s = 0$ and $d_v -= +\infty$ for all $v$. Let us consider a step of Dijkstra's algorithm where we are examining edge -$(u,v)$ in $E$. If $p_v> p_u + L(u,v)$ then: += +\infty$ for all $v$. Let us consider a step of Dijkstra's algorithm where we +are examining edge $(u,v)$ in $E$. If $p_v> p_u + L(u,v)$ then: \begin{enumerate} \item set $p_v = p_u + L(u,v)$ and set $f_{u,v} = 1$ \item add $-1$ to $f_e$ for all edges $e$ in the previous path from $s$ |