Name
Abstract | ||
|---|---|---|
We study online competitive algorithms for the emph{line chasing problem} in Euclidean spaces $reals^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_tin 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 significantly improve this bound, by providing a~$3$-competitive algorithm for any dimension $d$. We also improve the lower bound on the competitive ratio, from $1.412$ to $1.5358$. |
Year | Venue | DocType |
|---|---|---|
2018 | mathematical foundations of computer science | Journal |
Volume | Citations | PageRank |
abs/1811.09233 | 0 | 0.34 |
References | Authors | |
0 | 6 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Marcin Bienkowski | 1 | 254 | 27.18 |
| Jaroslaw Byrka | 2 | 523 | 31.45 |
| Marek Chrobak | 3 | 1665 | 151.84 |
| Christian Coester | 4 | 0 | 2.70 |
| Lukasz Jez | 5 | 61 | 11.93 |
| Elias Koutsoupias | 6 | 1894 | 182.77 |