Chasing Convex Bodies with Linear Competitive Ratio

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

Research output: Contribution to journalArticlepeer-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 languageEnglish (US)
Article number32
JournalJournal of the ACM
Volume68
Issue number5
DOIs
StatePublished - 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

Cite this