Better Bounds for Online Line Chasing

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.

Authors

• Marcin Bienkowski
• Jaroslaw Byrka
• Marek Chrobak
• Christian Coester
• Lukasz Jez
• Elias Koutsoupias

Keywords

• convex body chasing
• line chasing
• competitive analysis