Chasing Convex Bodies with Linear Competitive Ratio

2019/05/28 by Argue, C. J., Gupta, Anupam, Guruganesh, Guru +1 · 3 citations
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Metric Geometry (math.MG)

paper · doi:10.48550/arxiv.1905.11877

Abstract

We study the problem of chasing convex bodies online: given a sequence of convex bodies K_t⊆ ℝ^d the algorithm must respond with points x_t∈ K_t in an online fashion (i.e., x_t is chosen before K_t+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, √(d log T)))-competitive for any sequence of length T.

Cited by

• Chasing Submodular Objectives, and Submodular Maximization via Cutting Planes
• Universal Dynamic Regret and Constraint Violation Bounds for Constrained Online Convex Optimization
• Low Recourse Arborescence Forests Under Uniformly Random Arcs

Related

• Chasing Convex Bodies Optimally
• A Nearly-Linear Bound for Chasing Nested Convex Bodies
• Nested Convex Bodies are Chaseable
• Competitively Chasing Convex Bodies
• Chasing Nested Convex Bodies Nearly Optimally