Nested convex bodies are chaseable

DOI10.1007/s00453-019-00661-xzbMath1433.68618OpenAlexW2994697260WikidataQ126542122 ScholiaQ126542122MaRDI QIDQ1987239

Seeun William Umboh, Nikhil Bansal, Grigorios Koumoutsos, Martin Böhm, Marek Eliáš

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

competitive analysisonline algorithmsconvex body chasingnested convex body chasing

Mathematics Subject Classification ID

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

Related Items (1)

Lipschitz selectors may not yield competitive algorithms for convex body chasing

Cites Work

• Unnamed Item
• Understanding and using linear programming
• On convex body chasing
• A tight lower bound for online convex optimization with switching costs
• On the competitive ratio of the work function algorithm for the \(k\)-server problem
• Ramsey-type theorems for metric spaces with applications to online problems
• Chasing Convex Bodies and Functions
• Online Primal-Dual Algorithms for Covering and Packing
• Better algorithms for unfair metrical task systems and applications
• The generalized two-server problem
• An optimal on-line algorithm for metrical task system
• On the k -server conjecture
• Traversing Layered Graphs Using the Work Function Algorithm
• 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

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