Return to Answer

Yesterday I also circulated this question to my colleagues and one more example was brought to my attention.

https://arxiv.org/abs/1905.11968

https://arxiv.org/abs/1905.11877

(both of them appeared on arXiv on 28 May 2019)

They solve the following problem: one receives a convex body $K_{0}$ in $\mathbb{R}^{n}$ and chooses a point $x_{0} \in K_{0}$, then one receives another convex body $K_{1}$, and chooses a point $x_{1} \in K_{1}$ etc. The goal is after $N$ steps to make the total distance between these points $\sum_{i=1}^{N}\| x_{j}-x_{j-1}\|$ minimal. They both find an algorithm such that $\frac{\sum_{i=1}^{N}\| x_{j}-x_{j-1}\|}{\sum_{i=1}^{N}\| \tilde{x}_{j}-\tilde{x}_{j-1}\|} \leq O(\sqrt{n \ln N})$, where $\sum_{i=1}^{N}\| \tilde{x}_{j}-\tilde{x}_{j-1}\|$ is the smallest distance one could get if one would in advance knew positions and shapes of all convex bodies $\{K_{j}\}_{j=0}^{N}$.

Yesterday I also circulated this question to my colleagues and one more example was brought to my attention.

https://arxiv.org/abs/1905.11968

https://arxiv.org/abs/1905.11877

(both of them appeared on arXiv on 28 May 2019)

They solve the following problem: one receives a convex body $K_{0}$ in $\mathbb{R}^{n}$ and chooses a point $x_{0} \in K_{0}$, then one receives another convex body $K_{1}$, and chooses a point $x_{1} \in K_{1}$ etc. The goal is after $N$ steps to make the total distance between these points $\sum_{i=1}^{N}\| x_{j}-x_{j-1}\|$ minimal. They both find an algorithm such that $\frac{\sum_{i=1}^{N}\| x_{j}-x_{j-1}\|}{\sum_{i=1}^{N}\| \tilde{x}_{j}-\tilde{x}_{j-1}\|} \leq O(\sqrt{n \ln N})$, where $\sum_{i=1}^{N}\| \tilde{x}_{j}-\tilde{x}_{j-1}\|$ is the smallest distance one could get if one would in advance knew positions and shapes of all convex bodies $\{K_{j}\}_{j=0}^{N}$.

UPDATE: looks like they also are synchronized. Right before the section 2 the author of the first paper writes

After this work was completed, we were informed that C.J. Argue, Anupam Gupta, Guru Guruganesh, and Ziye Tang jointly obtained similar results for this problem. Both preprints are being posted to the ArXiv simultaneously.

Yesterday I also circulated this question to my colleagues and one more example was brought to my attention.

https://arxiv.org/abs/1905.11968

https://arxiv.org/abs/1905.11877

(both of them appeared on arXiv on 28 May 2019)

They solve the following problem: one receives a convex body $K_{0}$ in $\mathbb{R}^{n}$ and chooses a point $x_{0} \in K_{0}$, then one receives another convex body $K_{1}$, and chooses a point $x_{1} \in K_{1}$ etc. The goal is after $N$ steps to make the total distance between these points $\sum_{i=1}^{N}\| x_{j}-x_{j-1}\|$ minimal. They both find an algorithm such that $\frac{\sum_{i=1}^{N}\| x_{j}-x_{j-1}\|}{\sum_{i=1}^{N}\| \tilde{x}_{j}-\tilde{x}_{j-1}\|} \leq O(\sqrt{n \ln T})$, where $\sum_{i=1}^{N}\| \tilde{x}_{j}-\tilde{x}_{j-1}\|$ is the smallest distance one could get if one would in advance knew positions and shapes of all convex bodies $\{K_{j}\}_{j=0}^{N}$.

Yesterday I also circulated this question to my colleagues and one more example was brought to my attention.

https://arxiv.org/abs/1905.11968

https://arxiv.org/abs/1905.11877

(both of them appeared on arXiv on 28 May 2019)

They solve the following problem: one receives a convex body $K_{0}$ in $\mathbb{R}^{n}$ and chooses a point $x_{0} \in K_{0}$, then one receives another convex body $K_{1}$, and chooses a point $x_{1} \in K_{1}$ etc. The goal is after $N$ steps to make the total distance between these points $\sum_{i=1}^{N}\| x_{j}-x_{j-1}\|$ minimal. They both find an algorithm such that $\frac{\sum_{i=1}^{N}\| x_{j}-x_{j-1}\|}{\sum_{i=1}^{N}\| \tilde{x}_{j}-\tilde{x}_{j-1}\|} \leq O(\sqrt{n \ln N})$, where $\sum_{i=1}^{N}\| \tilde{x}_{j}-\tilde{x}_{j-1}\|$ is the smallest distance one could get if one would in advance knew positions and shapes of all convex bodies $\{K_{j}\}_{j=0}^{N}$.

Yesterday I also circulated this question to my colleagues and one more example was brought to my attention.

https://arxiv.org/abs/1905.11968

https://arxiv.org/abs/1905.11877

(both of them appeared on arXiv on 28 May 2019)

They solve the following problem: one receives a convex body $K_{0}$ in $\mathbb{R}^{n}$ and chooses a point $x_{0} \in K_{0}$, then one receives another convex body $K_{1}$, and choose a point $x_{1} \in K_{1}$ etc. The goal is after $N$ steps to make the total distance between these points $\sum_{i=1}^{N}\| x_{j}-x_{j-1}\|$ minimal. They both find an algorithm such that $\frac{\sum_{i=1}^{N}\| x_{j}-x_{j-1}\|}{\sum_{i=1}^{N}\| \tilde{x}_{j}-\tilde{x}_{j-1}\|} \leq O(\sqrt{n \ln T})$, where $\sum_{i=1}^{N}\| \tilde{x}_{j}-\tilde{x}_{j-1}\|$ is the smallest distance one could get if one would in advance knew positions and shapes of all convex bodies $\{K_{j}\}_{j=0}^{N}$.

Yesterday I also circulated this question to my colleagues and one more example was brought to my attention.

https://arxiv.org/abs/1905.11968

https://arxiv.org/abs/1905.11877

(both of them appeared on arXiv on 28 May 2019)

They solve the following problem: one receives a convex body $K_{0}$ in $\mathbb{R}^{n}$ and chooses a point $x_{0} \in K_{0}$, then one receives another convex body $K_{1}$, and chooses a point $x_{1} \in K_{1}$ etc. The goal is after $N$ steps to make the total distance between these points $\sum_{i=1}^{N}\| x_{j}-x_{j-1}\|$ minimal. They both find an algorithm such that $\frac{\sum_{i=1}^{N}\| x_{j}-x_{j-1}\|}{\sum_{i=1}^{N}\| \tilde{x}_{j}-\tilde{x}_{j-1}\|} \leq O(\sqrt{n \ln T})$, where $\sum_{i=1}^{N}\| \tilde{x}_{j}-\tilde{x}_{j-1}\|$ is the smallest distance one could get if one would in advance knew positions and shapes of all convex bodies $\{K_{j}\}_{j=0}^{N}$.