LIPIcs.MFCS.2019.8.pdf
- Filesize: 0.51 MB
- 13 pages
Document
Better Bounds for Online Line Chasing
Authors
Marcin Bienkowski 
,
Jarosław Byrka ,
Marek Chrobak ,
Christian Coester ,
Łukasz Jeż ,
Elias Koutsoupias
-
Part of:
Volume:
44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: Mathematical Foundations of Computer Science (MFCS) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2019-08-20
File
Document Identifiers
Author Details
Cite As Get BibTex
Marcin Bienkowski, Jarosław Byrka, Marek Chrobak, Christian Coester, Łukasz Jeż, and Elias Koutsoupias. Better Bounds for Online Line Chasing. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 8:1-8:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.MFCS.2019.8
Abstract
We study online competitive algorithms for the line chasing problem in Euclidean spaces R^d, where the input consists of an initial point P_0 and a sequence of lines X_1, X_2, ..., X_m, revealed one at a time. At each step t, when the line X_t is revealed, the algorithm must determine a point P_t in X_t. An online algorithm is called c-competitive if for any input sequence the path P_0, P_1 , ..., P_m it computes has length at most c times the optimum path. The line chasing problem is a variant of a more general convex body chasing problem, where the sets X_t are arbitrary convex sets.
To date, the best competitive ratio for the line chasing problem was 28.1, even in the plane. We improve this bound by providing a simple 3-competitive algorithm for any dimension d. We complement this bound by a matching lower bound for algorithms that are memoryless in the sense of our algorithm, and a lower bound of 1.5358 for arbitrary algorithms. The latter bound also improves upon the previous lower bound of sqrt{2}~=1.412 for convex body chasing in 2 dimensions.
Subject Classification
ACM Subject Classification
- Theory of computation → Online algorithms
Keywords
- convex body chasing
- line chasing
- competitive analysis
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- Antonios Antoniadis, Neal Barcelo, Michael Nugent, Kirk Pruhs, Kevin Schewior, and Michele Scquizzato. Chasing Convex Bodies and Functions. In Proc. 12th Latin American Theoretical Informatics Symposium (LATIN), pages 68-81, 2016. URL: https://doi.org/10.1007/978-3-662-49529-2_6.
-
C. J. Argue, Sébastien Bubeck, Michael B. Cohen, Anupam Gupta, and Yin Tat Lee. A Nearly-Linear Bound for Chasing Nested Convex Bodies. In Proc. 30th ACM-SIAM Symp. on Discrete Algorithms (SODA), pages 117-122, 2019.
- Nikhil Bansal, Martin Böhm, Marek Eliás, Grigorios Koumoutsos, and Seeun William Umboh. Nested Convex Bodies are Chaseable. In Proc. 29th ACM-SIAM Symp. on Discrete Algorithms (SODA), pages 1253-1260, 2018. URL: https://doi.org/10.1137/1.9781611975031.81.
- Nikhil Bansal, Anupam Gupta, Ravishankar Krishnaswamy, Kirk Pruhs, Kevin Schewior, and Clifford Stein. A 2-Competitive Algorithm For Online Convex Optimization With Switching Costs. In Proc. Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM), pages 96-109, 2015. URL: https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2015.96.
- Allan Borodin, Nathan Linial, and Michael E. Saks. An Optimal On-Line Algorithm for Metrical Task System. J. ACM, 39(4):745-763, 1992. URL: https://doi.org/10.1145/146585.146588.
- Sébastien Bubeck, Yin Tat Lee, Yuanzhi Li, and Mark Sellke. Chasing Nested Convex Bodies Nearly Optimally. CoRR, abs/1811.00999, 2018. URL: http://arxiv.org/abs/1811.00999.
- Sébastien Bubeck, Yin Tat Lee, Yuanzhi Li, and Mark Sellke. Competitively chasing convex bodies. In Proc. 51st ACM Symp. on Theory of Computing (STOC), pages 861-868, 2019. URL: https://doi.org/10.1145/3313276.3316314.
- William R. Burley. Traversing Layered Graphs Using the Work Function Algorithm. J. Algorithms, 20(3):479-511, 1996. URL: https://doi.org/10.1006/jagm.1996.0024.
- Marek Chrobak and Lawrence L. Larmore. Metrical Task Systems, the Server Problem and the Work Function Algorithm. In Online Algorithms, The State of the Art (Proc. Dagstuhl Seminar, June 1996), pages 74-96, 1996. URL: https://doi.org/10.1007/BFb0029565.
- Amos Fiat, Dean P. Foster, Howard J. Karloff, Yuval Rabani, Yiftach Ravid, and Sundar Vishwanathan. Competitive Algorithms for Layered Graph Traversal. SIAM J. Comput., 28(2):447-462, 1998. URL: https://doi.org/10.1137/S0097539795279943.
- Joel Friedman and Nathan Linial. On Convex Body Chasing. Discrete & Computational Geometry, 9:293-321, 1993. URL: https://doi.org/10.1007/BF02189324.
- Elias Koutsoupias and Christos H. Papadimitriou. On the k-Server Conjecture. J. ACM, 42(5):971-983, 1995. URL: https://doi.org/10.1145/210118.210128.
- Minghong Lin, Adam Wierman, Lachlan L. H. Andrew, and Eno Thereska. Dynamic Right-Sizing for Power-Proportional Data Centers. IEEE/ACM Trans. Netw., 21(5):1378-1391, 2013. URL: https://doi.org/10.1109/TNET.2012.2226216.
- Mark S. Manasse, Lyle A. McGeoch, and Daniel Dominic Sleator. Competitive Algorithms for Server Problems. J. Algorithms, 11(2):208-230, 1990. URL: https://doi.org/10.1016/0196-6774(90)90003-W.
- H. Ramesh. On Traversing Layered Graphs On-Line. J. Algorithms, 18(3):480-512, 1995. URL: https://doi.org/10.1006/jagm.1995.1019.
- René Sitters. The Generalized Work Function Algorithm Is Competitive for the Generalized 2-Server Problem. SIAM J. Comput., 43(1):96-125, 2014. URL: https://doi.org/10.1137/120885309.