Better Bounds for Online Line Chasing

DOI10.4230/LIPICS.MFCS.2019.8MaRDI QIDQ5092366zbMATH OpenOpenAlexFDO

Authors Marcin Bienkowski, Jaroslaw Byrka, Christian Coester, Łukasz Jeż, Elias Koutsoupias, Marek Chrobak

Publication date 21 July 2022

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

zbMATH Keywords

competitive analysisconvex body chasingline chasing

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Recommendations

• Chasing convex bodies and functions
• Chasing Convex Bodies with Linear Competitive Ratio
• On convex body chasing
• Chasing Convex Bodies Optimally
• Competitively chasing convex bodies

Cites work

• A 2-competitive algorithm for online convex optimization with switching costs
• A Nearly-Linear Bound for Chasing Nested Convex Bodies
• An optimal on-line algorithm for metrical task system
• Chasing convex bodies and functions
• Competitive Algorithms for Layered Graph Traversal
• Competitive algorithms for server problems
• Competitively chasing convex bodies
• Nested convex bodies are chaseable
• On convex body chasing
• On the k -server conjecture
• On Traversing Layered Graphs On-Line
• The Generalized Work Function Algorithm Is Competitive for the Generalized 2-Server Problem
• Traversing Layered Graphs Using the Work Function Algorithm

Cited in

(1)

• Online geometric covering and piercing

This page was built for publication: Better Bounds for Online Line Chasing

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