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

Internet

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

Ejemplares similares