Chasing Convex Bodies with Linear Competitive Ratio

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

doi:10.1145/3450349

Chasing Convex Bodies with Linear Competitive Ratio

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

Computer Science

Research output: Contribution to journal › Article › peer-review

Abstract

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

Original language	English (US)
Article number	32
Journal	Journal of the ACM
Volume	68
Issue number	5
DOIs	https://doi.org/10.1145/3450349
State	Published - Oct 2021

Keywords

convex body chasing
Online algorithms
Steiner point
work function

ASJC Scopus subject areas

Software
Control and Systems Engineering
Information Systems
Hardware and Architecture
Artificial Intelligence

Access to Document

10.1145/3450349

Cite this

@article{3c5945a0587b4e85868126e64b5f4f3a,

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 ⊆ ℝd the algorithm must respond with points xt ϵ Kt in an online fashion (i.e., xt is chosen before Kt+1is revealed). The objective is to minimize the sum of distances between successive points in this sequence. Bubeck et al. (STOC 2019) gave a 2O(d)-competitive algorithm for this problem. We give an algorithm that is O(min(d, √d log T))-competitive for any sequence of length T.",

keywords = "convex body chasing, Online algorithms, Steiner point, work function",

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

note = "Publisher Copyright: {\textcopyright} 2021 Copyright held by the owner/author(s). Publication rights licensed to ACM.",

year = "2021",

month = oct,

doi = "10.1145/3450349",

language = "English (US)",

volume = "68",

journal = "Journal of the ACM",

issn = "0004-5411",

publisher = "Association for Computing Machinery (ACM)",

number = "5",

}

TY - JOUR

T1 - Chasing Convex Bodies with Linear Competitive Ratio

AU - Argue, C. J.

AU - Gupta, Anupam

AU - Tang, Ziye

AU - Guruganesh, Guru

PY - 2021/10

Y1 - 2021/10

N2 - We study the problem of chasing convex bodies online: given a sequence of convex bodies Kt ⊆ ℝd the algorithm must respond with points xt ϵ Kt in an online fashion (i.e., xt is chosen before Kt+1is revealed). The objective is to minimize the sum of distances between successive points in this sequence. Bubeck et al. (STOC 2019) gave a 2O(d)-competitive algorithm for this problem. We give an algorithm that is O(min(d, √d log 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 ⊆ ℝd the algorithm must respond with points xt ϵ Kt in an online fashion (i.e., xt is chosen before Kt+1is revealed). The objective is to minimize the sum of distances between successive points in this sequence. Bubeck et al. (STOC 2019) gave a 2O(d)-competitive algorithm for this problem. We give an algorithm that is O(min(d, √d log T))-competitive for any sequence of length T.

KW - convex body chasing

KW - Online algorithms

KW - Steiner point

KW - work function

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

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

U2 - 10.1145/3450349

DO - 10.1145/3450349

M3 - Article

AN - SCOPUS:85120712766

SN - 0004-5411

VL - 68

JO - Journal of the ACM

JF - Journal of the ACM

IS - 5

M1 - 32

ER -

Chasing Convex Bodies with Linear Competitive Ratio

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this