A Nearly-Linear Bound for Chasing Nested Convex Bodies

DOI10.1137/1.9781611975482.8MaRDI QIDQ5236189zbMATH OpenOpenAlexFDO

Authors C. J. Argue, Sébastien Bubeck, Michael B. Cohen, Anupam Gupta, Yin Tat Lee

Publication date 15 October 2019

Published in Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1806.08865

Mathematics Subject Classification ID

Computational aspects related to convexity (52B55) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Online algorithms; streaming algorithms (68W27) Analysis of algorithms (68W40)

Abstract: Friedman and Linial introduced the convex body chasing problem to explore the interplay between geometry and competitive ratio in metrical task systems. In convex body chasing, at each time step $tinmathbbN$, the online algorithm receives a request in the form of a convex body $K_{t}subseteqmathbb{R}^d$ and must output a point $x_{t}in{K}_t$. The goal is to minimize the total movement between consecutive output points, where the distance is measured in some given norm. This problem is still far from being understood, and recently Bansal et al. gave an algorithm for the nested version, where each convex body is contained within the previous one. We propose a different strategy which is $O(dlogd)$-competitive algorithm for this nested convex body chasing problem, improving substantially over previous work. Our algorithm works for any norm. This result is almost tight, given an $Omega(d)$ lower bound for the $el{l}_{infty}$.

Recommendations

• Chasing Nested Convex Bodies Nearly Optimally
• Nested convex bodies are chaseable
• Nested convex bodies are chaseable
• Chasing Convex Bodies Optimally
• On convex body chasing
• Chasing convex bodies with linear competitive ratio (invited paper)
• Chasing Convex Bodies with Linear Competitive Ratio
• Chasing Convex Bodies with Linear Competitive Ratio
• Competitively chasing convex bodies
• scientific article; zbMATH DE number 6846375

Cited in

(15)

• On convex body chasing
• Nested convex bodies are chaseable
• Chasing convex bodies and functions
• scientific article; zbMATH DE number 6846375 (Why is no real title available?)
• Nested convex bodies are chaseable
• Path length bounds for gradient descent and flow
• Chasing Convex Bodies with Linear Competitive Ratio
• Better Bounds for Online Line Chasing
• Chasing Nested Convex Bodies Nearly Optimally
• Chasing Convex Bodies Optimally
• Lipschitz selectors may not yield competitive algorithms for convex body chasing
• Chasing convex bodies optimally
• Provably robust online voltage control for distribution networks with line parameter estimation
• Competitively chasing convex bodies
• Metrical service systems with transformations

This page was built for publication: A Nearly-Linear Bound for Chasing Nested Convex Bodies

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5236189)