License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.MFCS.2019.8
URN: urn:nbn:de:0030-drops-109521
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/10952/
Bienkowski, Marcin ;
Byrka, Jaroslaw ;
Chrobak, Marek ;
Coester, Christian ;
Jez, Lukasz ;
Koutsoupias, Elias
Better Bounds for Online Line Chasing
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.
BibTeX - Entry
@InProceedings{bienkowski_et_al:LIPIcs:2019:10952,
author = {Marcin Bienkowski and Jaroslaw Byrka and Marek Chrobak and Christian Coester and Lukasz Jez and Elias Koutsoupias},
title = {{Better Bounds for Online Line Chasing}},
booktitle = {44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)},
pages = {8:1--8:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-117-7},
ISSN = {1868-8969},
year = {2019},
volume = {138},
editor = {Peter Rossmanith and Pinar Heggernes and Joost-Pieter Katoen},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/10952},
URN = {urn:nbn:de:0030-drops-109521},
doi = {10.4230/LIPIcs.MFCS.2019.8},
annote = {Keywords: convex body chasing, line chasing, competitive analysis}
}
|
Keywords: |
|
convex body chasing, line chasing, competitive analysis |
|
Collection: |
|
44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019) |
|
Issue Date: |
|
2019 |
|
Date of publication: |
|
20.08.2019 |
