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 measured in any norm. Previously, the best known lower bound valid across all norms was , established by Papazov (2023); stronger lower bounds were known for norms, where Bubeck, Klartag, Lee, Li, and Sellke (2019) had established a lower bound of . In particular, a linear lower bound was known only for the norm, realized by the standard construction of chasing faces of a hypercube. Our lower bound strictly improves on the prior universal and lower bounds for and shows that the functional Steiner point algorithm of Sellke (2023) - which has competitive ratio - is asymptotically optimal for every norm. Our approach 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 . 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 ; the general result then follows via Milman's (1985) quotient-of-a-subspace theorem.