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.


    Access

    Download


    Export, share and cite



    Title :

    Better Bounds for Online Line Chasing


    Contributors:

    Publication date :

    2019-01-01



    Type of media :

    Conference paper


    Type of material :

    Electronic Resource


    Language :

    English



    Classification :

    DDC:    004 / 629




    Chasing Spacecraft

    T. Horvath / J. Inman | NTIS | 2022


    Chasing Exoplanets

    Jenkins, Jon M. | NTRS | 2017


    Chasing Sustainability

    Langlois, Myriam / van Lierop, Dea / Wasfi, Rania A. et al. | Transportation Research Record | 2015


    Chasing Spacecraft

    Tom Horvath / Jennifer Inman | NTRS


    Chasing Exoplanets

    J. M. Jenkins | NTIS | 2017