Chasing convex bodies with linear competitive ratio

C. J. Argue; Anupam Gupta; Guru Guruganesh; Ziye Tang

Chasing convex bodies with linear competitive ratio

C. J. Argue, Anupam Gupta, Guru Guruganesh, Ziye Tang

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

We study the problem of chasing convex bodies online: given a sequence of convex bodies K_t ⊆ R^d the algorithm must respond with points x_t ∈ K_t in an online fashion (i.e., x_t is chosen before K_t₊₁ is revealed). The objective is to minimize the total distance between successive points in this sequence. Recently, Bubeck et al. (STOC 2019) gave a 2^O(d⁾-competitive algorithm for this problem. We give an algorithm that is O(min(d, √dlog T))-competitive for any sequence of length T.

Original language	English (US)
Title of host publication	31st Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2020
Editors	Shuchi Chawla
Publisher	Association for Computing Machinery
Pages	1519-1524
Number of pages	6
ISBN (Electronic)	9781611975994
State	Published - 2020
Event	31st Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2020 - Salt Lake City, United States Duration: Jan 5 2020 → Jan 8 2020

Publication series

Name	Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
Volume	2020-January

Conference

Conference	31st Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2020
Country/Territory	United States
City	Salt Lake City
Period	1/5/20 → 1/8/20

ASJC Scopus subject areas

Software
General Mathematics

Cite this

Chasing convex bodies with linear competitive ratio. / Argue, C. J.; Gupta, Anupam; Guruganesh, Guru et al.
31st Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2020. ed. / Shuchi Chawla. Association for Computing Machinery, 2020. p. 1519-1524 (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms; Vol. 2020-January).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Argue, CJ, Gupta, A, Guruganesh, G & Tang, Z 2020, Chasing convex bodies with linear competitive ratio. in S Chawla (ed.), 31st Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2020. Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, vol. 2020-January, Association for Computing Machinery, pp. 1519-1524, 31st Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2020, Salt Lake City, United States, 1/5/20.

@inproceedings{41da4cdc33f34ffbb7302190651deba4,

title = "Chasing convex bodies with linear competitive ratio",

abstract = "We study the problem of chasing convex bodies online: given a sequence of convex bodies Kt ⊆ Rd the algorithm must respond with points xt ∈ Kt in an online fashion (i.e., xt is chosen before Kt+1 is revealed). The objective is to minimize the total distance between successive points in this sequence. Recently, Bubeck et al. (STOC 2019) gave a 2O(d)-competitive algorithm for this problem. We give an algorithm that is O(min(d, √dlog T))-competitive for any sequence of length T.",

author = "Argue, {C. J.} and Anupam Gupta and Guru Guruganesh and Ziye Tang",

note = "Publisher Copyright: Copyright {\textcopyright} 2020 by SIAM; 31st Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2020 ; Conference date: 05-01-2020 Through 08-01-2020",

year = "2020",

language = "English (US)",

series = "Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms",

publisher = "Association for Computing Machinery",

pages = "1519--1524",

editor = "Shuchi Chawla",

booktitle = "31st Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2020",

}

TY - GEN

T1 - Chasing convex bodies with linear competitive ratio

AU - Argue, C. J.

AU - Gupta, Anupam

AU - Guruganesh, Guru

AU - Tang, Ziye

PY - 2020

Y1 - 2020

N2 - We study the problem of chasing convex bodies online: given a sequence of convex bodies Kt ⊆ Rd the algorithm must respond with points xt ∈ Kt in an online fashion (i.e., xt is chosen before Kt+1 is revealed). The objective is to minimize the total distance between successive points in this sequence. Recently, Bubeck et al. (STOC 2019) gave a 2O(d)-competitive algorithm for this problem. We give an algorithm that is O(min(d, √dlog T))-competitive for any sequence of length T.

AB - We study the problem of chasing convex bodies online: given a sequence of convex bodies Kt ⊆ Rd the algorithm must respond with points xt ∈ Kt in an online fashion (i.e., xt is chosen before Kt+1 is revealed). The objective is to minimize the total distance between successive points in this sequence. Recently, Bubeck et al. (STOC 2019) gave a 2O(d)-competitive algorithm for this problem. We give an algorithm that is O(min(d, √dlog T))-competitive for any sequence of length T.

UR - http://www.scopus.com/inward/record.url?scp=85084048228&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85084048228&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:85084048228

T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

SP - 1519

EP - 1524

BT - 31st Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2020

A2 - Chawla, Shuchi

PB - Association for Computing Machinery

T2 - 31st Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2020

Y2 - 5 January 2020 through 8 January 2020

ER -

Chasing convex bodies with linear competitive ratio

Abstract

Publication series

Conference

ASJC Scopus subject areas

Other files and links

Fingerprint

Cite this