The Lazy Adversary Conjecture Fails |
| |
Authors: | Email author" target="_blank">Enoch?PesericoEmail author |
| |
Affiliation: | (1) Computer Science and Artificial Intelligence Laboratory, Massachusetts Institute of Technology, Cambridge, MA 02139, USA |
| |
Abstract: | In the context of competitive analysis of online algorithms for the k-server problem, it has been conjectured that every randomized,
memoryless online algorithm exhibits the highest competitive ratio against an offline adversary that is lazy, i.e., that will
issue requests forcing it to move one of its own servers only when this is strictly necessary to force a move on the part
of the online algorithm. We prove that, in general, this lazy adversary conjecture fails. Moreover, it fails in a very strong
sense: there are adversaries which perform arbitrarily better than any other adversary which is even slightly "lazier." |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|