Competitively chasing convex bodies

DOI10.1137/20M1312332MaRDI QIDQ7036479zbMATH OpenFDO

Authors Sébastien Bubeck, Yin Tat Lee, Yuanzhi Li, Mark Sellke

Publication date 28 January 2025

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/20M1312332

zbMATH Keywords

chasing convex bodiesconvex optimizationmetrical task systemsonline algorithms

Mathematics Subject Classification ID

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

Cites work

• \(k\)-server via multiscale entropic regularization
• A Nearly-Linear Bound for Chasing Nested Convex Bodies
• Chasing convex bodies and functions
• Chasing Convex Bodies Optimally
• Chasing Convex Bodies with Linear Competitive Ratio
• Chasing Nested Convex Bodies Nearly Optimally
• Competitive algorithms for server problems
• Competitive analysis via regularization
• Fusible HSTs and the randomized k-server conjecture
• Isoperimetric problems for convex bodies and a localization lemma
• Nested convex bodies are chaseable
• On convex body chasing
• Solving convex programs by random walks

This page was built for publication: Competitively chasing convex bodies

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