Abstract
In the Convex Body Chasing problem, we are given an initial point \(v_0 \in \mathbb {R}^d\) and an online sequence of n convex bodies \(F_1, \ldots , F_n\). When we receive \(F_t\), we are required to move inside \(F_t\). Our goal is to minimize the total distance traveled. This fundamental online problem was first studied by Friedman and Linial (DCG 1993). They proved an \(\varOmega (\sqrt{d})\) lower bound on the competitive ratio, and conjectured that a competitive ratio depending only on d is possible. However, despite much interest in the problem, the conjecture remains wide open. We consider the setting in which the convex bodies are nested: \(F_1 \supset \cdots \supset F_n\). The nested setting is closely related to extending the online LP framework of Buchbinder and Naor (ESA 2005) to arbitrary linear constraints. Moreover, this setting retains much of the difficulty of the general setting and captures an essential obstacle in resolving Friedman and Linial’s conjecture. In this work, we give a f(d)-competitive algorithm for chasing nested convex bodies in \(\mathbb {R}^d\).
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Notes
If F is the intersection of halfspaces \(H_1, \ldots , H_s\), to simulate the request for F, the adversary can give \(H_1,\ldots ,H_s\) several times in a round-robin manner until the online algorithm moves inside F. Not revealing F directly can only hurt the online algorithm and does not affect the offline solution.
References
Andrew, L.H., Barman, S., Ligett, K., Lin, M., Meyerson, A., Roytman, A., Wierman, A.: A tale of two metrics: simultaneous bounds on competitiveness and regret. In: Proceedings of COLT 2013, pp. 741–763 (2013)
Andrew, L.H., Barman, S., Ligett, K., Lin, M., Meyerson, A., Roytman, A., Wierman, A.: A tale of two metrics: simultaneous bounds on competitiveness and regret. ArXiv e-prints, arXiv:1508.03769 (2015)
Antoniadis, A., Barcelo, N., Nugent, M., Pruhs, K., Schewior, K., Scquizzato, M.: Chasing convex bodies and functions.In: Proceedings of LATIN 2016, pp. 68–81 (2016)
Antoniadis, A., Schewior, K.: A tight lower bound for online convex optimization with switching costs. In: Proceedings of WAOA 2017, pp. 164–175 (2017)
Argue, C.J., Bubeck, S., Cohen, M.B., Gupta, A., Lee, Y.T.: A nearly-linear bound for chasing nested convex bodies. In: Proceedings of SODA 2019, pp. 117–122 (2019)
Argue, C.J., Gupta, A., Guruganesh, G., Tang, Z.: Chasing convex bodies with linear competitive ratio. ArXiv e-prints, arXiv:1905.11877 (2019)
Bansal, N., Böhm, M., Eliáš, M., Koumoutsos, G., Umboh, S.W.: Nested convex bodies are chaseable. In: Proceedings of SODA 2018, pp. 1253–1260 (2018)
Bansal, N., Gupta, A., Krishnaswamy, R., Pruhs, K., Schewior, K., Stein, C.: A 2-competitive algorithm for online convex optimization with switching costs. In: Proceedings of APPROX/RANDOM 2015, pp. 96–109 (2015)
Bartal, Yair, Bollobás, Béla, Mendel, Manor: Ramsey-type theorems for metric spaces with applications to online problems. J. Comput. Syst. Sci. 72(5), 890–921 (2006)
Bartal, Yair, Koutsoupias, Elias: On the competitive ratio of the work function algorithm for the k-server problem. Theor. Comput. Sci. 324(2), 337–345 (2004)
Borodin, Allan, Linial, Nathan, Saks, Michael E.: An optimal on-line algorithm for metrical task system. J. ACM 39(4), 745–763 (1992)
Bubeck, S., Lee, Y. T., Li, Y., Sellke, M.: Chasing nested convex bodies nearly optimally. ArXiv e-prints, arXiv:1811.00999 (2018)
Bubeck, S., Lee, Y.T., Li, Y., Sellke, M.: Competitively chasing convex bodies. In: Proceedings of STOC 2019, pp. 861–868 (2019)
Buchbinder, N., Chen, S., Naor, J.: Competitive analysis via regularization. In: Proceedings of SODA 2014, pp. 436–444 (2014)
Buchbinder, Niv, Naor, Joseph: Online primal-dual algorithms for covering and packing. Math. Oper. Res. 34(2), 270–286 (2009)
Burley, William R.: Traversing layered graphs using the work function algorithm. J. Algorithms 20(3), 479–511 (1996)
Chrobak, M., Larmore, L.L.: Metrical task systems, the server problem and the work function algorithm. In: Fiat, A., Gerhard, J. (eds.) Online Algorithms: The State of the Art, pp. 74–96. Springer, Berlin (1998)
Fiat, A., Mendel, M.: Better algorithms for unfair metrical task systems and applications. In: Proceedings of STOC 2000, pp. 725–734 (2000)
Friedman, Joel, Linial, Nathan: On convex body chasing. Discrete Comput. Geom. 9, 293–321 (1993)
Koutsoupias, Elias, Papadimitriou, Christos H.: On the k-server conjecture. J. ACM 42(5), 971–983 (1995)
Matoušek, Jiří, Gärtner, Bernd: Understanding and Using Linear Programming. Springer, Berlin (2007)
Sellke, M.: Chasing convex bodies optimally. ArXiv e-prints, arXiv:1905.11968 (2019)
Sitters, R.: The generalized work function algorithm is competitive for the generalized 2-server problem. SIAM J. Comput. 43(1), 96–125 (2014)
Sitters, R.A., Stougie, L.: The generalized two-server problem. J. ACM 53(3), 437–458 (2006)
Acknowledgements
We would like to thank Sébastien Bubeck, Niv Buchbinder, Anupam Gupta, Guru Guruganesh, Cristóbal Guzmán, and René Sitters for several interesting discussions.
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
This work was supported by NWO grant 639.022.211, ERC consolidator grant 617951, and GAČR grant P202/12/G061. A preliminary version of this paper appeared in SODA 2018 [7]. N. Bansal, M. Eliáš, G. Koumoutsos and S. W. Umboh: Research was done while the authors were at TU Eindhoven. M. Böhm: Research was done while the author was visiting TU Eindhoven.
Rights and permissions
About this article
Cite this article
Bansal, N., Böhm, M., Eliáš, M. et al. Nested Convex Bodies are Chaseable. Algorithmica 82, 1640–1653 (2020). https://doi.org/10.1007/s00453-019-00661-x
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00453-019-00661-x