Chasing Small Sets Optimally Against Adaptive Adversaries

We study deterministic online algorithms for the problem of chasing sets of cardinality at most k in a metric space, also known as metrical service systems and equivalent to width-k layered graph traversal. We resolve the 30-year-old gap of Omega(2k)cap O(k2k) on the competitive ratio of this problem by giving an O(2k)-competitive deterministic algorithm. This bound is optimal even among randomized algorithms against adaptive adversaries. We also (slightly) improve the deterministic lower bound to Dk, defined recursively by D1=1 and Dk+1=2Dk+√8+8Dk+3, which we conjecture to be exactly tight. For k=3, we provide a matching upper bound of D3. Our results imply slightly improved upper and lower bounds for distributed asynchronous collective tree exploration and for the k-taxi problem, respectively. Our algorithm generalizes the classical doubling strategy, previously known to be optimal for k=2. The previous best bound for general k was achieved by the generalized work function algorithm (WFA), and was known to be tight for WFA. Our improved bound therefore implies that WFA is sub-optimal for chasing small sets.