WorksComputer Science
A Linear Lower Bound for Convex Body Chasing in Every Norm
Abstract
We establish an lower bound on the competitive ratio of convex body chasing in with movement costs for any . Previously, the best known lower bound for general was , established by Bubeck et al. (2019); a linear lower bound was known only for , realized by the standard construction of chasing faces of a hypercube. Our lower bound strictly improves on the prior bound for every fixed and shows that the functional Steiner point algorithm of Sellke (2023) - which has competitive ratio - is asymptotically optimal for every norm. Our lower bound is based on the recursive construction of Bubeck, Coester, and Rabani (2023) for metrical service systems, which gives a lower bound of for requests of size in that setting. We show that requests in their construction, each comprising a set of discrete points in a graph metric, can be mapped to the vertices of convex requests in a -dimensional vector space while approximately preserving movement costs up to a factor of , which establishes the lower bound.