Chasing Convex Bodies with Linear Competitive Ratio
Society for Industrial and Applied Mathematics eBooks2019pp. 1519–1524
Citations Over TimeTop 10% of 2019 papers
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 on-line 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 -competitive for any sequence of length T.
Related Papers
- → A New Approach to Online Scheduling: Approximating the Optimal Competitive Ratio(2013)15 cited
- → Optimal non-preemptive semi-online scheduling on two related machines(2004)22 cited
- → Minimizing weighted flow time(2003)16 cited
- → Optimal Non-preemptive Semi-online Scheduling on Two Related Machines(2002)6 cited
- Optimal Non-Preemptive Semi-Online Scheduling on Two Related Machines(2002)