Existence of a competitive online selector for convex body chasing
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.
Sources & referencesView supporting material
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
Sign in to submit a solution.
No solutions have been posted yet.