Linear lower bound proven for convex body chasing in all lp norms
A Linear Lower Bound for Convex Body Chasing in Every $\ell_p$ Norm
Data Structures and AlgorithmsComputational Geometry
Summary
Convex body chasing is a problem where you try to follow a moving shape in space while using the least amount of movement possible. The authors found a new, stronger minimum bound on how well any method can do this in different types of distance measurements (called lp norms). This means no method can be better than this limit, and an existing method is shown to be the best possible in terms of how much it moves. Their proof builds on previous work using complex constructions to translate one problem’s limits into another.
What this means in practice
- •For algorithm designers: Know the best possible performance limits when designing algorithms for online optimization problems involving spatial movement.
- •For operations research teams: Understand limits in real-time decision making for moving resources efficiently in multidimensional cost settings.
A theory result. No direct application yet.
Authors
Nicolas Christianson
Abstract
We establish an $Ω(d)$ lower bound on the competitive ratio of convex body chasing in $\mathbb{R}^d$ with $\ell_p$ movement costs for any $p \in [1, \infty)$. Previously, the best known lower bound for general $p$ was $Ω(\max\{\sqrt{d}, d^{1-1/p}\})$, established by Bubeck et al. (2019); a linear lower bound was known only for $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 \in [1, \infty)$ and shows that the functional Steiner point algorithm of Sellke (2023) - which has competitive ratio $O(d)$ - is asymptotically optimal for every $\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 $Ω(r^2)$ for requests of size $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)$-dimensional vector space while approximately preserving movement costs up to a factor of $O(r)$, which establishes the lower bound.