betaFeedback

WorksComputer Science

A Linear Lower Bound for Convex Body Chasing in Every Norm

Abstract

We establish an Ω(d)Ω(d) lower bound on the competitive ratio of convex body chasing in Rd\mathbb{R}^d with movement costs measured in any norm. Previously, the best known lower bound valid across all norms was Ω(d1/6)Ω(d^{1/6}), established by Papazov (2023); stronger lower bounds were known for ℓp\ell_p norms, where Bubeck, Klartag, Lee, Li, and Sellke (2019) had established a lower bound of Ω(max⁡{d,d1−1/p})Ω(\max\{\sqrt{d}, d^{1-1/p}\}). In particular, a linear lower bound was known only for the ℓ∞\ell_\infty norm, realized by the standard construction of chasing faces of a hypercube. Our lower bound strictly improves on the prior universal and ℓp\ell_p lower bounds for p<∞p < \infty and shows that the functional Steiner point algorithm of Sellke (2023) - which has competitive ratio O(d)O(d) - 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 Ω(r2)Ω(r^2) for requests of size O(r)O(r). 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 (2r+1)(2r+1)-dimensional ℓp\ell_p vector space while approximately preserving movement costs up to a factor of O(r)O(r); the general result then follows via Milman's (1985) quotient-of-a-subspace theorem.

Paper details

vlnc:W_jhfhtcjt
Version
v2 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
arXiv nonexclusive license
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…