Generating adversaries for request-answer games
Todd A. Gormley, Nicholas Reingold, Eric K. Torng, Jeffery Westbrook · 2000
Introduction and Results The k-server conjecture postulates the existence of an algorithm which is k-competitive for all values of k on all metric spaces. We give a procedure which is guaranteed to nd a complementary structure - an adversary strategy and a metric space such that no algorithm is k-competitive against the adversary strategy and metric space - assuming such a structure exists. That is, we prove the complement of the k-server conjecture is recursively enumerable. In fact, we give a general procedure that can perform the following search for a fairly general subset of request-answer games [3]. For a given c, nd a nite adversary strategy against which no algorithm can be better than c-competitive assuming such an adversary strategy exists. This essentially implies that for these request-answer games, \\Is c