Nested convex bodies are chaseable

N. Bansal, M. Bohm, M. Elias, G. Koumoutsos, S.W. Umboh

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

9 Citaten (Scopus)
80 Downloads (Pure)

Samenvatting



In the Convex Body Chasing problem, we are given an initial point v0 ∊ ℝd and an online sequence of n convex bodies F1, …, Fn. When we receive Fi, we are required to move inside Fi. Our goal is to minimize the total distance traveled. This fundamental online problem was first studied by Friedman and Linial (DCG 1993). They proved an lower bound on the competitive ratio, and conjectured that a competitive ratio depending only on d is possible. However, despite much interest in the problem, the conjecture remains wide open.

We consider the setting in which the convex bodies are nested: Fi ⊃ … ⊃ Fn. The nested setting is closely related to extending the online LP framework of Buchbinder and Naor (ESA 2005) to arbitrary linear constraints. Moreover, this setting retains much of the difficulty of the general setting and captures an essential obstacle in resolving Friedman and Linial's conjecture. In this work, we give a f(d)-competitive algorithm for chasing nested convex bodies in ℝd.



Originele taal-2Engels
Titel29th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018
RedacteurenArtur Czumaj
Plaats van producties.l.
UitgeverijSociety for Industrial and Applied Mathematics (SIAM)
Pagina's1253-1260
Aantal pagina's8
ISBN van elektronische versie9781611975031
DOI's
StatusGepubliceerd - 2018
Evenement29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2018) - Astor Crowne Plaza, New Orleans, Verenigde Staten van Amerika
Duur: 7 jan 201810 jan 2018
Congresnummer: 29
https://www.siam.org/meetings/da18/

Congres

Congres29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2018)
Verkorte titelSODA 2018
LandVerenigde Staten van Amerika
StadNew Orleans
Periode7/01/1810/01/18
Internet adres

Vingerafdruk Duik in de onderzoeksthema's van 'Nested convex bodies are chaseable'. Samen vormen ze een unieke vingerafdruk.

  • Citeer dit

    Bansal, N., Bohm, M., Elias, M., Koumoutsos, G., & Umboh, S. W. (2018). Nested convex bodies are chaseable. In A. Czumaj (editor), 29th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018 (blz. 1253-1260). Society for Industrial and Applied Mathematics (SIAM). https://doi.org/10.1137/1.9781611975031.81