Fetching the paper…

Reading the bibliography…

2018

A Nearly-Linear Bound for Chasing Nested Convex Bodies

Argue, C. J., Bubeck, Sébastien, Cohen, Michael B. et al.

Original
PDF
Post on X

Understand

Friedman and Linial introduced the convex body chasing problem to explore the interplay between geometry and competitive ratio in metrical task systems.

In convex body chasing, at each time step $t \in \mathbb{N}$, the online algorithm receives a request in the form of a convex body $K_t \subseteq \mathbb{R}^d$ and must output a point $x_t \in K_t$.
The goal is to minimize the total movement between consecutive output points, where the distance is measured in some given norm.
This problem is still far from being understood, and recently Bansal et al.

A Nearly-Linear Bound for Chasing Nested Convex Bodies · Around

Built on

B. Grünbaum,
1960
Earlier work this paper cites.
Paolo Manselli and Carlo Pucci,
1991
Earlier work this paper cites.
Keith Ball,
1992
Earlier work this paper cites.
Allan Borodin, Nathan Linial, and Michael E. Saks,
1992
Earlier work this paper cites.
Joel Friedman and Nathan Linial,
1993
Earlier work this paper cites.

Similar

Ravi Kannan, László Lovász, and Miklós Simonovits,
1995
Cited alongside, same era.
Niv Buchbinder and Joseph (Seffi) Naor,
2007
Cited alongside, same era.
Minghong Lin, Adam Wierman, Alan Roytman, Adam Meyerson, and Lachlan L. H. Andrew,
2012
Cited alongside, same era.
Lachlan L. H. Andrew, Siddharth Barman, Katrina Ligett, Minghong Lin, Adam Meyerson, Alan Roytman, and Adam Wierman,
2013
Cited alongside, same era.
René Sitters,
2014
Cited alongside, same era.

Then

Nikhil Bansal, Anupam Gupta, Ravishankar Krishnaswamy, Kirk Pruhs, Kevin Schewior, and Cliff Stein,
2015
Later among the works it cites.
Antonios Antoniadis, Neal Barcelo, Michael Nugent, Kirk Pruhs, Kevin Schewior, and Michele Scquizzato,
2016
Later among the works it cites.
Nikhil Bansal, Martin Böhm, Marek Eliáš, Grigorios Koumoutsos, and Seeun William Umboh,
2017
Later among the works it cites.
Ilan Lobel, Renato Paes Leme, and Adrian Vladu,
2017
Later among the works it cites.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…