Randomized Online Computation with High Probability Guarantees

We study the relationship between the competitive ratio and the tail distribution of randomized online problems. To this end, we identify a broad class of online problems for which the existence of a randomized online algorithm with constant expected competitive ratio r implies the existence of a ra...

Descripción completa

Detalles Bibliográficos
Autores principales: Komm, Dennis, Královič, Rastislav, Královič, Richard, Mömke, Tobias
Formato: Online Artículo Texto
Lenguaje:English
Publicado: Springer US 2022
Materias:
Article
Acceso en línea:https://www.ncbi.nlm.nih.gov/pmc/articles/PMC9050809/
https://www.ncbi.nlm.nih.gov/pubmed/35535223
http://dx.doi.org/10.1007/s00453-022-00925-z
_version_ 1784696449488912384
author Komm, Dennis
Královič, Rastislav
Královič, Richard
Mömke, Tobias
author_facet Komm, Dennis
Královič, Rastislav
Královič, Richard
Mömke, Tobias
author_sort Komm, Dennis
collection PubMed
description We study the relationship between the competitive ratio and the tail distribution of randomized online problems. To this end, we identify a broad class of online problems for which the existence of a randomized online algorithm with constant expected competitive ratio r implies the existence of a randomized online algorithm that has a competitive ratio of [Formula: see text] with high probability, measured with respect to the optimal profit or cost, respectively. The class of problems includes some of the well-studied online problems such as paging, k-server, and metrical task systems on finite metric spaces.
format Online
Article
Text
id pubmed-9050809
institution National Center for Biotechnology Information
language English
publishDate 2022
publisher Springer US
record_format MEDLINE/PubMed
spelling pubmed-90508092022-05-07 Randomized Online Computation with High Probability Guarantees Komm, Dennis Královič, Rastislav Královič, Richard Mömke, Tobias Algorithmica Article We study the relationship between the competitive ratio and the tail distribution of randomized online problems. To this end, we identify a broad class of online problems for which the existence of a randomized online algorithm with constant expected competitive ratio r implies the existence of a randomized online algorithm that has a competitive ratio of [Formula: see text] with high probability, measured with respect to the optimal profit or cost, respectively. The class of problems includes some of the well-studied online problems such as paging, k-server, and metrical task systems on finite metric spaces. Springer US 2022-01-30 2022 /pmc/articles/PMC9050809/ /pubmed/35535223 http://dx.doi.org/10.1007/s00453-022-00925-z Text en © The Author(s) 2022 https://creativecommons.org/licenses/by/4.0/Open AccessThis article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article’s Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article’s Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/ (https://creativecommons.org/licenses/by/4.0/) .
spellingShingle Article
Komm, Dennis
Královič, Rastislav
Královič, Richard
Mömke, Tobias
Randomized Online Computation with High Probability Guarantees
title Randomized Online Computation with High Probability Guarantees
title_full Randomized Online Computation with High Probability Guarantees
title_fullStr Randomized Online Computation with High Probability Guarantees
title_full_unstemmed Randomized Online Computation with High Probability Guarantees
title_short Randomized Online Computation with High Probability Guarantees
title_sort randomized online computation with high probability guarantees
topic Article
url https://www.ncbi.nlm.nih.gov/pmc/articles/PMC9050809/
https://www.ncbi.nlm.nih.gov/pubmed/35535223
http://dx.doi.org/10.1007/s00453-022-00925-z
work_keys_str_mv AT kommdennis randomizedonlinecomputationwithhighprobabilityguarantees
AT kralovicrastislav randomizedonlinecomputationwithhighprobabilityguarantees
AT kralovicrichard randomizedonlinecomputationwithhighprobabilityguarantees
AT momketobias randomizedonlinecomputationwithhighprobabilityguarantees

Ejemplares similares