Here’s a recap of some of the questions, answers, and pointers for yesterday’s lecture.
Adversaries in Randomized Settings
In the randomized setting, we used the notion of “oblivious” adversaries who first fixed the request sequence $\sigma$, and then we considered the ratio of $\mathbb{E}[ALG(\sigma)]$ versus $OPT(\sigma)$. This was contrasted with an adaptive adversary which could build the request sequence online, i.e., decide $\sigma_2$ after it saw the response to the algorithm on $\sigma_1$. We said the latter was more powerful, and we were going to stick with the former, oblivious adversaries. Corwin had asked for an example showing the difference: one example is the ski-rental problem itself.
In ski rental, the oblivious adversary fixes the length of the sequence up-front, and then the algorithm wants to randomize over the choice of the “buying day”, so that whatever the (unknown) length of the sequence is, the algorithm does not buy on (or close to) the last day of the sequence. E.g., for $B=4$, the optimal strategy was to choose the “buying buy” to be $i \leq 4$ with probability $(c/4)(3/4)^{4-i}$. Hence we would choose a number between $1$ and $4$, where $4$ is chosen with probability $c/4 = 0.365$, etc. This gave a better-than-$(2-1/4)$ competitive ratio.
In fact, having an oblivious adversary was crucial to this randomized analysis, because it allowed us to formulate the problem as a two-player zero-sum game. In the adaptive case, it’s a multi-round game and the same minimax ideas don’t apply any more.
Moreover, once you have an adaptive strategy, the competitive ratio is no better than $2-1/B$. Indeed, consider the following adversary which looks at the algorithm’s decisions before it makes the next decision: as soon as the algorithm buys, the adversary stops the sequence. You can check that you cannot do better than $2-1/B$ against such an adversary!
In fact, this paper of Ben-David and others shows a general theorem, that in the online setting, the competitive ratio against an adaptive adversary cannot be better than in the deterministic setting. They consider other, more nuanced adversaries (does the adversary have to also make decisions online, or does it make decisions only at the end?, etc.), check out the paper for details.
The Finite Ski-Rental Game
Alireza asked for more details about why we could reduce the ski-rental game to just $4 \times 4$. An exercise will appear on the next HW, but here’s the simple idea. I claim that the adversary should never choose an input $I_j$ for $j \geq B$, it should instead choose $I_\infty$. Indeed, the OPT cost will be the same for those two columns, and maybe the algorithm may be dumb and screw up. Formally, for every algorithm $i$, I claim that the cost of $(A_i, I_j)$ is no less than that of $(A_i, I_\infty)$ when $j \geq B$, so the column $I_\infty$ dominates $I_j$ for every row $A_i$.
Hence, we’re left with $I_1, I_2, \ldots, I_{B-1}, I_\infty$, the other columns are strictly dominated and can be removed. And now you can show that the algorithm player should place no mass on algorithm $A_i$ for $i > B$, given this smaller set of columns. So you can remove all but the first $B$ rows. And it leaves you with the $B \times B$ game that we analyzed.
Details on the Randomized Paging Analysis
Some of you asked for more details on the randomized paging analysis, I’ll post about that later. In fact, the analysis also addresses the issue Alireza mentioned about the additive term in the deterministic paging, I think. Watch this space for more details.
X-Fit Bin-Packing Algorithms
Corwin also asked whether First-Fit was better than $2$. Recall that first-fit is the algorithm that opens the bins sequentially, and puts the next item in the first of these bins that can hold it. (So it is really an online algorithm.) Jeff Ullman showed that first-fit uses at most $1.7 OPT + 1$ bins. This was improved by Dosa and Sgall to $\lfloor 1.7 OPT \rfloor$, so there’s no additive term any more. They also show the result is tight.
There are other algorithms of this ilk. Next-fit seems more wasteful: whenever the current item $i$ does not fit into the current bin, it closes this bin forever, and opens a new bin, makes that the current bin, and puts $i$ in it. Note that next-fit is very fast to implement, since you only have to see if the current item fits into the current bin. It is easy to show that Next-Fit uses $2OPT+1$ bins. (Why? For any two consecutive bins, the total size must be strictly more than $1$, that is why you opened the latter bin. In fact this also gives a shorter analysis for first-fit than the one I gave in lecture.) And by being a bit more careful with strict inequalities and taking floors, you can show that both first-fit and next-fit use no more than $2OPT$.
There’s also Best-Fit, which puts the item into the bin where it fits the best and leaves the least space. And Worst-Fit, which puts the item into the occupied bin where it fits the worst and leaves the most space, you can think of this as trying to load-balance, and not leave any small gaps which may be difficult to fill. As long as you don’t open new bins when the current item fits into the last-opened bin, you can always use the analysis above and show a factor of $2$. And sometimes you do better: people have come up with ingenious analyses for each of these cases. E.g., Dosa and Sgall have also shown $\lfloor 1.7 OPT \rfloor$ for Best-Fit.
For each of these, you can also sort the items and consider then in decreasing order: things improve, e.g., you can easily improve to $1.5$ for first-fit-decreasing (and that would be optimal given the hardness from partition). Please Google for more results, if you’re interested!