Chasing Convex Bodies with Linear Competitive Ratio
C. J. Argue, Anupam Gupta, Ziye Tang, Guru Guruganesh
Abstract
We study the problem of chasing convex bodies online: given a sequence of convex bodies the algorithm must respond with points in an online fashion (i.e., is chosen before is revealed). The objective is to minimize the sum of distances between successive points in this sequence. Bubeck et al. (STOC 2019) gave a -competitive algorithm for this problem. We give an algorithm that is -competitive for any sequence of length .
Topics & Concepts
CombinatoricsSequence (biology)Regular polygonCompetitive analysisMathematicsConvex bodyConvex hullGeometryUpper and lower boundsMathematical analysisBiologyGeneticsOptimization and Search ProblemsAdvanced Bandit Algorithms ResearchReinforcement Learning in Robotics