Chasing Convex Bodies with Linear Competitive Ratio
Chasing Convex Bodies with Linear Competitive Ratio
复制标题
以线性竞比追逐凸体
DOI：
10.1145/3450349
复制
发表时间：
2021
影响因子：
2.5
通讯作者：
Guruganesh, Guru
中科院分区：
文献类型：
--
作者：
Argue, C. J.;Gupta, Anupam;Tang, Ziye;Guruganesh, Guru
我们研究了在线追逐凸体的问题：给定凸体序列<？TeX $K_t\subseteq \mathbb {R}^d$？>算法必须以点<？TeX $x_t\in K_t$？>以在线方式（即，<? TeX $x_t$？>在此之前，“？TeX $K_{t+1}$？>已被揭露）。目标是最小化该序列中连续点之间的距离之和。Bubeck等人(STOC 2019年，《？TeX $2^{O（d）}$？>-竞争力算法解决这个问题。我们给出了一个算法，是<？$O（\min（d，\sqrt {d \log T}））$？>-竞争的任何序列的长度<？TeX $T$？>。
We study the problem of chasing convex bodies online: given a sequence of convex bodies <?TeX $K_t\subseteq \mathbb {R}^d$?> the algorithm must respond with points <?TeX $x_t\in K_t$?> in an online fashion (i.e., <?TeX $x_t$?> is chosen before <?TeX $K_{t+1}$?> is revealed). The objective is to minimize the sum of distances between successive points in this sequence. Bubeck et al. (STOC 2019) gave a <?TeX $2^{O(d)}$?>-competitive algorithm for this problem. We give an algorithm that is <?TeX $O(\min (d, \sqrt {d \log T}))$?>-competitive for any sequence of length <?TeX $T$?>.
登录
查看更多内容
LpMetrics 中的凸集中心
DOI：
--
发表时间：
1996
期刊：
影响因子：
--
作者：
Krzysztof Przeslawski
通讯作者：
Krzysztof Przeslawski
DOI：
10.1137/120885309
发表时间：
2011-10
期刊：
ArXiv
影响因子：
--
作者：
René Sitters
通讯作者：
René Sitters
DOI：
10.1137/1.9781611975482.8
发表时间：
2018
期刊：
Inf. Process. Lett.
影响因子：
--
作者：
C. Argue;Sébastien Bubeck;Michael B. Cohen;Anupam Gupta;Y. Lee
通讯作者：
Y. Lee
影响因子：
2.5
作者：
BORODIN, A;LINIAL, N;SAKS, ME
通讯作者：
SAKS, ME
凸身追击上
影响因子：
0.8
作者：
J. Friedman;N. Linial
通讯作者：
N. Linial