2026-10-15T01:28:02Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:10952 2024-03-06T09:46:54Z ddc:004 open_access

Better Bounds for Online Line Chasing Bienkowski, Marcin Byrka, Jarosław Chrobak, Marek Coester, Christian Jeż, Łukasz Koutsoupias, Elias convex body chasing line chasing competitive analysis 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Marcin Bienkowski and Jarosław Byrka and Marek Chrobak and Christian Coester and Łukasz Jeż and Elias Koutsoupias 2019 Is Part Of LIPIcs, Volume 138, 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2019.8 urn:nbn:de:0030-drops-109521 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2019.8 eng https://creativecommons.org/licenses/by/3.0/legalcode