Competitiveness via primal-dual
Marek Chrobák · ACM SIGACT News · 2007
From the editor: So you are reading this paper on online algorithms. At first the paper reads well, and you get through the first few pages in no time -- until the authors pull a rabbit out of a hat: the online algorithm. Fine, you say to yourself, patience, it all will start making sense when I get to the analysis, just keep reading. But it doesn't -- the proof is by an even more mysterious trick, and this time out of the hat comes a humpback whale: yes, a potential function. Sound familiar?