Chasing Convex Bodies with Linear Competitive Ratio

被引：10

作者：

Argue, C. J. ^{[1
]}

Gupta, Anupam ^{[1
]}

Tang, Ziye ^{[1
]}

Guruganesh, Guru ^{[2
]}

机构：

[1] Carnegie Mellon Univ, 5000 Forbes Ave, Pittsburgh, PA 15217 USA

[2] Google Res, 1600 Amphitheatre Pkwy, Mountain View, CA 94043 USA

来源：

JOURNAL OF THE ACM | 2021年 / 68卷 / 05期

关键词：

Online algorithms; convex body chasing; Steiner point; work function; ALGORITHM;

D O I：

10.1145/3450349

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

We study the problem of chasing convex bodies online: given a sequence of convex bodies K-t subset of R-d the algorithm must respond with points x(t) is an element of K-t in an online fashion (i.e., xt is chosen before Kt+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 2(O(d))-competitive algorithm for this problem. We give an algorithm that is O(min(d, root d log T))-competitive for any sequence of length T.

引用

页数：10

共 18 条

[1] Second-order cone programming
Alizadeh, F
Goldfarb, D
[J]. MATHEMATICAL PROGRAMMING, 2003, 95 (01) : 3 - 51
[2] [Anonymous], 2019, P 2019 ANN ACM SIAM, DOI DOI 10.1137/1.9781611975482.8
[3] Antoniadis Antonios, 2016, LATIN 2016: Theoretical Informatics. 12th Latin American Symposium. Proceedings: LNCS 9644, P68, DOI 10.1007/978-3-662-49529-2_6
[4] Bansal N, 2018, SODA'18: PROCEEDINGS OF THE TWENTY-NINTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, P1253
[5] Benyamini Yoav, 2000, AM MATH SOC, V48
[6] AN OPTIMAL ONLINE ALGORITHM FOR METRICAL TASK SYSTEM
BORODIN, A
LINIAL, N
SAKS, ME
[J]. JOURNAL OF THE ACM, 1992, 39 (04) : 745 - 763
[7] Competitively Chasing Convex Bodies
Bubeck, Sebastien
Lee, Yin Tat
Li, Yuanzhi
Sellke, Mark
[J]. PROCEEDINGS OF THE 51ST ANNUAL ACM SIGACT SYMPOSIUM ON THEORY OF COMPUTING (STOC '19), 2019, : 861 - 868
[8] Chen N., 2018, P MACHINE LEARNING R, V75, P1574
[9] ON CONVEX BODY CHASING
FRIEDMAN, J
LINIAL, N
[J]. DISCRETE & COMPUTATIONAL GEOMETRY, 1993, 9 (03) : 293 - 321
[10] Online chasing problems for regular polygons
Fujiwara, Hiroshi
Iwama, Kazuo
Yonezawa, Kouki
[J]. INFORMATION PROCESSING LETTERS, 2008, 108 (03) : 155 - 159

← 1 2 →