Nested convex bodies are chaseable

DOI10.1007/S00453-019-00661-XMaRDI QIDQ1987239zbMATH OpenOpenAlexWikidataFDO

Authors N. Bansal, Martin Böhm, Marek Eliáš, Grigorios Koumoutsos, Seeun William Umboh

Publication date 14 April 2020

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://ir.cwi.nl/pub/29219

zbMATH Keywords

online algorithmscompetitive analysisconvex body chasingnested convex body chasing

Mathematics Subject Classification ID

Online algorithms; streaming algorithms (68W27) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Recommendations

• Nested convex bodies are chaseable
• A Nearly-Linear Bound for Chasing Nested Convex Bodies
• Chasing Convex Bodies with Linear Competitive Ratio
• Competitively chasing convex bodies
• Chasing convex bodies and functions

Cites work

• A 2-competitive algorithm for online convex optimization with switching costs
• A Nearly-Linear Bound for Chasing Nested Convex Bodies
• A tight lower bound for online convex optimization with switching costs
• An optimal on-line algorithm for metrical task system
• Better algorithms for unfair metrical task systems and applications
• Chasing Convex Bodies with Linear Competitive Ratio
• Chasing convex bodies and functions
• Competitive analysis via regularization
• Competitively chasing convex bodies
• Nested convex bodies are chaseable
• On convex body chasing
• On the k -server conjecture
• On the competitive ratio of the work function algorithm for the \(k\)-server problem
• Online primal-dual algorithms for covering and packing
• Ramsey-type theorems for metric spaces with applications to online problems
• The Generalized Work Function Algorithm Is Competitive for the Generalized 2-Server Problem
• The generalized two-server problem
• Traversing Layered Graphs Using the Work Function Algorithm
• Understanding and using linear programming

Cited in

(6)

• Chasing Convex Bodies Optimally
• Chasing convex bodies and functions
• Nested convex bodies are chaseable
• Competitively chasing convex bodies
• Lipschitz selectors may not yield competitive algorithms for convex body chasing
• A Nearly-Linear Bound for Chasing Nested Convex Bodies

This page was built for publication: Nested convex bodies are chaseable

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