Existence of a competitive online selector for convex body chasing

At least 7 years old · documented by

Let d4a6d4a6 denote the family of convex sets in d53ddd53d^d, let d4a6∗d4a6^* 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

cost⁡S(K):=∑t≥1∥S(K1,…,Kt−1)−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 cost⁡S(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 d∈Nd\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.

References

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.