betaFeedback

Reading v1View latest version

WorksComputer Science

A Linear Lower Bound for Convex Body Chasing in Every ℓp\ell_p Norm

Abstract

We establish an Ω(d)Ω(d) lower bound on the competitive ratio of convex body chasing in Rd\mathbb{R}^d with ℓp\ell_p movement costs for any p∈[1,∞)p \in [1, \infty). Previously, the best known lower bound for general pp was Ω(max⁡{d,d1−1/p})Ω(\max\{\sqrt{d}, d^{1-1/p}\}), established by Bubeck et al. (2019); a linear lower bound was known only for p=∞p = \infty, realized by the standard construction of chasing faces of a hypercube. Our lower bound strictly improves on the prior bound for every fixed p∈[1,∞)p \in [1, \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 ℓp\ell_p 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 Ω(r2)Ω(r^2) for requests of size O(r)O(r) 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 (2r+1)(2r+1)-dimensional vector space while approximately preserving movement costs up to a factor of O(r)O(r), which establishes the lower bound.

Paper details

vlnc:W_jhfhtcjt
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…