Nested convex bodies are chaseable

DOI10.1007/S00453-019-00661-XzbMATH Open1433.68618OpenAlexW2994697260WikidataQ126542122 ScholiaQ126542122MaRDI QIDQ1987239FDOQ1987239

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

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

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)

Cites Work

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

Cited In (6)

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

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)