Existence of a competitive online selector for convex body chasing
Let denote the family of convex sets in , let be the set of finite strings with alphabet , and let an online selector be a map satisfying for every finite sequence of convex sets. Its movement cost on a sequence of convex sets, from a starting state , is
where the norm is Euclidean, and is the infimum of this quantity over offline selectors. The selector is -competitive if for every sequence . Competitive-selector conjecture. For any , there exists an -competitive online selector for some . The conjecture asks for a dimension-dependent constant-competitive deterministic strategy for chasing arbitrary convex bodies in Euclidean space. The source provides no resolution status; the existence of such selectors is the central question in the convex body chasing problem.
References
Primary source
Sébastien Bubeck, Yin Tat Lee, Yuanzhi Li and Mark Sellke, “Competitively Chasing Convex Bodies”, arXiv:1811.00887 (2018).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
No solutions have been posted yet.