Competitiveness via primal-dual
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...
| Published in: | ACM SIGACT News |
|---|---|
| Main Author: | |
| Format: | Article in Journal/Newspaper |
| Language: | English |
| Published: |
Association for Computing Machinery (ACM)
2007
|
| Subjects: | |
| Online Access: | http://dx.doi.org/10.1145/1324215.1324233 https://dl.acm.org/doi/pdf/10.1145/1324215.1324233 |
| Summary: | 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? |
|---|