|
| | | | |
| | | |
| Stat |
Members: 3645
Articles: 2'506'133
Articles rated: 2609
26 April 2024 |
|
| | | | |
|
Article overview
| |
|
|
Better Bounds for Online Line Chasing | | Marcin Bienkowski
; Jarosław Byrka
; Marek Chrobak
; Christian Coester
; Łukasz Jeż
; Elias Koutsoupias
; | | Date: |
22 Nov 2018 | | Abstract: | We study online competitive algorithms for the emph{line chasing problem} in
Euclidean spaces $
eals^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$. | | Source: | arXiv, 1811.9233 | | Services: | Forum | Review | PDF | Favorites | |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
browser Mozilla/5.0 AppleWebKit/537.36 (KHTML, like Gecko; compatible; ClaudeBot/1.0; +claudebot@anthropic.com)
|
| |
|
|
|
|
News, job offers and information for researchers and scientists:
| |
REGISTER