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.


    Zugriff

    Download


    Exportieren, teilen und zitieren



    Titel :

    Better Bounds for Online Line Chasing


    Beteiligte:
    Bienkowski, Marcin (Autor:in) / Byrka, Jaroslaw (Autor:in) / Chrobak, Marek (Autor:in) / Coester, Christian (Autor:in) / Jez, Lukasz (Autor:in) / Koutsoupias, Elias (Autor:in)

    Erscheinungsdatum :

    2019-01-01



    Medientyp :

    Aufsatz (Konferenz)


    Format :

    Elektronische Ressource


    Sprache :

    Englisch



    Klassifikation :

    DDC:    004 / 629




    Chasing Spacecraft

    T. Horvath / J. Inman | NTIS | 2022


    Chasing Exoplanets

    Jenkins, Jon M. | NTRS | 2017


    Chasing Spacecraft

    Tom Horvath / Jennifer Inman | NTRS


    Chasing Exoplanets

    J. M. Jenkins | NTIS | 2017


    Chasing Sustainability

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