Existence of a competitive online selector for convex body chasing

Let d4a6d4a6 denote the family of convex sets in d53ddd53d^d, let d4a6d4a6^* be the set of finite strings with alphabet d4a6d4a6, and let an online selector be a map S:d4a6\tod53ddS:d4a6^*\tod53d^d satisfying S(K1,,Kt)KtS(K_1,\ldots,K_t)\in K_t for every finite sequence of convex sets. Its movement cost on a sequence of convex sets, from a starting state x0x_0, is

costS(K):=t1S(K1,,Kt1)S(K1,,Kt),\operatorname{cost}_S(\mathbf K):=\sum_{t\geq 1}\left\|S(\mathbf K_1,\ldots,\mathbf K_{t-1})-S(\mathbf K_1,\ldots,\mathbf K_t)\right\|,

where the norm is Euclidean, and cost(K)\operatorname{cost}^*(\mathbf K) is the infimum of this quantity over offline selectors. The selector is ω\omega-competitive if costS(K)ωcost(K)\operatorname{cost}_S(\mathbf K)\leq\omega\operatorname{cost}^*(\mathbf K) for every sequence K\mathbf K. Competitive-selector conjecture. For any dNd\in\mathbb N, there exists an ω\omega-competitive online selector for some ω>1\omega>1. 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

Never refreshed

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.